1 /* Functions to determine/estimate number of iterations of a loop. 2 Copyright (C) 2004-2018 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by the 8 Free Software Foundation; either version 3, or (at your option) any 9 later version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 #include "config.h" 21 #include "system.h" 22 #include "coretypes.h" 23 #include "backend.h" 24 #include "rtl.h" 25 #include "tree.h" 26 #include "gimple.h" 27 #include "tree-pass.h" 28 #include "ssa.h" 29 #include "gimple-pretty-print.h" 30 #include "diagnostic-core.h" 31 #include "stor-layout.h" 32 #include "fold-const.h" 33 #include "calls.h" 34 #include "intl.h" 35 #include "gimplify.h" 36 #include "gimple-iterator.h" 37 #include "tree-cfg.h" 38 #include "tree-ssa-loop-ivopts.h" 39 #include "tree-ssa-loop-niter.h" 40 #include "tree-ssa-loop.h" 41 #include "cfgloop.h" 42 #include "tree-chrec.h" 43 #include "tree-scalar-evolution.h" 44 #include "params.h" 45 #include "tree-dfa.h" 46 47 48 /* The maximum number of dominator BBs we search for conditions 49 of loop header copies we use for simplifying a conditional 50 expression. */ 51 #define MAX_DOMINATORS_TO_WALK 8 52 53 /* 54 55 Analysis of number of iterations of an affine exit test. 56 57 */ 58 59 /* Bounds on some value, BELOW <= X <= UP. */ 60 61 struct bounds 62 { 63 mpz_t below, up; 64 }; 65 66 67 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */ 68 69 static void 70 split_to_var_and_offset (tree expr, tree *var, mpz_t offset) 71 { 72 tree type = TREE_TYPE (expr); 73 tree op0, op1; 74 bool negate = false; 75 76 *var = expr; 77 mpz_set_ui (offset, 0); 78 79 switch (TREE_CODE (expr)) 80 { 81 case MINUS_EXPR: 82 negate = true; 83 /* Fallthru. */ 84 85 case PLUS_EXPR: 86 case POINTER_PLUS_EXPR: 87 op0 = TREE_OPERAND (expr, 0); 88 op1 = TREE_OPERAND (expr, 1); 89 90 if (TREE_CODE (op1) != INTEGER_CST) 91 break; 92 93 *var = op0; 94 /* Always sign extend the offset. */ 95 wi::to_mpz (wi::to_wide (op1), offset, SIGNED); 96 if (negate) 97 mpz_neg (offset, offset); 98 break; 99 100 case INTEGER_CST: 101 *var = build_int_cst_type (type, 0); 102 wi::to_mpz (wi::to_wide (expr), offset, TYPE_SIGN (type)); 103 break; 104 105 default: 106 break; 107 } 108 } 109 110 /* From condition C0 CMP C1 derives information regarding the value range 111 of VAR, which is of TYPE. Results are stored in to BELOW and UP. */ 112 113 static void 114 refine_value_range_using_guard (tree type, tree var, 115 tree c0, enum tree_code cmp, tree c1, 116 mpz_t below, mpz_t up) 117 { 118 tree varc0, varc1, ctype; 119 mpz_t offc0, offc1; 120 mpz_t mint, maxt, minc1, maxc1; 121 wide_int minv, maxv; 122 bool no_wrap = nowrap_type_p (type); 123 bool c0_ok, c1_ok; 124 signop sgn = TYPE_SIGN (type); 125 126 switch (cmp) 127 { 128 case LT_EXPR: 129 case LE_EXPR: 130 case GT_EXPR: 131 case GE_EXPR: 132 STRIP_SIGN_NOPS (c0); 133 STRIP_SIGN_NOPS (c1); 134 ctype = TREE_TYPE (c0); 135 if (!useless_type_conversion_p (ctype, type)) 136 return; 137 138 break; 139 140 case EQ_EXPR: 141 /* We could derive quite precise information from EQ_EXPR, however, 142 such a guard is unlikely to appear, so we do not bother with 143 handling it. */ 144 return; 145 146 case NE_EXPR: 147 /* NE_EXPR comparisons do not contain much of useful information, 148 except for cases of comparing with bounds. */ 149 if (TREE_CODE (c1) != INTEGER_CST 150 || !INTEGRAL_TYPE_P (type)) 151 return; 152 153 /* Ensure that the condition speaks about an expression in the same 154 type as X and Y. */ 155 ctype = TREE_TYPE (c0); 156 if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type)) 157 return; 158 c0 = fold_convert (type, c0); 159 c1 = fold_convert (type, c1); 160 161 if (operand_equal_p (var, c0, 0)) 162 { 163 mpz_t valc1; 164 165 /* Case of comparing VAR with its below/up bounds. */ 166 mpz_init (valc1); 167 wi::to_mpz (wi::to_wide (c1), valc1, TYPE_SIGN (type)); 168 if (mpz_cmp (valc1, below) == 0) 169 cmp = GT_EXPR; 170 if (mpz_cmp (valc1, up) == 0) 171 cmp = LT_EXPR; 172 173 mpz_clear (valc1); 174 } 175 else 176 { 177 /* Case of comparing with the bounds of the type. */ 178 wide_int min = wi::min_value (type); 179 wide_int max = wi::max_value (type); 180 181 if (wi::to_wide (c1) == min) 182 cmp = GT_EXPR; 183 if (wi::to_wide (c1) == max) 184 cmp = LT_EXPR; 185 } 186 187 /* Quick return if no useful information. */ 188 if (cmp == NE_EXPR) 189 return; 190 191 break; 192 193 default: 194 return; 195 } 196 197 mpz_init (offc0); 198 mpz_init (offc1); 199 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0); 200 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1); 201 202 /* We are only interested in comparisons of expressions based on VAR. */ 203 if (operand_equal_p (var, varc1, 0)) 204 { 205 std::swap (varc0, varc1); 206 mpz_swap (offc0, offc1); 207 cmp = swap_tree_comparison (cmp); 208 } 209 else if (!operand_equal_p (var, varc0, 0)) 210 { 211 mpz_clear (offc0); 212 mpz_clear (offc1); 213 return; 214 } 215 216 mpz_init (mint); 217 mpz_init (maxt); 218 get_type_static_bounds (type, mint, maxt); 219 mpz_init (minc1); 220 mpz_init (maxc1); 221 /* Setup range information for varc1. */ 222 if (integer_zerop (varc1)) 223 { 224 wi::to_mpz (0, minc1, TYPE_SIGN (type)); 225 wi::to_mpz (0, maxc1, TYPE_SIGN (type)); 226 } 227 else if (TREE_CODE (varc1) == SSA_NAME 228 && INTEGRAL_TYPE_P (type) 229 && get_range_info (varc1, &minv, &maxv) == VR_RANGE) 230 { 231 gcc_assert (wi::le_p (minv, maxv, sgn)); 232 wi::to_mpz (minv, minc1, sgn); 233 wi::to_mpz (maxv, maxc1, sgn); 234 } 235 else 236 { 237 mpz_set (minc1, mint); 238 mpz_set (maxc1, maxt); 239 } 240 241 /* Compute valid range information for varc1 + offc1. Note nothing 242 useful can be derived if it overflows or underflows. Overflow or 243 underflow could happen when: 244 245 offc1 > 0 && varc1 + offc1 > MAX_VAL (type) 246 offc1 < 0 && varc1 + offc1 < MIN_VAL (type). */ 247 mpz_add (minc1, minc1, offc1); 248 mpz_add (maxc1, maxc1, offc1); 249 c1_ok = (no_wrap 250 || mpz_sgn (offc1) == 0 251 || (mpz_sgn (offc1) < 0 && mpz_cmp (minc1, mint) >= 0) 252 || (mpz_sgn (offc1) > 0 && mpz_cmp (maxc1, maxt) <= 0)); 253 if (!c1_ok) 254 goto end; 255 256 if (mpz_cmp (minc1, mint) < 0) 257 mpz_set (minc1, mint); 258 if (mpz_cmp (maxc1, maxt) > 0) 259 mpz_set (maxc1, maxt); 260 261 if (cmp == LT_EXPR) 262 { 263 cmp = LE_EXPR; 264 mpz_sub_ui (maxc1, maxc1, 1); 265 } 266 if (cmp == GT_EXPR) 267 { 268 cmp = GE_EXPR; 269 mpz_add_ui (minc1, minc1, 1); 270 } 271 272 /* Compute range information for varc0. If there is no overflow, 273 the condition implied that 274 275 (varc0) cmp (varc1 + offc1 - offc0) 276 277 We can possibly improve the upper bound of varc0 if cmp is LE_EXPR, 278 or the below bound if cmp is GE_EXPR. 279 280 To prove there is no overflow/underflow, we need to check below 281 four cases: 282 1) cmp == LE_EXPR && offc0 > 0 283 284 (varc0 + offc0) doesn't overflow 285 && (varc1 + offc1 - offc0) doesn't underflow 286 287 2) cmp == LE_EXPR && offc0 < 0 288 289 (varc0 + offc0) doesn't underflow 290 && (varc1 + offc1 - offc0) doesn't overfloe 291 292 In this case, (varc0 + offc0) will never underflow if we can 293 prove (varc1 + offc1 - offc0) doesn't overflow. 294 295 3) cmp == GE_EXPR && offc0 < 0 296 297 (varc0 + offc0) doesn't underflow 298 && (varc1 + offc1 - offc0) doesn't overflow 299 300 4) cmp == GE_EXPR && offc0 > 0 301 302 (varc0 + offc0) doesn't overflow 303 && (varc1 + offc1 - offc0) doesn't underflow 304 305 In this case, (varc0 + offc0) will never overflow if we can 306 prove (varc1 + offc1 - offc0) doesn't underflow. 307 308 Note we only handle case 2 and 4 in below code. */ 309 310 mpz_sub (minc1, minc1, offc0); 311 mpz_sub (maxc1, maxc1, offc0); 312 c0_ok = (no_wrap 313 || mpz_sgn (offc0) == 0 314 || (cmp == LE_EXPR 315 && mpz_sgn (offc0) < 0 && mpz_cmp (maxc1, maxt) <= 0) 316 || (cmp == GE_EXPR 317 && mpz_sgn (offc0) > 0 && mpz_cmp (minc1, mint) >= 0)); 318 if (!c0_ok) 319 goto end; 320 321 if (cmp == LE_EXPR) 322 { 323 if (mpz_cmp (up, maxc1) > 0) 324 mpz_set (up, maxc1); 325 } 326 else 327 { 328 if (mpz_cmp (below, minc1) < 0) 329 mpz_set (below, minc1); 330 } 331 332 end: 333 mpz_clear (mint); 334 mpz_clear (maxt); 335 mpz_clear (minc1); 336 mpz_clear (maxc1); 337 mpz_clear (offc0); 338 mpz_clear (offc1); 339 } 340 341 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF 342 in TYPE to MIN and MAX. */ 343 344 static void 345 determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, 346 mpz_t min, mpz_t max) 347 { 348 int cnt = 0; 349 mpz_t minm, maxm; 350 basic_block bb; 351 wide_int minv, maxv; 352 enum value_range_type rtype = VR_VARYING; 353 354 /* If the expression is a constant, we know its value exactly. */ 355 if (integer_zerop (var)) 356 { 357 mpz_set (min, off); 358 mpz_set (max, off); 359 return; 360 } 361 362 get_type_static_bounds (type, min, max); 363 364 /* See if we have some range info from VRP. */ 365 if (TREE_CODE (var) == SSA_NAME && INTEGRAL_TYPE_P (type)) 366 { 367 edge e = loop_preheader_edge (loop); 368 signop sgn = TYPE_SIGN (type); 369 gphi_iterator gsi; 370 371 /* Either for VAR itself... */ 372 rtype = get_range_info (var, &minv, &maxv); 373 /* Or for PHI results in loop->header where VAR is used as 374 PHI argument from the loop preheader edge. */ 375 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi)) 376 { 377 gphi *phi = gsi.phi (); 378 wide_int minc, maxc; 379 if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var 380 && (get_range_info (gimple_phi_result (phi), &minc, &maxc) 381 == VR_RANGE)) 382 { 383 if (rtype != VR_RANGE) 384 { 385 rtype = VR_RANGE; 386 minv = minc; 387 maxv = maxc; 388 } 389 else 390 { 391 minv = wi::max (minv, minc, sgn); 392 maxv = wi::min (maxv, maxc, sgn); 393 /* If the PHI result range are inconsistent with 394 the VAR range, give up on looking at the PHI 395 results. This can happen if VR_UNDEFINED is 396 involved. */ 397 if (wi::gt_p (minv, maxv, sgn)) 398 { 399 rtype = get_range_info (var, &minv, &maxv); 400 break; 401 } 402 } 403 } 404 } 405 mpz_init (minm); 406 mpz_init (maxm); 407 if (rtype != VR_RANGE) 408 { 409 mpz_set (minm, min); 410 mpz_set (maxm, max); 411 } 412 else 413 { 414 gcc_assert (wi::le_p (minv, maxv, sgn)); 415 wi::to_mpz (minv, minm, sgn); 416 wi::to_mpz (maxv, maxm, sgn); 417 } 418 /* Now walk the dominators of the loop header and use the entry 419 guards to refine the estimates. */ 420 for (bb = loop->header; 421 bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK; 422 bb = get_immediate_dominator (CDI_DOMINATORS, bb)) 423 { 424 edge e; 425 tree c0, c1; 426 gimple *cond; 427 enum tree_code cmp; 428 429 if (!single_pred_p (bb)) 430 continue; 431 e = single_pred_edge (bb); 432 433 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) 434 continue; 435 436 cond = last_stmt (e->src); 437 c0 = gimple_cond_lhs (cond); 438 cmp = gimple_cond_code (cond); 439 c1 = gimple_cond_rhs (cond); 440 441 if (e->flags & EDGE_FALSE_VALUE) 442 cmp = invert_tree_comparison (cmp, false); 443 444 refine_value_range_using_guard (type, var, c0, cmp, c1, minm, maxm); 445 ++cnt; 446 } 447 448 mpz_add (minm, minm, off); 449 mpz_add (maxm, maxm, off); 450 /* If the computation may not wrap or off is zero, then this 451 is always fine. If off is negative and minv + off isn't 452 smaller than type's minimum, or off is positive and 453 maxv + off isn't bigger than type's maximum, use the more 454 precise range too. */ 455 if (nowrap_type_p (type) 456 || mpz_sgn (off) == 0 457 || (mpz_sgn (off) < 0 && mpz_cmp (minm, min) >= 0) 458 || (mpz_sgn (off) > 0 && mpz_cmp (maxm, max) <= 0)) 459 { 460 mpz_set (min, minm); 461 mpz_set (max, maxm); 462 mpz_clear (minm); 463 mpz_clear (maxm); 464 return; 465 } 466 mpz_clear (minm); 467 mpz_clear (maxm); 468 } 469 470 /* If the computation may wrap, we know nothing about the value, except for 471 the range of the type. */ 472 if (!nowrap_type_p (type)) 473 return; 474 475 /* Since the addition of OFF does not wrap, if OFF is positive, then we may 476 add it to MIN, otherwise to MAX. */ 477 if (mpz_sgn (off) < 0) 478 mpz_add (max, max, off); 479 else 480 mpz_add (min, min, off); 481 } 482 483 /* Stores the bounds on the difference of the values of the expressions 484 (var + X) and (var + Y), computed in TYPE, to BNDS. */ 485 486 static void 487 bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y, 488 bounds *bnds) 489 { 490 int rel = mpz_cmp (x, y); 491 bool may_wrap = !nowrap_type_p (type); 492 mpz_t m; 493 494 /* If X == Y, then the expressions are always equal. 495 If X > Y, there are the following possibilities: 496 a) neither of var + X and var + Y overflow or underflow, or both of 497 them do. Then their difference is X - Y. 498 b) var + X overflows, and var + Y does not. Then the values of the 499 expressions are var + X - M and var + Y, where M is the range of 500 the type, and their difference is X - Y - M. 501 c) var + Y underflows and var + X does not. Their difference again 502 is M - X + Y. 503 Therefore, if the arithmetics in type does not overflow, then the 504 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y) 505 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or 506 (X - Y, X - Y + M). */ 507 508 if (rel == 0) 509 { 510 mpz_set_ui (bnds->below, 0); 511 mpz_set_ui (bnds->up, 0); 512 return; 513 } 514 515 mpz_init (m); 516 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), m, UNSIGNED); 517 mpz_add_ui (m, m, 1); 518 mpz_sub (bnds->up, x, y); 519 mpz_set (bnds->below, bnds->up); 520 521 if (may_wrap) 522 { 523 if (rel > 0) 524 mpz_sub (bnds->below, bnds->below, m); 525 else 526 mpz_add (bnds->up, bnds->up, m); 527 } 528 529 mpz_clear (m); 530 } 531 532 /* From condition C0 CMP C1 derives information regarding the 533 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE, 534 and stores it to BNDS. */ 535 536 static void 537 refine_bounds_using_guard (tree type, tree varx, mpz_t offx, 538 tree vary, mpz_t offy, 539 tree c0, enum tree_code cmp, tree c1, 540 bounds *bnds) 541 { 542 tree varc0, varc1, ctype; 543 mpz_t offc0, offc1, loffx, loffy, bnd; 544 bool lbound = false; 545 bool no_wrap = nowrap_type_p (type); 546 bool x_ok, y_ok; 547 548 switch (cmp) 549 { 550 case LT_EXPR: 551 case LE_EXPR: 552 case GT_EXPR: 553 case GE_EXPR: 554 STRIP_SIGN_NOPS (c0); 555 STRIP_SIGN_NOPS (c1); 556 ctype = TREE_TYPE (c0); 557 if (!useless_type_conversion_p (ctype, type)) 558 return; 559 560 break; 561 562 case EQ_EXPR: 563 /* We could derive quite precise information from EQ_EXPR, however, such 564 a guard is unlikely to appear, so we do not bother with handling 565 it. */ 566 return; 567 568 case NE_EXPR: 569 /* NE_EXPR comparisons do not contain much of useful information, except for 570 special case of comparing with the bounds of the type. */ 571 if (TREE_CODE (c1) != INTEGER_CST 572 || !INTEGRAL_TYPE_P (type)) 573 return; 574 575 /* Ensure that the condition speaks about an expression in the same type 576 as X and Y. */ 577 ctype = TREE_TYPE (c0); 578 if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type)) 579 return; 580 c0 = fold_convert (type, c0); 581 c1 = fold_convert (type, c1); 582 583 if (TYPE_MIN_VALUE (type) 584 && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0)) 585 { 586 cmp = GT_EXPR; 587 break; 588 } 589 if (TYPE_MAX_VALUE (type) 590 && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0)) 591 { 592 cmp = LT_EXPR; 593 break; 594 } 595 596 return; 597 default: 598 return; 599 } 600 601 mpz_init (offc0); 602 mpz_init (offc1); 603 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0); 604 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1); 605 606 /* We are only interested in comparisons of expressions based on VARX and 607 VARY. TODO -- we might also be able to derive some bounds from 608 expressions containing just one of the variables. */ 609 610 if (operand_equal_p (varx, varc1, 0)) 611 { 612 std::swap (varc0, varc1); 613 mpz_swap (offc0, offc1); 614 cmp = swap_tree_comparison (cmp); 615 } 616 617 if (!operand_equal_p (varx, varc0, 0) 618 || !operand_equal_p (vary, varc1, 0)) 619 goto end; 620 621 mpz_init_set (loffx, offx); 622 mpz_init_set (loffy, offy); 623 624 if (cmp == GT_EXPR || cmp == GE_EXPR) 625 { 626 std::swap (varx, vary); 627 mpz_swap (offc0, offc1); 628 mpz_swap (loffx, loffy); 629 cmp = swap_tree_comparison (cmp); 630 lbound = true; 631 } 632 633 /* If there is no overflow, the condition implies that 634 635 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0). 636 637 The overflows and underflows may complicate things a bit; each 638 overflow decreases the appropriate offset by M, and underflow 639 increases it by M. The above inequality would not necessarily be 640 true if 641 642 -- VARX + OFFX underflows and VARX + OFFC0 does not, or 643 VARX + OFFC0 overflows, but VARX + OFFX does not. 644 This may only happen if OFFX < OFFC0. 645 -- VARY + OFFY overflows and VARY + OFFC1 does not, or 646 VARY + OFFC1 underflows and VARY + OFFY does not. 647 This may only happen if OFFY > OFFC1. */ 648 649 if (no_wrap) 650 { 651 x_ok = true; 652 y_ok = true; 653 } 654 else 655 { 656 x_ok = (integer_zerop (varx) 657 || mpz_cmp (loffx, offc0) >= 0); 658 y_ok = (integer_zerop (vary) 659 || mpz_cmp (loffy, offc1) <= 0); 660 } 661 662 if (x_ok && y_ok) 663 { 664 mpz_init (bnd); 665 mpz_sub (bnd, loffx, loffy); 666 mpz_add (bnd, bnd, offc1); 667 mpz_sub (bnd, bnd, offc0); 668 669 if (cmp == LT_EXPR) 670 mpz_sub_ui (bnd, bnd, 1); 671 672 if (lbound) 673 { 674 mpz_neg (bnd, bnd); 675 if (mpz_cmp (bnds->below, bnd) < 0) 676 mpz_set (bnds->below, bnd); 677 } 678 else 679 { 680 if (mpz_cmp (bnd, bnds->up) < 0) 681 mpz_set (bnds->up, bnd); 682 } 683 mpz_clear (bnd); 684 } 685 686 mpz_clear (loffx); 687 mpz_clear (loffy); 688 end: 689 mpz_clear (offc0); 690 mpz_clear (offc1); 691 } 692 693 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS. 694 The subtraction is considered to be performed in arbitrary precision, 695 without overflows. 696 697 We do not attempt to be too clever regarding the value ranges of X and 698 Y; most of the time, they are just integers or ssa names offsetted by 699 integer. However, we try to use the information contained in the 700 comparisons before the loop (usually created by loop header copying). */ 701 702 static void 703 bound_difference (struct loop *loop, tree x, tree y, bounds *bnds) 704 { 705 tree type = TREE_TYPE (x); 706 tree varx, vary; 707 mpz_t offx, offy; 708 mpz_t minx, maxx, miny, maxy; 709 int cnt = 0; 710 edge e; 711 basic_block bb; 712 tree c0, c1; 713 gimple *cond; 714 enum tree_code cmp; 715 716 /* Get rid of unnecessary casts, but preserve the value of 717 the expressions. */ 718 STRIP_SIGN_NOPS (x); 719 STRIP_SIGN_NOPS (y); 720 721 mpz_init (bnds->below); 722 mpz_init (bnds->up); 723 mpz_init (offx); 724 mpz_init (offy); 725 split_to_var_and_offset (x, &varx, offx); 726 split_to_var_and_offset (y, &vary, offy); 727 728 if (!integer_zerop (varx) 729 && operand_equal_p (varx, vary, 0)) 730 { 731 /* Special case VARX == VARY -- we just need to compare the 732 offsets. The matters are a bit more complicated in the 733 case addition of offsets may wrap. */ 734 bound_difference_of_offsetted_base (type, offx, offy, bnds); 735 } 736 else 737 { 738 /* Otherwise, use the value ranges to determine the initial 739 estimates on below and up. */ 740 mpz_init (minx); 741 mpz_init (maxx); 742 mpz_init (miny); 743 mpz_init (maxy); 744 determine_value_range (loop, type, varx, offx, minx, maxx); 745 determine_value_range (loop, type, vary, offy, miny, maxy); 746 747 mpz_sub (bnds->below, minx, maxy); 748 mpz_sub (bnds->up, maxx, miny); 749 mpz_clear (minx); 750 mpz_clear (maxx); 751 mpz_clear (miny); 752 mpz_clear (maxy); 753 } 754 755 /* If both X and Y are constants, we cannot get any more precise. */ 756 if (integer_zerop (varx) && integer_zerop (vary)) 757 goto end; 758 759 /* Now walk the dominators of the loop header and use the entry 760 guards to refine the estimates. */ 761 for (bb = loop->header; 762 bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK; 763 bb = get_immediate_dominator (CDI_DOMINATORS, bb)) 764 { 765 if (!single_pred_p (bb)) 766 continue; 767 e = single_pred_edge (bb); 768 769 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) 770 continue; 771 772 cond = last_stmt (e->src); 773 c0 = gimple_cond_lhs (cond); 774 cmp = gimple_cond_code (cond); 775 c1 = gimple_cond_rhs (cond); 776 777 if (e->flags & EDGE_FALSE_VALUE) 778 cmp = invert_tree_comparison (cmp, false); 779 780 refine_bounds_using_guard (type, varx, offx, vary, offy, 781 c0, cmp, c1, bnds); 782 ++cnt; 783 } 784 785 end: 786 mpz_clear (offx); 787 mpz_clear (offy); 788 } 789 790 /* Update the bounds in BNDS that restrict the value of X to the bounds 791 that restrict the value of X + DELTA. X can be obtained as a 792 difference of two values in TYPE. */ 793 794 static void 795 bounds_add (bounds *bnds, const widest_int &delta, tree type) 796 { 797 mpz_t mdelta, max; 798 799 mpz_init (mdelta); 800 wi::to_mpz (delta, mdelta, SIGNED); 801 802 mpz_init (max); 803 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), max, UNSIGNED); 804 805 mpz_add (bnds->up, bnds->up, mdelta); 806 mpz_add (bnds->below, bnds->below, mdelta); 807 808 if (mpz_cmp (bnds->up, max) > 0) 809 mpz_set (bnds->up, max); 810 811 mpz_neg (max, max); 812 if (mpz_cmp (bnds->below, max) < 0) 813 mpz_set (bnds->below, max); 814 815 mpz_clear (mdelta); 816 mpz_clear (max); 817 } 818 819 /* Update the bounds in BNDS that restrict the value of X to the bounds 820 that restrict the value of -X. */ 821 822 static void 823 bounds_negate (bounds *bnds) 824 { 825 mpz_t tmp; 826 827 mpz_init_set (tmp, bnds->up); 828 mpz_neg (bnds->up, bnds->below); 829 mpz_neg (bnds->below, tmp); 830 mpz_clear (tmp); 831 } 832 833 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */ 834 835 static tree 836 inverse (tree x, tree mask) 837 { 838 tree type = TREE_TYPE (x); 839 tree rslt; 840 unsigned ctr = tree_floor_log2 (mask); 841 842 if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT) 843 { 844 unsigned HOST_WIDE_INT ix; 845 unsigned HOST_WIDE_INT imask; 846 unsigned HOST_WIDE_INT irslt = 1; 847 848 gcc_assert (cst_and_fits_in_hwi (x)); 849 gcc_assert (cst_and_fits_in_hwi (mask)); 850 851 ix = int_cst_value (x); 852 imask = int_cst_value (mask); 853 854 for (; ctr; ctr--) 855 { 856 irslt *= ix; 857 ix *= ix; 858 } 859 irslt &= imask; 860 861 rslt = build_int_cst_type (type, irslt); 862 } 863 else 864 { 865 rslt = build_int_cst (type, 1); 866 for (; ctr; ctr--) 867 { 868 rslt = int_const_binop (MULT_EXPR, rslt, x); 869 x = int_const_binop (MULT_EXPR, x, x); 870 } 871 rslt = int_const_binop (BIT_AND_EXPR, rslt, mask); 872 } 873 874 return rslt; 875 } 876 877 /* Derives the upper bound BND on the number of executions of loop with exit 878 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of 879 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed 880 that the loop ends through this exit, i.e., the induction variable ever 881 reaches the value of C. 882 883 The value C is equal to final - base, where final and base are the final and 884 initial value of the actual induction variable in the analysed loop. BNDS 885 bounds the value of this difference when computed in signed type with 886 unbounded range, while the computation of C is performed in an unsigned 887 type with the range matching the range of the type of the induction variable. 888 In particular, BNDS.up contains an upper bound on C in the following cases: 889 -- if the iv must reach its final value without overflow, i.e., if 890 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or 891 -- if final >= base, which we know to hold when BNDS.below >= 0. */ 892 893 static void 894 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s, 895 bounds *bnds, bool exit_must_be_taken) 896 { 897 widest_int max; 898 mpz_t d; 899 tree type = TREE_TYPE (c); 900 bool bnds_u_valid = ((no_overflow && exit_must_be_taken) 901 || mpz_sgn (bnds->below) >= 0); 902 903 if (integer_onep (s) 904 || (TREE_CODE (c) == INTEGER_CST 905 && TREE_CODE (s) == INTEGER_CST 906 && wi::mod_trunc (wi::to_wide (c), wi::to_wide (s), 907 TYPE_SIGN (type)) == 0) 908 || (TYPE_OVERFLOW_UNDEFINED (type) 909 && multiple_of_p (type, c, s))) 910 { 911 /* If C is an exact multiple of S, then its value will be reached before 912 the induction variable overflows (unless the loop is exited in some 913 other way before). Note that the actual induction variable in the 914 loop (which ranges from base to final instead of from 0 to C) may 915 overflow, in which case BNDS.up will not be giving a correct upper 916 bound on C; thus, BNDS_U_VALID had to be computed in advance. */ 917 no_overflow = true; 918 exit_must_be_taken = true; 919 } 920 921 /* If the induction variable can overflow, the number of iterations is at 922 most the period of the control variable (or infinite, but in that case 923 the whole # of iterations analysis will fail). */ 924 if (!no_overflow) 925 { 926 max = wi::mask <widest_int> (TYPE_PRECISION (type) 927 - wi::ctz (wi::to_wide (s)), false); 928 wi::to_mpz (max, bnd, UNSIGNED); 929 return; 930 } 931 932 /* Now we know that the induction variable does not overflow, so the loop 933 iterates at most (range of type / S) times. */ 934 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), bnd, UNSIGNED); 935 936 /* If the induction variable is guaranteed to reach the value of C before 937 overflow, ... */ 938 if (exit_must_be_taken) 939 { 940 /* ... then we can strengthen this to C / S, and possibly we can use 941 the upper bound on C given by BNDS. */ 942 if (TREE_CODE (c) == INTEGER_CST) 943 wi::to_mpz (wi::to_wide (c), bnd, UNSIGNED); 944 else if (bnds_u_valid) 945 mpz_set (bnd, bnds->up); 946 } 947 948 mpz_init (d); 949 wi::to_mpz (wi::to_wide (s), d, UNSIGNED); 950 mpz_fdiv_q (bnd, bnd, d); 951 mpz_clear (d); 952 } 953 954 /* Determines number of iterations of loop whose ending condition 955 is IV <> FINAL. TYPE is the type of the iv. The number of 956 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if 957 we know that the exit must be taken eventually, i.e., that the IV 958 ever reaches the value FINAL (we derived this earlier, and possibly set 959 NITER->assumptions to make sure this is the case). BNDS contains the 960 bounds on the difference FINAL - IV->base. */ 961 962 static bool 963 number_of_iterations_ne (struct loop *loop, tree type, affine_iv *iv, 964 tree final, struct tree_niter_desc *niter, 965 bool exit_must_be_taken, bounds *bnds) 966 { 967 tree niter_type = unsigned_type_for (type); 968 tree s, c, d, bits, assumption, tmp, bound; 969 mpz_t max; 970 971 niter->control = *iv; 972 niter->bound = final; 973 niter->cmp = NE_EXPR; 974 975 /* Rearrange the terms so that we get inequality S * i <> C, with S 976 positive. Also cast everything to the unsigned type. If IV does 977 not overflow, BNDS bounds the value of C. Also, this is the 978 case if the computation |FINAL - IV->base| does not overflow, i.e., 979 if BNDS->below in the result is nonnegative. */ 980 if (tree_int_cst_sign_bit (iv->step)) 981 { 982 s = fold_convert (niter_type, 983 fold_build1 (NEGATE_EXPR, type, iv->step)); 984 c = fold_build2 (MINUS_EXPR, niter_type, 985 fold_convert (niter_type, iv->base), 986 fold_convert (niter_type, final)); 987 bounds_negate (bnds); 988 } 989 else 990 { 991 s = fold_convert (niter_type, iv->step); 992 c = fold_build2 (MINUS_EXPR, niter_type, 993 fold_convert (niter_type, final), 994 fold_convert (niter_type, iv->base)); 995 } 996 997 mpz_init (max); 998 number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds, 999 exit_must_be_taken); 1000 niter->max = widest_int::from (wi::from_mpz (niter_type, max, false), 1001 TYPE_SIGN (niter_type)); 1002 mpz_clear (max); 1003 1004 /* Compute no-overflow information for the control iv. This can be 1005 proven when below two conditions are satisfied: 1006 1007 1) IV evaluates toward FINAL at beginning, i.e: 1008 base <= FINAL ; step > 0 1009 base >= FINAL ; step < 0 1010 1011 2) |FINAL - base| is an exact multiple of step. 1012 1013 Unfortunately, it's hard to prove above conditions after pass loop-ch 1014 because loop with exit condition (IV != FINAL) usually will be guarded 1015 by initial-condition (IV.base - IV.step != FINAL). In this case, we 1016 can alternatively try to prove below conditions: 1017 1018 1') IV evaluates toward FINAL at beginning, i.e: 1019 new_base = base - step < FINAL ; step > 0 1020 && base - step doesn't underflow 1021 new_base = base - step > FINAL ; step < 0 1022 && base - step doesn't overflow 1023 1024 2') |FINAL - new_base| is an exact multiple of step. 1025 1026 Please refer to PR34114 as an example of loop-ch's impact, also refer 1027 to PR72817 as an example why condition 2') is necessary. 1028 1029 Note, for NE_EXPR, base equals to FINAL is a special case, in 1030 which the loop exits immediately, and the iv does not overflow. */ 1031 if (!niter->control.no_overflow 1032 && (integer_onep (s) || multiple_of_p (type, c, s))) 1033 { 1034 tree t, cond, new_c, relaxed_cond = boolean_false_node; 1035 1036 if (tree_int_cst_sign_bit (iv->step)) 1037 { 1038 cond = fold_build2 (GE_EXPR, boolean_type_node, iv->base, final); 1039 if (TREE_CODE (type) == INTEGER_TYPE) 1040 { 1041 /* Only when base - step doesn't overflow. */ 1042 t = TYPE_MAX_VALUE (type); 1043 t = fold_build2 (PLUS_EXPR, type, t, iv->step); 1044 t = fold_build2 (GE_EXPR, boolean_type_node, t, iv->base); 1045 if (integer_nonzerop (t)) 1046 { 1047 t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step); 1048 new_c = fold_build2 (MINUS_EXPR, niter_type, 1049 fold_convert (niter_type, t), 1050 fold_convert (niter_type, final)); 1051 if (multiple_of_p (type, new_c, s)) 1052 relaxed_cond = fold_build2 (GT_EXPR, boolean_type_node, 1053 t, final); 1054 } 1055 } 1056 } 1057 else 1058 { 1059 cond = fold_build2 (LE_EXPR, boolean_type_node, iv->base, final); 1060 if (TREE_CODE (type) == INTEGER_TYPE) 1061 { 1062 /* Only when base - step doesn't underflow. */ 1063 t = TYPE_MIN_VALUE (type); 1064 t = fold_build2 (PLUS_EXPR, type, t, iv->step); 1065 t = fold_build2 (LE_EXPR, boolean_type_node, t, iv->base); 1066 if (integer_nonzerop (t)) 1067 { 1068 t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step); 1069 new_c = fold_build2 (MINUS_EXPR, niter_type, 1070 fold_convert (niter_type, final), 1071 fold_convert (niter_type, t)); 1072 if (multiple_of_p (type, new_c, s)) 1073 relaxed_cond = fold_build2 (LT_EXPR, boolean_type_node, 1074 t, final); 1075 } 1076 } 1077 } 1078 1079 t = simplify_using_initial_conditions (loop, cond); 1080 if (!t || !integer_onep (t)) 1081 t = simplify_using_initial_conditions (loop, relaxed_cond); 1082 1083 if (t && integer_onep (t)) 1084 niter->control.no_overflow = true; 1085 } 1086 1087 /* First the trivial cases -- when the step is 1. */ 1088 if (integer_onep (s)) 1089 { 1090 niter->niter = c; 1091 return true; 1092 } 1093 if (niter->control.no_overflow && multiple_of_p (type, c, s)) 1094 { 1095 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, c, s); 1096 return true; 1097 } 1098 1099 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop 1100 is infinite. Otherwise, the number of iterations is 1101 (inverse(s/d) * (c/d)) mod (size of mode/d). */ 1102 bits = num_ending_zeros (s); 1103 bound = build_low_bits_mask (niter_type, 1104 (TYPE_PRECISION (niter_type) 1105 - tree_to_uhwi (bits))); 1106 1107 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type, 1108 build_int_cst (niter_type, 1), bits); 1109 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits); 1110 1111 if (!exit_must_be_taken) 1112 { 1113 /* If we cannot assume that the exit is taken eventually, record the 1114 assumptions for divisibility of c. */ 1115 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d); 1116 assumption = fold_build2 (EQ_EXPR, boolean_type_node, 1117 assumption, build_int_cst (niter_type, 0)); 1118 if (!integer_nonzerop (assumption)) 1119 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 1120 niter->assumptions, assumption); 1121 } 1122 1123 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d); 1124 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound)); 1125 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound); 1126 return true; 1127 } 1128 1129 /* Checks whether we can determine the final value of the control variable 1130 of the loop with ending condition IV0 < IV1 (computed in TYPE). 1131 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value 1132 of the step. The assumptions necessary to ensure that the computation 1133 of the final value does not overflow are recorded in NITER. If we 1134 find the final value, we adjust DELTA and return TRUE. Otherwise 1135 we return false. BNDS bounds the value of IV1->base - IV0->base, 1136 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is 1137 true if we know that the exit must be taken eventually. */ 1138 1139 static bool 1140 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1, 1141 struct tree_niter_desc *niter, 1142 tree *delta, tree step, 1143 bool exit_must_be_taken, bounds *bnds) 1144 { 1145 tree niter_type = TREE_TYPE (step); 1146 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step); 1147 tree tmod; 1148 mpz_t mmod; 1149 tree assumption = boolean_true_node, bound, noloop; 1150 bool ret = false, fv_comp_no_overflow; 1151 tree type1 = type; 1152 if (POINTER_TYPE_P (type)) 1153 type1 = sizetype; 1154 1155 if (TREE_CODE (mod) != INTEGER_CST) 1156 return false; 1157 if (integer_nonzerop (mod)) 1158 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod); 1159 tmod = fold_convert (type1, mod); 1160 1161 mpz_init (mmod); 1162 wi::to_mpz (wi::to_wide (mod), mmod, UNSIGNED); 1163 mpz_neg (mmod, mmod); 1164 1165 /* If the induction variable does not overflow and the exit is taken, 1166 then the computation of the final value does not overflow. This is 1167 also obviously the case if the new final value is equal to the 1168 current one. Finally, we postulate this for pointer type variables, 1169 as the code cannot rely on the object to that the pointer points being 1170 placed at the end of the address space (and more pragmatically, 1171 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */ 1172 if (integer_zerop (mod) || POINTER_TYPE_P (type)) 1173 fv_comp_no_overflow = true; 1174 else if (!exit_must_be_taken) 1175 fv_comp_no_overflow = false; 1176 else 1177 fv_comp_no_overflow = 1178 (iv0->no_overflow && integer_nonzerop (iv0->step)) 1179 || (iv1->no_overflow && integer_nonzerop (iv1->step)); 1180 1181 if (integer_nonzerop (iv0->step)) 1182 { 1183 /* The final value of the iv is iv1->base + MOD, assuming that this 1184 computation does not overflow, and that 1185 iv0->base <= iv1->base + MOD. */ 1186 if (!fv_comp_no_overflow) 1187 { 1188 bound = fold_build2 (MINUS_EXPR, type1, 1189 TYPE_MAX_VALUE (type1), tmod); 1190 assumption = fold_build2 (LE_EXPR, boolean_type_node, 1191 iv1->base, bound); 1192 if (integer_zerop (assumption)) 1193 goto end; 1194 } 1195 if (mpz_cmp (mmod, bnds->below) < 0) 1196 noloop = boolean_false_node; 1197 else if (POINTER_TYPE_P (type)) 1198 noloop = fold_build2 (GT_EXPR, boolean_type_node, 1199 iv0->base, 1200 fold_build_pointer_plus (iv1->base, tmod)); 1201 else 1202 noloop = fold_build2 (GT_EXPR, boolean_type_node, 1203 iv0->base, 1204 fold_build2 (PLUS_EXPR, type1, 1205 iv1->base, tmod)); 1206 } 1207 else 1208 { 1209 /* The final value of the iv is iv0->base - MOD, assuming that this 1210 computation does not overflow, and that 1211 iv0->base - MOD <= iv1->base. */ 1212 if (!fv_comp_no_overflow) 1213 { 1214 bound = fold_build2 (PLUS_EXPR, type1, 1215 TYPE_MIN_VALUE (type1), tmod); 1216 assumption = fold_build2 (GE_EXPR, boolean_type_node, 1217 iv0->base, bound); 1218 if (integer_zerop (assumption)) 1219 goto end; 1220 } 1221 if (mpz_cmp (mmod, bnds->below) < 0) 1222 noloop = boolean_false_node; 1223 else if (POINTER_TYPE_P (type)) 1224 noloop = fold_build2 (GT_EXPR, boolean_type_node, 1225 fold_build_pointer_plus (iv0->base, 1226 fold_build1 (NEGATE_EXPR, 1227 type1, tmod)), 1228 iv1->base); 1229 else 1230 noloop = fold_build2 (GT_EXPR, boolean_type_node, 1231 fold_build2 (MINUS_EXPR, type1, 1232 iv0->base, tmod), 1233 iv1->base); 1234 } 1235 1236 if (!integer_nonzerop (assumption)) 1237 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 1238 niter->assumptions, 1239 assumption); 1240 if (!integer_zerop (noloop)) 1241 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, 1242 niter->may_be_zero, 1243 noloop); 1244 bounds_add (bnds, wi::to_widest (mod), type); 1245 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod); 1246 1247 ret = true; 1248 end: 1249 mpz_clear (mmod); 1250 return ret; 1251 } 1252 1253 /* Add assertions to NITER that ensure that the control variable of the loop 1254 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1 1255 are TYPE. Returns false if we can prove that there is an overflow, true 1256 otherwise. STEP is the absolute value of the step. */ 1257 1258 static bool 1259 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1, 1260 struct tree_niter_desc *niter, tree step) 1261 { 1262 tree bound, d, assumption, diff; 1263 tree niter_type = TREE_TYPE (step); 1264 1265 if (integer_nonzerop (iv0->step)) 1266 { 1267 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */ 1268 if (iv0->no_overflow) 1269 return true; 1270 1271 /* If iv0->base is a constant, we can determine the last value before 1272 overflow precisely; otherwise we conservatively assume 1273 MAX - STEP + 1. */ 1274 1275 if (TREE_CODE (iv0->base) == INTEGER_CST) 1276 { 1277 d = fold_build2 (MINUS_EXPR, niter_type, 1278 fold_convert (niter_type, TYPE_MAX_VALUE (type)), 1279 fold_convert (niter_type, iv0->base)); 1280 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step); 1281 } 1282 else 1283 diff = fold_build2 (MINUS_EXPR, niter_type, step, 1284 build_int_cst (niter_type, 1)); 1285 bound = fold_build2 (MINUS_EXPR, type, 1286 TYPE_MAX_VALUE (type), fold_convert (type, diff)); 1287 assumption = fold_build2 (LE_EXPR, boolean_type_node, 1288 iv1->base, bound); 1289 } 1290 else 1291 { 1292 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */ 1293 if (iv1->no_overflow) 1294 return true; 1295 1296 if (TREE_CODE (iv1->base) == INTEGER_CST) 1297 { 1298 d = fold_build2 (MINUS_EXPR, niter_type, 1299 fold_convert (niter_type, iv1->base), 1300 fold_convert (niter_type, TYPE_MIN_VALUE (type))); 1301 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step); 1302 } 1303 else 1304 diff = fold_build2 (MINUS_EXPR, niter_type, step, 1305 build_int_cst (niter_type, 1)); 1306 bound = fold_build2 (PLUS_EXPR, type, 1307 TYPE_MIN_VALUE (type), fold_convert (type, diff)); 1308 assumption = fold_build2 (GE_EXPR, boolean_type_node, 1309 iv0->base, bound); 1310 } 1311 1312 if (integer_zerop (assumption)) 1313 return false; 1314 if (!integer_nonzerop (assumption)) 1315 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 1316 niter->assumptions, assumption); 1317 1318 iv0->no_overflow = true; 1319 iv1->no_overflow = true; 1320 return true; 1321 } 1322 1323 /* Add an assumption to NITER that a loop whose ending condition 1324 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS 1325 bounds the value of IV1->base - IV0->base. */ 1326 1327 static void 1328 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1, 1329 struct tree_niter_desc *niter, bounds *bnds) 1330 { 1331 tree assumption = boolean_true_node, bound, diff; 1332 tree mbz, mbzl, mbzr, type1; 1333 bool rolls_p, no_overflow_p; 1334 widest_int dstep; 1335 mpz_t mstep, max; 1336 1337 /* We are going to compute the number of iterations as 1338 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned 1339 variant of TYPE. This formula only works if 1340 1341 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1 1342 1343 (where MAX is the maximum value of the unsigned variant of TYPE, and 1344 the computations in this formula are performed in full precision, 1345 i.e., without overflows). 1346 1347 Usually, for loops with exit condition iv0->base + step * i < iv1->base, 1348 we have a condition of the form iv0->base - step < iv1->base before the loop, 1349 and for loops iv0->base < iv1->base - step * i the condition 1350 iv0->base < iv1->base + step, due to loop header copying, which enable us 1351 to prove the lower bound. 1352 1353 The upper bound is more complicated. Unless the expressions for initial 1354 and final value themselves contain enough information, we usually cannot 1355 derive it from the context. */ 1356 1357 /* First check whether the answer does not follow from the bounds we gathered 1358 before. */ 1359 if (integer_nonzerop (iv0->step)) 1360 dstep = wi::to_widest (iv0->step); 1361 else 1362 { 1363 dstep = wi::sext (wi::to_widest (iv1->step), TYPE_PRECISION (type)); 1364 dstep = -dstep; 1365 } 1366 1367 mpz_init (mstep); 1368 wi::to_mpz (dstep, mstep, UNSIGNED); 1369 mpz_neg (mstep, mstep); 1370 mpz_add_ui (mstep, mstep, 1); 1371 1372 rolls_p = mpz_cmp (mstep, bnds->below) <= 0; 1373 1374 mpz_init (max); 1375 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), max, UNSIGNED); 1376 mpz_add (max, max, mstep); 1377 no_overflow_p = (mpz_cmp (bnds->up, max) <= 0 1378 /* For pointers, only values lying inside a single object 1379 can be compared or manipulated by pointer arithmetics. 1380 Gcc in general does not allow or handle objects larger 1381 than half of the address space, hence the upper bound 1382 is satisfied for pointers. */ 1383 || POINTER_TYPE_P (type)); 1384 mpz_clear (mstep); 1385 mpz_clear (max); 1386 1387 if (rolls_p && no_overflow_p) 1388 return; 1389 1390 type1 = type; 1391 if (POINTER_TYPE_P (type)) 1392 type1 = sizetype; 1393 1394 /* Now the hard part; we must formulate the assumption(s) as expressions, and 1395 we must be careful not to introduce overflow. */ 1396 1397 if (integer_nonzerop (iv0->step)) 1398 { 1399 diff = fold_build2 (MINUS_EXPR, type1, 1400 iv0->step, build_int_cst (type1, 1)); 1401 1402 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since 1403 0 address never belongs to any object, we can assume this for 1404 pointers. */ 1405 if (!POINTER_TYPE_P (type)) 1406 { 1407 bound = fold_build2 (PLUS_EXPR, type1, 1408 TYPE_MIN_VALUE (type), diff); 1409 assumption = fold_build2 (GE_EXPR, boolean_type_node, 1410 iv0->base, bound); 1411 } 1412 1413 /* And then we can compute iv0->base - diff, and compare it with 1414 iv1->base. */ 1415 mbzl = fold_build2 (MINUS_EXPR, type1, 1416 fold_convert (type1, iv0->base), diff); 1417 mbzr = fold_convert (type1, iv1->base); 1418 } 1419 else 1420 { 1421 diff = fold_build2 (PLUS_EXPR, type1, 1422 iv1->step, build_int_cst (type1, 1)); 1423 1424 if (!POINTER_TYPE_P (type)) 1425 { 1426 bound = fold_build2 (PLUS_EXPR, type1, 1427 TYPE_MAX_VALUE (type), diff); 1428 assumption = fold_build2 (LE_EXPR, boolean_type_node, 1429 iv1->base, bound); 1430 } 1431 1432 mbzl = fold_convert (type1, iv0->base); 1433 mbzr = fold_build2 (MINUS_EXPR, type1, 1434 fold_convert (type1, iv1->base), diff); 1435 } 1436 1437 if (!integer_nonzerop (assumption)) 1438 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 1439 niter->assumptions, assumption); 1440 if (!rolls_p) 1441 { 1442 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr); 1443 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, 1444 niter->may_be_zero, mbz); 1445 } 1446 } 1447 1448 /* Determines number of iterations of loop whose ending condition 1449 is IV0 < IV1. TYPE is the type of the iv. The number of 1450 iterations is stored to NITER. BNDS bounds the difference 1451 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know 1452 that the exit must be taken eventually. */ 1453 1454 static bool 1455 number_of_iterations_lt (struct loop *loop, tree type, affine_iv *iv0, 1456 affine_iv *iv1, struct tree_niter_desc *niter, 1457 bool exit_must_be_taken, bounds *bnds) 1458 { 1459 tree niter_type = unsigned_type_for (type); 1460 tree delta, step, s; 1461 mpz_t mstep, tmp; 1462 1463 if (integer_nonzerop (iv0->step)) 1464 { 1465 niter->control = *iv0; 1466 niter->cmp = LT_EXPR; 1467 niter->bound = iv1->base; 1468 } 1469 else 1470 { 1471 niter->control = *iv1; 1472 niter->cmp = GT_EXPR; 1473 niter->bound = iv0->base; 1474 } 1475 1476 delta = fold_build2 (MINUS_EXPR, niter_type, 1477 fold_convert (niter_type, iv1->base), 1478 fold_convert (niter_type, iv0->base)); 1479 1480 /* First handle the special case that the step is +-1. */ 1481 if ((integer_onep (iv0->step) && integer_zerop (iv1->step)) 1482 || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step))) 1483 { 1484 /* for (i = iv0->base; i < iv1->base; i++) 1485 1486 or 1487 1488 for (i = iv1->base; i > iv0->base; i--). 1489 1490 In both cases # of iterations is iv1->base - iv0->base, assuming that 1491 iv1->base >= iv0->base. 1492 1493 First try to derive a lower bound on the value of 1494 iv1->base - iv0->base, computed in full precision. If the difference 1495 is nonnegative, we are done, otherwise we must record the 1496 condition. */ 1497 1498 if (mpz_sgn (bnds->below) < 0) 1499 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node, 1500 iv1->base, iv0->base); 1501 niter->niter = delta; 1502 niter->max = widest_int::from (wi::from_mpz (niter_type, bnds->up, false), 1503 TYPE_SIGN (niter_type)); 1504 niter->control.no_overflow = true; 1505 return true; 1506 } 1507 1508 if (integer_nonzerop (iv0->step)) 1509 step = fold_convert (niter_type, iv0->step); 1510 else 1511 step = fold_convert (niter_type, 1512 fold_build1 (NEGATE_EXPR, type, iv1->step)); 1513 1514 /* If we can determine the final value of the control iv exactly, we can 1515 transform the condition to != comparison. In particular, this will be 1516 the case if DELTA is constant. */ 1517 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step, 1518 exit_must_be_taken, bnds)) 1519 { 1520 affine_iv zps; 1521 1522 zps.base = build_int_cst (niter_type, 0); 1523 zps.step = step; 1524 /* number_of_iterations_lt_to_ne will add assumptions that ensure that 1525 zps does not overflow. */ 1526 zps.no_overflow = true; 1527 1528 return number_of_iterations_ne (loop, type, &zps, 1529 delta, niter, true, bnds); 1530 } 1531 1532 /* Make sure that the control iv does not overflow. */ 1533 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step)) 1534 return false; 1535 1536 /* We determine the number of iterations as (delta + step - 1) / step. For 1537 this to work, we must know that iv1->base >= iv0->base - step + 1, 1538 otherwise the loop does not roll. */ 1539 assert_loop_rolls_lt (type, iv0, iv1, niter, bnds); 1540 1541 s = fold_build2 (MINUS_EXPR, niter_type, 1542 step, build_int_cst (niter_type, 1)); 1543 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s); 1544 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step); 1545 1546 mpz_init (mstep); 1547 mpz_init (tmp); 1548 wi::to_mpz (wi::to_wide (step), mstep, UNSIGNED); 1549 mpz_add (tmp, bnds->up, mstep); 1550 mpz_sub_ui (tmp, tmp, 1); 1551 mpz_fdiv_q (tmp, tmp, mstep); 1552 niter->max = widest_int::from (wi::from_mpz (niter_type, tmp, false), 1553 TYPE_SIGN (niter_type)); 1554 mpz_clear (mstep); 1555 mpz_clear (tmp); 1556 1557 return true; 1558 } 1559 1560 /* Determines number of iterations of loop whose ending condition 1561 is IV0 <= IV1. TYPE is the type of the iv. The number of 1562 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if 1563 we know that this condition must eventually become false (we derived this 1564 earlier, and possibly set NITER->assumptions to make sure this 1565 is the case). BNDS bounds the difference IV1->base - IV0->base. */ 1566 1567 static bool 1568 number_of_iterations_le (struct loop *loop, tree type, affine_iv *iv0, 1569 affine_iv *iv1, struct tree_niter_desc *niter, 1570 bool exit_must_be_taken, bounds *bnds) 1571 { 1572 tree assumption; 1573 tree type1 = type; 1574 if (POINTER_TYPE_P (type)) 1575 type1 = sizetype; 1576 1577 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff 1578 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest 1579 value of the type. This we must know anyway, since if it is 1580 equal to this value, the loop rolls forever. We do not check 1581 this condition for pointer type ivs, as the code cannot rely on 1582 the object to that the pointer points being placed at the end of 1583 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is 1584 not defined for pointers). */ 1585 1586 if (!exit_must_be_taken && !POINTER_TYPE_P (type)) 1587 { 1588 if (integer_nonzerop (iv0->step)) 1589 assumption = fold_build2 (NE_EXPR, boolean_type_node, 1590 iv1->base, TYPE_MAX_VALUE (type)); 1591 else 1592 assumption = fold_build2 (NE_EXPR, boolean_type_node, 1593 iv0->base, TYPE_MIN_VALUE (type)); 1594 1595 if (integer_zerop (assumption)) 1596 return false; 1597 if (!integer_nonzerop (assumption)) 1598 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 1599 niter->assumptions, assumption); 1600 } 1601 1602 if (integer_nonzerop (iv0->step)) 1603 { 1604 if (POINTER_TYPE_P (type)) 1605 iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1); 1606 else 1607 iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base, 1608 build_int_cst (type1, 1)); 1609 } 1610 else if (POINTER_TYPE_P (type)) 1611 iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1); 1612 else 1613 iv0->base = fold_build2 (MINUS_EXPR, type1, 1614 iv0->base, build_int_cst (type1, 1)); 1615 1616 bounds_add (bnds, 1, type1); 1617 1618 return number_of_iterations_lt (loop, type, iv0, iv1, niter, exit_must_be_taken, 1619 bnds); 1620 } 1621 1622 /* Dumps description of affine induction variable IV to FILE. */ 1623 1624 static void 1625 dump_affine_iv (FILE *file, affine_iv *iv) 1626 { 1627 if (!integer_zerop (iv->step)) 1628 fprintf (file, "["); 1629 1630 print_generic_expr (dump_file, iv->base, TDF_SLIM); 1631 1632 if (!integer_zerop (iv->step)) 1633 { 1634 fprintf (file, ", + , "); 1635 print_generic_expr (dump_file, iv->step, TDF_SLIM); 1636 fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : ""); 1637 } 1638 } 1639 1640 /* Determine the number of iterations according to condition (for staying 1641 inside loop) which compares two induction variables using comparison 1642 operator CODE. The induction variable on left side of the comparison 1643 is IV0, the right-hand side is IV1. Both induction variables must have 1644 type TYPE, which must be an integer or pointer type. The steps of the 1645 ivs must be constants (or NULL_TREE, which is interpreted as constant zero). 1646 1647 LOOP is the loop whose number of iterations we are determining. 1648 1649 ONLY_EXIT is true if we are sure this is the only way the loop could be 1650 exited (including possibly non-returning function calls, exceptions, etc.) 1651 -- in this case we can use the information whether the control induction 1652 variables can overflow or not in a more efficient way. 1653 1654 if EVERY_ITERATION is true, we know the test is executed on every iteration. 1655 1656 The results (number of iterations and assumptions as described in 1657 comments at struct tree_niter_desc in tree-ssa-loop.h) are stored to NITER. 1658 Returns false if it fails to determine number of iterations, true if it 1659 was determined (possibly with some assumptions). */ 1660 1661 static bool 1662 number_of_iterations_cond (struct loop *loop, 1663 tree type, affine_iv *iv0, enum tree_code code, 1664 affine_iv *iv1, struct tree_niter_desc *niter, 1665 bool only_exit, bool every_iteration) 1666 { 1667 bool exit_must_be_taken = false, ret; 1668 bounds bnds; 1669 1670 /* If the test is not executed every iteration, wrapping may make the test 1671 to pass again. 1672 TODO: the overflow case can be still used as unreliable estimate of upper 1673 bound. But we have no API to pass it down to number of iterations code 1674 and, at present, it will not use it anyway. */ 1675 if (!every_iteration 1676 && (!iv0->no_overflow || !iv1->no_overflow 1677 || code == NE_EXPR || code == EQ_EXPR)) 1678 return false; 1679 1680 /* The meaning of these assumptions is this: 1681 if !assumptions 1682 then the rest of information does not have to be valid 1683 if may_be_zero then the loop does not roll, even if 1684 niter != 0. */ 1685 niter->assumptions = boolean_true_node; 1686 niter->may_be_zero = boolean_false_node; 1687 niter->niter = NULL_TREE; 1688 niter->max = 0; 1689 niter->bound = NULL_TREE; 1690 niter->cmp = ERROR_MARK; 1691 1692 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that 1693 the control variable is on lhs. */ 1694 if (code == GE_EXPR || code == GT_EXPR 1695 || (code == NE_EXPR && integer_zerop (iv0->step))) 1696 { 1697 std::swap (iv0, iv1); 1698 code = swap_tree_comparison (code); 1699 } 1700 1701 if (POINTER_TYPE_P (type)) 1702 { 1703 /* Comparison of pointers is undefined unless both iv0 and iv1 point 1704 to the same object. If they do, the control variable cannot wrap 1705 (as wrap around the bounds of memory will never return a pointer 1706 that would be guaranteed to point to the same object, even if we 1707 avoid undefined behavior by casting to size_t and back). */ 1708 iv0->no_overflow = true; 1709 iv1->no_overflow = true; 1710 } 1711 1712 /* If the control induction variable does not overflow and the only exit 1713 from the loop is the one that we analyze, we know it must be taken 1714 eventually. */ 1715 if (only_exit) 1716 { 1717 if (!integer_zerop (iv0->step) && iv0->no_overflow) 1718 exit_must_be_taken = true; 1719 else if (!integer_zerop (iv1->step) && iv1->no_overflow) 1720 exit_must_be_taken = true; 1721 } 1722 1723 /* We can handle cases which neither of the sides of the comparison is 1724 invariant: 1725 1726 {iv0.base, iv0.step} cmp_code {iv1.base, iv1.step} 1727 as if: 1728 {iv0.base, iv0.step - iv1.step} cmp_code {iv1.base, 0} 1729 1730 provided that either below condition is satisfied: 1731 1732 a) the test is NE_EXPR; 1733 b) iv0.step - iv1.step is integer and iv0/iv1 don't overflow. 1734 1735 This rarely occurs in practice, but it is simple enough to manage. */ 1736 if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step)) 1737 { 1738 tree step_type = POINTER_TYPE_P (type) ? sizetype : type; 1739 tree step = fold_binary_to_constant (MINUS_EXPR, step_type, 1740 iv0->step, iv1->step); 1741 1742 /* No need to check sign of the new step since below code takes care 1743 of this well. */ 1744 if (code != NE_EXPR 1745 && (TREE_CODE (step) != INTEGER_CST 1746 || !iv0->no_overflow || !iv1->no_overflow)) 1747 return false; 1748 1749 iv0->step = step; 1750 if (!POINTER_TYPE_P (type)) 1751 iv0->no_overflow = false; 1752 1753 iv1->step = build_int_cst (step_type, 0); 1754 iv1->no_overflow = true; 1755 } 1756 1757 /* If the result of the comparison is a constant, the loop is weird. More 1758 precise handling would be possible, but the situation is not common enough 1759 to waste time on it. */ 1760 if (integer_zerop (iv0->step) && integer_zerop (iv1->step)) 1761 return false; 1762 1763 /* Ignore loops of while (i-- < 10) type. */ 1764 if (code != NE_EXPR) 1765 { 1766 if (iv0->step && tree_int_cst_sign_bit (iv0->step)) 1767 return false; 1768 1769 if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step)) 1770 return false; 1771 } 1772 1773 /* If the loop exits immediately, there is nothing to do. */ 1774 tree tem = fold_binary (code, boolean_type_node, iv0->base, iv1->base); 1775 if (tem && integer_zerop (tem)) 1776 { 1777 niter->niter = build_int_cst (unsigned_type_for (type), 0); 1778 niter->max = 0; 1779 return true; 1780 } 1781 1782 /* OK, now we know we have a senseful loop. Handle several cases, depending 1783 on what comparison operator is used. */ 1784 bound_difference (loop, iv1->base, iv0->base, &bnds); 1785 1786 if (dump_file && (dump_flags & TDF_DETAILS)) 1787 { 1788 fprintf (dump_file, 1789 "Analyzing # of iterations of loop %d\n", loop->num); 1790 1791 fprintf (dump_file, " exit condition "); 1792 dump_affine_iv (dump_file, iv0); 1793 fprintf (dump_file, " %s ", 1794 code == NE_EXPR ? "!=" 1795 : code == LT_EXPR ? "<" 1796 : "<="); 1797 dump_affine_iv (dump_file, iv1); 1798 fprintf (dump_file, "\n"); 1799 1800 fprintf (dump_file, " bounds on difference of bases: "); 1801 mpz_out_str (dump_file, 10, bnds.below); 1802 fprintf (dump_file, " ... "); 1803 mpz_out_str (dump_file, 10, bnds.up); 1804 fprintf (dump_file, "\n"); 1805 } 1806 1807 switch (code) 1808 { 1809 case NE_EXPR: 1810 gcc_assert (integer_zerop (iv1->step)); 1811 ret = number_of_iterations_ne (loop, type, iv0, iv1->base, niter, 1812 exit_must_be_taken, &bnds); 1813 break; 1814 1815 case LT_EXPR: 1816 ret = number_of_iterations_lt (loop, type, iv0, iv1, niter, 1817 exit_must_be_taken, &bnds); 1818 break; 1819 1820 case LE_EXPR: 1821 ret = number_of_iterations_le (loop, type, iv0, iv1, niter, 1822 exit_must_be_taken, &bnds); 1823 break; 1824 1825 default: 1826 gcc_unreachable (); 1827 } 1828 1829 mpz_clear (bnds.up); 1830 mpz_clear (bnds.below); 1831 1832 if (dump_file && (dump_flags & TDF_DETAILS)) 1833 { 1834 if (ret) 1835 { 1836 fprintf (dump_file, " result:\n"); 1837 if (!integer_nonzerop (niter->assumptions)) 1838 { 1839 fprintf (dump_file, " under assumptions "); 1840 print_generic_expr (dump_file, niter->assumptions, TDF_SLIM); 1841 fprintf (dump_file, "\n"); 1842 } 1843 1844 if (!integer_zerop (niter->may_be_zero)) 1845 { 1846 fprintf (dump_file, " zero if "); 1847 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM); 1848 fprintf (dump_file, "\n"); 1849 } 1850 1851 fprintf (dump_file, " # of iterations "); 1852 print_generic_expr (dump_file, niter->niter, TDF_SLIM); 1853 fprintf (dump_file, ", bounded by "); 1854 print_decu (niter->max, dump_file); 1855 fprintf (dump_file, "\n"); 1856 } 1857 else 1858 fprintf (dump_file, " failed\n\n"); 1859 } 1860 return ret; 1861 } 1862 1863 /* Substitute NEW for OLD in EXPR and fold the result. */ 1864 1865 static tree 1866 simplify_replace_tree (tree expr, tree old, tree new_tree) 1867 { 1868 unsigned i, n; 1869 tree ret = NULL_TREE, e, se; 1870 1871 if (!expr) 1872 return NULL_TREE; 1873 1874 /* Do not bother to replace constants. */ 1875 if (CONSTANT_CLASS_P (old)) 1876 return expr; 1877 1878 if (expr == old 1879 || operand_equal_p (expr, old, 0)) 1880 return unshare_expr (new_tree); 1881 1882 if (!EXPR_P (expr)) 1883 return expr; 1884 1885 n = TREE_OPERAND_LENGTH (expr); 1886 for (i = 0; i < n; i++) 1887 { 1888 e = TREE_OPERAND (expr, i); 1889 se = simplify_replace_tree (e, old, new_tree); 1890 if (e == se) 1891 continue; 1892 1893 if (!ret) 1894 ret = copy_node (expr); 1895 1896 TREE_OPERAND (ret, i) = se; 1897 } 1898 1899 return (ret ? fold (ret) : expr); 1900 } 1901 1902 /* Expand definitions of ssa names in EXPR as long as they are simple 1903 enough, and return the new expression. If STOP is specified, stop 1904 expanding if EXPR equals to it. */ 1905 1906 tree 1907 expand_simple_operations (tree expr, tree stop) 1908 { 1909 unsigned i, n; 1910 tree ret = NULL_TREE, e, ee, e1; 1911 enum tree_code code; 1912 gimple *stmt; 1913 1914 if (expr == NULL_TREE) 1915 return expr; 1916 1917 if (is_gimple_min_invariant (expr)) 1918 return expr; 1919 1920 code = TREE_CODE (expr); 1921 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))) 1922 { 1923 n = TREE_OPERAND_LENGTH (expr); 1924 for (i = 0; i < n; i++) 1925 { 1926 e = TREE_OPERAND (expr, i); 1927 ee = expand_simple_operations (e, stop); 1928 if (e == ee) 1929 continue; 1930 1931 if (!ret) 1932 ret = copy_node (expr); 1933 1934 TREE_OPERAND (ret, i) = ee; 1935 } 1936 1937 if (!ret) 1938 return expr; 1939 1940 fold_defer_overflow_warnings (); 1941 ret = fold (ret); 1942 fold_undefer_and_ignore_overflow_warnings (); 1943 return ret; 1944 } 1945 1946 /* Stop if it's not ssa name or the one we don't want to expand. */ 1947 if (TREE_CODE (expr) != SSA_NAME || expr == stop) 1948 return expr; 1949 1950 stmt = SSA_NAME_DEF_STMT (expr); 1951 if (gimple_code (stmt) == GIMPLE_PHI) 1952 { 1953 basic_block src, dest; 1954 1955 if (gimple_phi_num_args (stmt) != 1) 1956 return expr; 1957 e = PHI_ARG_DEF (stmt, 0); 1958 1959 /* Avoid propagating through loop exit phi nodes, which 1960 could break loop-closed SSA form restrictions. */ 1961 dest = gimple_bb (stmt); 1962 src = single_pred (dest); 1963 if (TREE_CODE (e) == SSA_NAME 1964 && src->loop_father != dest->loop_father) 1965 return expr; 1966 1967 return expand_simple_operations (e, stop); 1968 } 1969 if (gimple_code (stmt) != GIMPLE_ASSIGN) 1970 return expr; 1971 1972 /* Avoid expanding to expressions that contain SSA names that need 1973 to take part in abnormal coalescing. */ 1974 ssa_op_iter iter; 1975 FOR_EACH_SSA_TREE_OPERAND (e, stmt, iter, SSA_OP_USE) 1976 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e)) 1977 return expr; 1978 1979 e = gimple_assign_rhs1 (stmt); 1980 code = gimple_assign_rhs_code (stmt); 1981 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) 1982 { 1983 if (is_gimple_min_invariant (e)) 1984 return e; 1985 1986 if (code == SSA_NAME) 1987 return expand_simple_operations (e, stop); 1988 else if (code == ADDR_EXPR) 1989 { 1990 poly_int64 offset; 1991 tree base = get_addr_base_and_unit_offset (TREE_OPERAND (e, 0), 1992 &offset); 1993 if (base 1994 && TREE_CODE (base) == MEM_REF) 1995 { 1996 ee = expand_simple_operations (TREE_OPERAND (base, 0), stop); 1997 return fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (expr), ee, 1998 wide_int_to_tree (sizetype, 1999 mem_ref_offset (base) 2000 + offset)); 2001 } 2002 } 2003 2004 return expr; 2005 } 2006 2007 switch (code) 2008 { 2009 CASE_CONVERT: 2010 /* Casts are simple. */ 2011 ee = expand_simple_operations (e, stop); 2012 return fold_build1 (code, TREE_TYPE (expr), ee); 2013 2014 case PLUS_EXPR: 2015 case MINUS_EXPR: 2016 if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (expr)) 2017 && TYPE_OVERFLOW_TRAPS (TREE_TYPE (expr))) 2018 return expr; 2019 /* Fallthru. */ 2020 case POINTER_PLUS_EXPR: 2021 /* And increments and decrements by a constant are simple. */ 2022 e1 = gimple_assign_rhs2 (stmt); 2023 if (!is_gimple_min_invariant (e1)) 2024 return expr; 2025 2026 ee = expand_simple_operations (e, stop); 2027 return fold_build2 (code, TREE_TYPE (expr), ee, e1); 2028 2029 default: 2030 return expr; 2031 } 2032 } 2033 2034 /* Tries to simplify EXPR using the condition COND. Returns the simplified 2035 expression (or EXPR unchanged, if no simplification was possible). */ 2036 2037 static tree 2038 tree_simplify_using_condition_1 (tree cond, tree expr) 2039 { 2040 bool changed; 2041 tree e, e0, e1, e2, notcond; 2042 enum tree_code code = TREE_CODE (expr); 2043 2044 if (code == INTEGER_CST) 2045 return expr; 2046 2047 if (code == TRUTH_OR_EXPR 2048 || code == TRUTH_AND_EXPR 2049 || code == COND_EXPR) 2050 { 2051 changed = false; 2052 2053 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0)); 2054 if (TREE_OPERAND (expr, 0) != e0) 2055 changed = true; 2056 2057 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1)); 2058 if (TREE_OPERAND (expr, 1) != e1) 2059 changed = true; 2060 2061 if (code == COND_EXPR) 2062 { 2063 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2)); 2064 if (TREE_OPERAND (expr, 2) != e2) 2065 changed = true; 2066 } 2067 else 2068 e2 = NULL_TREE; 2069 2070 if (changed) 2071 { 2072 if (code == COND_EXPR) 2073 expr = fold_build3 (code, boolean_type_node, e0, e1, e2); 2074 else 2075 expr = fold_build2 (code, boolean_type_node, e0, e1); 2076 } 2077 2078 return expr; 2079 } 2080 2081 /* In case COND is equality, we may be able to simplify EXPR by copy/constant 2082 propagation, and vice versa. Fold does not handle this, since it is 2083 considered too expensive. */ 2084 if (TREE_CODE (cond) == EQ_EXPR) 2085 { 2086 e0 = TREE_OPERAND (cond, 0); 2087 e1 = TREE_OPERAND (cond, 1); 2088 2089 /* We know that e0 == e1. Check whether we cannot simplify expr 2090 using this fact. */ 2091 e = simplify_replace_tree (expr, e0, e1); 2092 if (integer_zerop (e) || integer_nonzerop (e)) 2093 return e; 2094 2095 e = simplify_replace_tree (expr, e1, e0); 2096 if (integer_zerop (e) || integer_nonzerop (e)) 2097 return e; 2098 } 2099 if (TREE_CODE (expr) == EQ_EXPR) 2100 { 2101 e0 = TREE_OPERAND (expr, 0); 2102 e1 = TREE_OPERAND (expr, 1); 2103 2104 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */ 2105 e = simplify_replace_tree (cond, e0, e1); 2106 if (integer_zerop (e)) 2107 return e; 2108 e = simplify_replace_tree (cond, e1, e0); 2109 if (integer_zerop (e)) 2110 return e; 2111 } 2112 if (TREE_CODE (expr) == NE_EXPR) 2113 { 2114 e0 = TREE_OPERAND (expr, 0); 2115 e1 = TREE_OPERAND (expr, 1); 2116 2117 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */ 2118 e = simplify_replace_tree (cond, e0, e1); 2119 if (integer_zerop (e)) 2120 return boolean_true_node; 2121 e = simplify_replace_tree (cond, e1, e0); 2122 if (integer_zerop (e)) 2123 return boolean_true_node; 2124 } 2125 2126 /* Check whether COND ==> EXPR. */ 2127 notcond = invert_truthvalue (cond); 2128 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, expr); 2129 if (e && integer_nonzerop (e)) 2130 return e; 2131 2132 /* Check whether COND ==> not EXPR. */ 2133 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, expr); 2134 if (e && integer_zerop (e)) 2135 return e; 2136 2137 return expr; 2138 } 2139 2140 /* Tries to simplify EXPR using the condition COND. Returns the simplified 2141 expression (or EXPR unchanged, if no simplification was possible). 2142 Wrapper around tree_simplify_using_condition_1 that ensures that chains 2143 of simple operations in definitions of ssa names in COND are expanded, 2144 so that things like casts or incrementing the value of the bound before 2145 the loop do not cause us to fail. */ 2146 2147 static tree 2148 tree_simplify_using_condition (tree cond, tree expr) 2149 { 2150 cond = expand_simple_operations (cond); 2151 2152 return tree_simplify_using_condition_1 (cond, expr); 2153 } 2154 2155 /* Tries to simplify EXPR using the conditions on entry to LOOP. 2156 Returns the simplified expression (or EXPR unchanged, if no 2157 simplification was possible). */ 2158 2159 tree 2160 simplify_using_initial_conditions (struct loop *loop, tree expr) 2161 { 2162 edge e; 2163 basic_block bb; 2164 gimple *stmt; 2165 tree cond, expanded, backup; 2166 int cnt = 0; 2167 2168 if (TREE_CODE (expr) == INTEGER_CST) 2169 return expr; 2170 2171 backup = expanded = expand_simple_operations (expr); 2172 2173 /* Limit walking the dominators to avoid quadraticness in 2174 the number of BBs times the number of loops in degenerate 2175 cases. */ 2176 for (bb = loop->header; 2177 bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK; 2178 bb = get_immediate_dominator (CDI_DOMINATORS, bb)) 2179 { 2180 if (!single_pred_p (bb)) 2181 continue; 2182 e = single_pred_edge (bb); 2183 2184 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) 2185 continue; 2186 2187 stmt = last_stmt (e->src); 2188 cond = fold_build2 (gimple_cond_code (stmt), 2189 boolean_type_node, 2190 gimple_cond_lhs (stmt), 2191 gimple_cond_rhs (stmt)); 2192 if (e->flags & EDGE_FALSE_VALUE) 2193 cond = invert_truthvalue (cond); 2194 expanded = tree_simplify_using_condition (cond, expanded); 2195 /* Break if EXPR is simplified to const values. */ 2196 if (expanded 2197 && (integer_zerop (expanded) || integer_nonzerop (expanded))) 2198 return expanded; 2199 2200 ++cnt; 2201 } 2202 2203 /* Return the original expression if no simplification is done. */ 2204 return operand_equal_p (backup, expanded, 0) ? expr : expanded; 2205 } 2206 2207 /* Tries to simplify EXPR using the evolutions of the loop invariants 2208 in the superloops of LOOP. Returns the simplified expression 2209 (or EXPR unchanged, if no simplification was possible). */ 2210 2211 static tree 2212 simplify_using_outer_evolutions (struct loop *loop, tree expr) 2213 { 2214 enum tree_code code = TREE_CODE (expr); 2215 bool changed; 2216 tree e, e0, e1, e2; 2217 2218 if (is_gimple_min_invariant (expr)) 2219 return expr; 2220 2221 if (code == TRUTH_OR_EXPR 2222 || code == TRUTH_AND_EXPR 2223 || code == COND_EXPR) 2224 { 2225 changed = false; 2226 2227 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0)); 2228 if (TREE_OPERAND (expr, 0) != e0) 2229 changed = true; 2230 2231 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1)); 2232 if (TREE_OPERAND (expr, 1) != e1) 2233 changed = true; 2234 2235 if (code == COND_EXPR) 2236 { 2237 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2)); 2238 if (TREE_OPERAND (expr, 2) != e2) 2239 changed = true; 2240 } 2241 else 2242 e2 = NULL_TREE; 2243 2244 if (changed) 2245 { 2246 if (code == COND_EXPR) 2247 expr = fold_build3 (code, boolean_type_node, e0, e1, e2); 2248 else 2249 expr = fold_build2 (code, boolean_type_node, e0, e1); 2250 } 2251 2252 return expr; 2253 } 2254 2255 e = instantiate_parameters (loop, expr); 2256 if (is_gimple_min_invariant (e)) 2257 return e; 2258 2259 return expr; 2260 } 2261 2262 /* Returns true if EXIT is the only possible exit from LOOP. */ 2263 2264 bool 2265 loop_only_exit_p (const struct loop *loop, const_edge exit) 2266 { 2267 basic_block *body; 2268 gimple_stmt_iterator bsi; 2269 unsigned i; 2270 2271 if (exit != single_exit (loop)) 2272 return false; 2273 2274 body = get_loop_body (loop); 2275 for (i = 0; i < loop->num_nodes; i++) 2276 { 2277 for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi)) 2278 if (stmt_can_terminate_bb_p (gsi_stmt (bsi))) 2279 { 2280 free (body); 2281 return true; 2282 } 2283 } 2284 2285 free (body); 2286 return true; 2287 } 2288 2289 /* Stores description of number of iterations of LOOP derived from 2290 EXIT (an exit edge of the LOOP) in NITER. Returns true if some useful 2291 information could be derived (and fields of NITER have meaning described 2292 in comments at struct tree_niter_desc declaration), false otherwise. 2293 When EVERY_ITERATION is true, only tests that are known to be executed 2294 every iteration are considered (i.e. only test that alone bounds the loop). 2295 If AT_STMT is not NULL, this function stores LOOP's condition statement in 2296 it when returning true. */ 2297 2298 bool 2299 number_of_iterations_exit_assumptions (struct loop *loop, edge exit, 2300 struct tree_niter_desc *niter, 2301 gcond **at_stmt, bool every_iteration) 2302 { 2303 gimple *last; 2304 gcond *stmt; 2305 tree type; 2306 tree op0, op1; 2307 enum tree_code code; 2308 affine_iv iv0, iv1; 2309 bool safe; 2310 2311 /* Nothing to analyze if the loop is known to be infinite. */ 2312 if (loop_constraint_set_p (loop, LOOP_C_INFINITE)) 2313 return false; 2314 2315 safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src); 2316 2317 if (every_iteration && !safe) 2318 return false; 2319 2320 niter->assumptions = boolean_false_node; 2321 niter->control.base = NULL_TREE; 2322 niter->control.step = NULL_TREE; 2323 niter->control.no_overflow = false; 2324 last = last_stmt (exit->src); 2325 if (!last) 2326 return false; 2327 stmt = dyn_cast <gcond *> (last); 2328 if (!stmt) 2329 return false; 2330 2331 /* We want the condition for staying inside loop. */ 2332 code = gimple_cond_code (stmt); 2333 if (exit->flags & EDGE_TRUE_VALUE) 2334 code = invert_tree_comparison (code, false); 2335 2336 switch (code) 2337 { 2338 case GT_EXPR: 2339 case GE_EXPR: 2340 case LT_EXPR: 2341 case LE_EXPR: 2342 case NE_EXPR: 2343 break; 2344 2345 default: 2346 return false; 2347 } 2348 2349 op0 = gimple_cond_lhs (stmt); 2350 op1 = gimple_cond_rhs (stmt); 2351 type = TREE_TYPE (op0); 2352 2353 if (TREE_CODE (type) != INTEGER_TYPE 2354 && !POINTER_TYPE_P (type)) 2355 return false; 2356 2357 tree iv0_niters = NULL_TREE; 2358 if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt), 2359 op0, &iv0, safe ? &iv0_niters : NULL, false)) 2360 return false; 2361 tree iv1_niters = NULL_TREE; 2362 if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt), 2363 op1, &iv1, safe ? &iv1_niters : NULL, false)) 2364 return false; 2365 /* Give up on complicated case. */ 2366 if (iv0_niters && iv1_niters) 2367 return false; 2368 2369 /* We don't want to see undefined signed overflow warnings while 2370 computing the number of iterations. */ 2371 fold_defer_overflow_warnings (); 2372 2373 iv0.base = expand_simple_operations (iv0.base); 2374 iv1.base = expand_simple_operations (iv1.base); 2375 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter, 2376 loop_only_exit_p (loop, exit), safe)) 2377 { 2378 fold_undefer_and_ignore_overflow_warnings (); 2379 return false; 2380 } 2381 2382 /* Incorporate additional assumption implied by control iv. */ 2383 tree iv_niters = iv0_niters ? iv0_niters : iv1_niters; 2384 if (iv_niters) 2385 { 2386 tree assumption = fold_build2 (LE_EXPR, boolean_type_node, niter->niter, 2387 fold_convert (TREE_TYPE (niter->niter), 2388 iv_niters)); 2389 2390 if (!integer_nonzerop (assumption)) 2391 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 2392 niter->assumptions, assumption); 2393 2394 /* Refine upper bound if possible. */ 2395 if (TREE_CODE (iv_niters) == INTEGER_CST 2396 && niter->max > wi::to_widest (iv_niters)) 2397 niter->max = wi::to_widest (iv_niters); 2398 } 2399 2400 /* There is no assumptions if the loop is known to be finite. */ 2401 if (!integer_zerop (niter->assumptions) 2402 && loop_constraint_set_p (loop, LOOP_C_FINITE)) 2403 niter->assumptions = boolean_true_node; 2404 2405 if (optimize >= 3) 2406 { 2407 niter->assumptions = simplify_using_outer_evolutions (loop, 2408 niter->assumptions); 2409 niter->may_be_zero = simplify_using_outer_evolutions (loop, 2410 niter->may_be_zero); 2411 niter->niter = simplify_using_outer_evolutions (loop, niter->niter); 2412 } 2413 2414 niter->assumptions 2415 = simplify_using_initial_conditions (loop, 2416 niter->assumptions); 2417 niter->may_be_zero 2418 = simplify_using_initial_conditions (loop, 2419 niter->may_be_zero); 2420 2421 fold_undefer_and_ignore_overflow_warnings (); 2422 2423 /* If NITER has simplified into a constant, update MAX. */ 2424 if (TREE_CODE (niter->niter) == INTEGER_CST) 2425 niter->max = wi::to_widest (niter->niter); 2426 2427 if (at_stmt) 2428 *at_stmt = stmt; 2429 2430 return (!integer_zerop (niter->assumptions)); 2431 } 2432 2433 /* Like number_of_iterations_exit_assumptions, but return TRUE only if 2434 the niter information holds unconditionally. */ 2435 2436 bool 2437 number_of_iterations_exit (struct loop *loop, edge exit, 2438 struct tree_niter_desc *niter, 2439 bool warn, bool every_iteration) 2440 { 2441 gcond *stmt; 2442 if (!number_of_iterations_exit_assumptions (loop, exit, niter, 2443 &stmt, every_iteration)) 2444 return false; 2445 2446 if (integer_nonzerop (niter->assumptions)) 2447 return true; 2448 2449 if (warn) 2450 dump_printf_loc (MSG_MISSED_OPTIMIZATION, gimple_location_safe (stmt), 2451 "missed loop optimization: niters analysis ends up " 2452 "with assumptions.\n"); 2453 2454 return false; 2455 } 2456 2457 /* Try to determine the number of iterations of LOOP. If we succeed, 2458 expression giving number of iterations is returned and *EXIT is 2459 set to the edge from that the information is obtained. Otherwise 2460 chrec_dont_know is returned. */ 2461 2462 tree 2463 find_loop_niter (struct loop *loop, edge *exit) 2464 { 2465 unsigned i; 2466 vec<edge> exits = get_loop_exit_edges (loop); 2467 edge ex; 2468 tree niter = NULL_TREE, aniter; 2469 struct tree_niter_desc desc; 2470 2471 *exit = NULL; 2472 FOR_EACH_VEC_ELT (exits, i, ex) 2473 { 2474 if (!number_of_iterations_exit (loop, ex, &desc, false)) 2475 continue; 2476 2477 if (integer_nonzerop (desc.may_be_zero)) 2478 { 2479 /* We exit in the first iteration through this exit. 2480 We won't find anything better. */ 2481 niter = build_int_cst (unsigned_type_node, 0); 2482 *exit = ex; 2483 break; 2484 } 2485 2486 if (!integer_zerop (desc.may_be_zero)) 2487 continue; 2488 2489 aniter = desc.niter; 2490 2491 if (!niter) 2492 { 2493 /* Nothing recorded yet. */ 2494 niter = aniter; 2495 *exit = ex; 2496 continue; 2497 } 2498 2499 /* Prefer constants, the lower the better. */ 2500 if (TREE_CODE (aniter) != INTEGER_CST) 2501 continue; 2502 2503 if (TREE_CODE (niter) != INTEGER_CST) 2504 { 2505 niter = aniter; 2506 *exit = ex; 2507 continue; 2508 } 2509 2510 if (tree_int_cst_lt (aniter, niter)) 2511 { 2512 niter = aniter; 2513 *exit = ex; 2514 continue; 2515 } 2516 } 2517 exits.release (); 2518 2519 return niter ? niter : chrec_dont_know; 2520 } 2521 2522 /* Return true if loop is known to have bounded number of iterations. */ 2523 2524 bool 2525 finite_loop_p (struct loop *loop) 2526 { 2527 widest_int nit; 2528 int flags; 2529 2530 flags = flags_from_decl_or_type (current_function_decl); 2531 if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE)) 2532 { 2533 if (dump_file && (dump_flags & TDF_DETAILS)) 2534 fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n", 2535 loop->num); 2536 return true; 2537 } 2538 2539 if (loop->any_upper_bound 2540 || max_loop_iterations (loop, &nit)) 2541 { 2542 if (dump_file && (dump_flags & TDF_DETAILS)) 2543 fprintf (dump_file, "Found loop %i to be finite: upper bound found.\n", 2544 loop->num); 2545 return true; 2546 } 2547 return false; 2548 } 2549 2550 /* 2551 2552 Analysis of a number of iterations of a loop by a brute-force evaluation. 2553 2554 */ 2555 2556 /* Bound on the number of iterations we try to evaluate. */ 2557 2558 #define MAX_ITERATIONS_TO_TRACK \ 2559 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK)) 2560 2561 /* Returns the loop phi node of LOOP such that ssa name X is derived from its 2562 result by a chain of operations such that all but exactly one of their 2563 operands are constants. */ 2564 2565 static gphi * 2566 chain_of_csts_start (struct loop *loop, tree x) 2567 { 2568 gimple *stmt = SSA_NAME_DEF_STMT (x); 2569 tree use; 2570 basic_block bb = gimple_bb (stmt); 2571 enum tree_code code; 2572 2573 if (!bb 2574 || !flow_bb_inside_loop_p (loop, bb)) 2575 return NULL; 2576 2577 if (gimple_code (stmt) == GIMPLE_PHI) 2578 { 2579 if (bb == loop->header) 2580 return as_a <gphi *> (stmt); 2581 2582 return NULL; 2583 } 2584 2585 if (gimple_code (stmt) != GIMPLE_ASSIGN 2586 || gimple_assign_rhs_class (stmt) == GIMPLE_TERNARY_RHS) 2587 return NULL; 2588 2589 code = gimple_assign_rhs_code (stmt); 2590 if (gimple_references_memory_p (stmt) 2591 || TREE_CODE_CLASS (code) == tcc_reference 2592 || (code == ADDR_EXPR 2593 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))) 2594 return NULL; 2595 2596 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE); 2597 if (use == NULL_TREE) 2598 return NULL; 2599 2600 return chain_of_csts_start (loop, use); 2601 } 2602 2603 /* Determines whether the expression X is derived from a result of a phi node 2604 in header of LOOP such that 2605 2606 * the derivation of X consists only from operations with constants 2607 * the initial value of the phi node is constant 2608 * the value of the phi node in the next iteration can be derived from the 2609 value in the current iteration by a chain of operations with constants, 2610 or is also a constant 2611 2612 If such phi node exists, it is returned, otherwise NULL is returned. */ 2613 2614 static gphi * 2615 get_base_for (struct loop *loop, tree x) 2616 { 2617 gphi *phi; 2618 tree init, next; 2619 2620 if (is_gimple_min_invariant (x)) 2621 return NULL; 2622 2623 phi = chain_of_csts_start (loop, x); 2624 if (!phi) 2625 return NULL; 2626 2627 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); 2628 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); 2629 2630 if (!is_gimple_min_invariant (init)) 2631 return NULL; 2632 2633 if (TREE_CODE (next) == SSA_NAME 2634 && chain_of_csts_start (loop, next) != phi) 2635 return NULL; 2636 2637 return phi; 2638 } 2639 2640 /* Given an expression X, then 2641 2642 * if X is NULL_TREE, we return the constant BASE. 2643 * if X is a constant, we return the constant X. 2644 * otherwise X is a SSA name, whose value in the considered loop is derived 2645 by a chain of operations with constant from a result of a phi node in 2646 the header of the loop. Then we return value of X when the value of the 2647 result of this phi node is given by the constant BASE. */ 2648 2649 static tree 2650 get_val_for (tree x, tree base) 2651 { 2652 gimple *stmt; 2653 2654 gcc_checking_assert (is_gimple_min_invariant (base)); 2655 2656 if (!x) 2657 return base; 2658 else if (is_gimple_min_invariant (x)) 2659 return x; 2660 2661 stmt = SSA_NAME_DEF_STMT (x); 2662 if (gimple_code (stmt) == GIMPLE_PHI) 2663 return base; 2664 2665 gcc_checking_assert (is_gimple_assign (stmt)); 2666 2667 /* STMT must be either an assignment of a single SSA name or an 2668 expression involving an SSA name and a constant. Try to fold that 2669 expression using the value for the SSA name. */ 2670 if (gimple_assign_ssa_name_copy_p (stmt)) 2671 return get_val_for (gimple_assign_rhs1 (stmt), base); 2672 else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS 2673 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME) 2674 return fold_build1 (gimple_assign_rhs_code (stmt), 2675 gimple_expr_type (stmt), 2676 get_val_for (gimple_assign_rhs1 (stmt), base)); 2677 else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS) 2678 { 2679 tree rhs1 = gimple_assign_rhs1 (stmt); 2680 tree rhs2 = gimple_assign_rhs2 (stmt); 2681 if (TREE_CODE (rhs1) == SSA_NAME) 2682 rhs1 = get_val_for (rhs1, base); 2683 else if (TREE_CODE (rhs2) == SSA_NAME) 2684 rhs2 = get_val_for (rhs2, base); 2685 else 2686 gcc_unreachable (); 2687 return fold_build2 (gimple_assign_rhs_code (stmt), 2688 gimple_expr_type (stmt), rhs1, rhs2); 2689 } 2690 else 2691 gcc_unreachable (); 2692 } 2693 2694 2695 /* Tries to count the number of iterations of LOOP till it exits by EXIT 2696 by brute force -- i.e. by determining the value of the operands of the 2697 condition at EXIT in first few iterations of the loop (assuming that 2698 these values are constant) and determining the first one in that the 2699 condition is not satisfied. Returns the constant giving the number 2700 of the iterations of LOOP if successful, chrec_dont_know otherwise. */ 2701 2702 tree 2703 loop_niter_by_eval (struct loop *loop, edge exit) 2704 { 2705 tree acnd; 2706 tree op[2], val[2], next[2], aval[2]; 2707 gphi *phi; 2708 gimple *cond; 2709 unsigned i, j; 2710 enum tree_code cmp; 2711 2712 cond = last_stmt (exit->src); 2713 if (!cond || gimple_code (cond) != GIMPLE_COND) 2714 return chrec_dont_know; 2715 2716 cmp = gimple_cond_code (cond); 2717 if (exit->flags & EDGE_TRUE_VALUE) 2718 cmp = invert_tree_comparison (cmp, false); 2719 2720 switch (cmp) 2721 { 2722 case EQ_EXPR: 2723 case NE_EXPR: 2724 case GT_EXPR: 2725 case GE_EXPR: 2726 case LT_EXPR: 2727 case LE_EXPR: 2728 op[0] = gimple_cond_lhs (cond); 2729 op[1] = gimple_cond_rhs (cond); 2730 break; 2731 2732 default: 2733 return chrec_dont_know; 2734 } 2735 2736 for (j = 0; j < 2; j++) 2737 { 2738 if (is_gimple_min_invariant (op[j])) 2739 { 2740 val[j] = op[j]; 2741 next[j] = NULL_TREE; 2742 op[j] = NULL_TREE; 2743 } 2744 else 2745 { 2746 phi = get_base_for (loop, op[j]); 2747 if (!phi) 2748 return chrec_dont_know; 2749 val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); 2750 next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); 2751 } 2752 } 2753 2754 /* Don't issue signed overflow warnings. */ 2755 fold_defer_overflow_warnings (); 2756 2757 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++) 2758 { 2759 for (j = 0; j < 2; j++) 2760 aval[j] = get_val_for (op[j], val[j]); 2761 2762 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]); 2763 if (acnd && integer_zerop (acnd)) 2764 { 2765 fold_undefer_and_ignore_overflow_warnings (); 2766 if (dump_file && (dump_flags & TDF_DETAILS)) 2767 fprintf (dump_file, 2768 "Proved that loop %d iterates %d times using brute force.\n", 2769 loop->num, i); 2770 return build_int_cst (unsigned_type_node, i); 2771 } 2772 2773 for (j = 0; j < 2; j++) 2774 { 2775 aval[j] = val[j]; 2776 val[j] = get_val_for (next[j], val[j]); 2777 if (!is_gimple_min_invariant (val[j])) 2778 { 2779 fold_undefer_and_ignore_overflow_warnings (); 2780 return chrec_dont_know; 2781 } 2782 } 2783 2784 /* If the next iteration would use the same base values 2785 as the current one, there is no point looping further, 2786 all following iterations will be the same as this one. */ 2787 if (val[0] == aval[0] && val[1] == aval[1]) 2788 break; 2789 } 2790 2791 fold_undefer_and_ignore_overflow_warnings (); 2792 2793 return chrec_dont_know; 2794 } 2795 2796 /* Finds the exit of the LOOP by that the loop exits after a constant 2797 number of iterations and stores the exit edge to *EXIT. The constant 2798 giving the number of iterations of LOOP is returned. The number of 2799 iterations is determined using loop_niter_by_eval (i.e. by brute force 2800 evaluation). If we are unable to find the exit for that loop_niter_by_eval 2801 determines the number of iterations, chrec_dont_know is returned. */ 2802 2803 tree 2804 find_loop_niter_by_eval (struct loop *loop, edge *exit) 2805 { 2806 unsigned i; 2807 vec<edge> exits = get_loop_exit_edges (loop); 2808 edge ex; 2809 tree niter = NULL_TREE, aniter; 2810 2811 *exit = NULL; 2812 2813 /* Loops with multiple exits are expensive to handle and less important. */ 2814 if (!flag_expensive_optimizations 2815 && exits.length () > 1) 2816 { 2817 exits.release (); 2818 return chrec_dont_know; 2819 } 2820 2821 FOR_EACH_VEC_ELT (exits, i, ex) 2822 { 2823 if (!just_once_each_iteration_p (loop, ex->src)) 2824 continue; 2825 2826 aniter = loop_niter_by_eval (loop, ex); 2827 if (chrec_contains_undetermined (aniter)) 2828 continue; 2829 2830 if (niter 2831 && !tree_int_cst_lt (aniter, niter)) 2832 continue; 2833 2834 niter = aniter; 2835 *exit = ex; 2836 } 2837 exits.release (); 2838 2839 return niter ? niter : chrec_dont_know; 2840 } 2841 2842 /* 2843 2844 Analysis of upper bounds on number of iterations of a loop. 2845 2846 */ 2847 2848 static widest_int derive_constant_upper_bound_ops (tree, tree, 2849 enum tree_code, tree); 2850 2851 /* Returns a constant upper bound on the value of the right-hand side of 2852 an assignment statement STMT. */ 2853 2854 static widest_int 2855 derive_constant_upper_bound_assign (gimple *stmt) 2856 { 2857 enum tree_code code = gimple_assign_rhs_code (stmt); 2858 tree op0 = gimple_assign_rhs1 (stmt); 2859 tree op1 = gimple_assign_rhs2 (stmt); 2860 2861 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)), 2862 op0, code, op1); 2863 } 2864 2865 /* Returns a constant upper bound on the value of expression VAL. VAL 2866 is considered to be unsigned. If its type is signed, its value must 2867 be nonnegative. */ 2868 2869 static widest_int 2870 derive_constant_upper_bound (tree val) 2871 { 2872 enum tree_code code; 2873 tree op0, op1, op2; 2874 2875 extract_ops_from_tree (val, &code, &op0, &op1, &op2); 2876 return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1); 2877 } 2878 2879 /* Returns a constant upper bound on the value of expression OP0 CODE OP1, 2880 whose type is TYPE. The expression is considered to be unsigned. If 2881 its type is signed, its value must be nonnegative. */ 2882 2883 static widest_int 2884 derive_constant_upper_bound_ops (tree type, tree op0, 2885 enum tree_code code, tree op1) 2886 { 2887 tree subtype, maxt; 2888 widest_int bnd, max, cst; 2889 gimple *stmt; 2890 2891 if (INTEGRAL_TYPE_P (type)) 2892 maxt = TYPE_MAX_VALUE (type); 2893 else 2894 maxt = upper_bound_in_type (type, type); 2895 2896 max = wi::to_widest (maxt); 2897 2898 switch (code) 2899 { 2900 case INTEGER_CST: 2901 return wi::to_widest (op0); 2902 2903 CASE_CONVERT: 2904 subtype = TREE_TYPE (op0); 2905 if (!TYPE_UNSIGNED (subtype) 2906 /* If TYPE is also signed, the fact that VAL is nonnegative implies 2907 that OP0 is nonnegative. */ 2908 && TYPE_UNSIGNED (type) 2909 && !tree_expr_nonnegative_p (op0)) 2910 { 2911 /* If we cannot prove that the casted expression is nonnegative, 2912 we cannot establish more useful upper bound than the precision 2913 of the type gives us. */ 2914 return max; 2915 } 2916 2917 /* We now know that op0 is an nonnegative value. Try deriving an upper 2918 bound for it. */ 2919 bnd = derive_constant_upper_bound (op0); 2920 2921 /* If the bound does not fit in TYPE, max. value of TYPE could be 2922 attained. */ 2923 if (wi::ltu_p (max, bnd)) 2924 return max; 2925 2926 return bnd; 2927 2928 case PLUS_EXPR: 2929 case POINTER_PLUS_EXPR: 2930 case MINUS_EXPR: 2931 if (TREE_CODE (op1) != INTEGER_CST 2932 || !tree_expr_nonnegative_p (op0)) 2933 return max; 2934 2935 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to 2936 choose the most logical way how to treat this constant regardless 2937 of the signedness of the type. */ 2938 cst = wi::sext (wi::to_widest (op1), TYPE_PRECISION (type)); 2939 if (code != MINUS_EXPR) 2940 cst = -cst; 2941 2942 bnd = derive_constant_upper_bound (op0); 2943 2944 if (wi::neg_p (cst)) 2945 { 2946 cst = -cst; 2947 /* Avoid CST == 0x80000... */ 2948 if (wi::neg_p (cst)) 2949 return max; 2950 2951 /* OP0 + CST. We need to check that 2952 BND <= MAX (type) - CST. */ 2953 2954 widest_int mmax = max - cst; 2955 if (wi::leu_p (bnd, mmax)) 2956 return max; 2957 2958 return bnd + cst; 2959 } 2960 else 2961 { 2962 /* OP0 - CST, where CST >= 0. 2963 2964 If TYPE is signed, we have already verified that OP0 >= 0, and we 2965 know that the result is nonnegative. This implies that 2966 VAL <= BND - CST. 2967 2968 If TYPE is unsigned, we must additionally know that OP0 >= CST, 2969 otherwise the operation underflows. 2970 */ 2971 2972 /* This should only happen if the type is unsigned; however, for 2973 buggy programs that use overflowing signed arithmetics even with 2974 -fno-wrapv, this condition may also be true for signed values. */ 2975 if (wi::ltu_p (bnd, cst)) 2976 return max; 2977 2978 if (TYPE_UNSIGNED (type)) 2979 { 2980 tree tem = fold_binary (GE_EXPR, boolean_type_node, op0, 2981 wide_int_to_tree (type, cst)); 2982 if (!tem || integer_nonzerop (tem)) 2983 return max; 2984 } 2985 2986 bnd -= cst; 2987 } 2988 2989 return bnd; 2990 2991 case FLOOR_DIV_EXPR: 2992 case EXACT_DIV_EXPR: 2993 if (TREE_CODE (op1) != INTEGER_CST 2994 || tree_int_cst_sign_bit (op1)) 2995 return max; 2996 2997 bnd = derive_constant_upper_bound (op0); 2998 return wi::udiv_floor (bnd, wi::to_widest (op1)); 2999 3000 case BIT_AND_EXPR: 3001 if (TREE_CODE (op1) != INTEGER_CST 3002 || tree_int_cst_sign_bit (op1)) 3003 return max; 3004 return wi::to_widest (op1); 3005 3006 case SSA_NAME: 3007 stmt = SSA_NAME_DEF_STMT (op0); 3008 if (gimple_code (stmt) != GIMPLE_ASSIGN 3009 || gimple_assign_lhs (stmt) != op0) 3010 return max; 3011 return derive_constant_upper_bound_assign (stmt); 3012 3013 default: 3014 return max; 3015 } 3016 } 3017 3018 /* Emit a -Waggressive-loop-optimizations warning if needed. */ 3019 3020 static void 3021 do_warn_aggressive_loop_optimizations (struct loop *loop, 3022 widest_int i_bound, gimple *stmt) 3023 { 3024 /* Don't warn if the loop doesn't have known constant bound. */ 3025 if (!loop->nb_iterations 3026 || TREE_CODE (loop->nb_iterations) != INTEGER_CST 3027 || !warn_aggressive_loop_optimizations 3028 /* To avoid warning multiple times for the same loop, 3029 only start warning when we preserve loops. */ 3030 || (cfun->curr_properties & PROP_loops) == 0 3031 /* Only warn once per loop. */ 3032 || loop->warned_aggressive_loop_optimizations 3033 /* Only warn if undefined behavior gives us lower estimate than the 3034 known constant bound. */ 3035 || wi::cmpu (i_bound, wi::to_widest (loop->nb_iterations)) >= 0 3036 /* And undefined behavior happens unconditionally. */ 3037 || !dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (stmt))) 3038 return; 3039 3040 edge e = single_exit (loop); 3041 if (e == NULL) 3042 return; 3043 3044 gimple *estmt = last_stmt (e->src); 3045 char buf[WIDE_INT_PRINT_BUFFER_SIZE]; 3046 print_dec (i_bound, buf, TYPE_UNSIGNED (TREE_TYPE (loop->nb_iterations)) 3047 ? UNSIGNED : SIGNED); 3048 if (warning_at (gimple_location (stmt), OPT_Waggressive_loop_optimizations, 3049 "iteration %s invokes undefined behavior", buf)) 3050 inform (gimple_location (estmt), "within this loop"); 3051 loop->warned_aggressive_loop_optimizations = true; 3052 } 3053 3054 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT 3055 is true if the loop is exited immediately after STMT, and this exit 3056 is taken at last when the STMT is executed BOUND + 1 times. 3057 REALISTIC is true if BOUND is expected to be close to the real number 3058 of iterations. UPPER is true if we are sure the loop iterates at most 3059 BOUND times. I_BOUND is a widest_int upper estimate on BOUND. */ 3060 3061 static void 3062 record_estimate (struct loop *loop, tree bound, const widest_int &i_bound, 3063 gimple *at_stmt, bool is_exit, bool realistic, bool upper) 3064 { 3065 widest_int delta; 3066 3067 if (dump_file && (dump_flags & TDF_DETAILS)) 3068 { 3069 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : ""); 3070 print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM); 3071 fprintf (dump_file, " is %sexecuted at most ", 3072 upper ? "" : "probably "); 3073 print_generic_expr (dump_file, bound, TDF_SLIM); 3074 fprintf (dump_file, " (bounded by "); 3075 print_decu (i_bound, dump_file); 3076 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num); 3077 } 3078 3079 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the 3080 real number of iterations. */ 3081 if (TREE_CODE (bound) != INTEGER_CST) 3082 realistic = false; 3083 else 3084 gcc_checking_assert (i_bound == wi::to_widest (bound)); 3085 3086 /* If we have a guaranteed upper bound, record it in the appropriate 3087 list, unless this is an !is_exit bound (i.e. undefined behavior in 3088 at_stmt) in a loop with known constant number of iterations. */ 3089 if (upper 3090 && (is_exit 3091 || loop->nb_iterations == NULL_TREE 3092 || TREE_CODE (loop->nb_iterations) != INTEGER_CST)) 3093 { 3094 struct nb_iter_bound *elt = ggc_alloc<nb_iter_bound> (); 3095 3096 elt->bound = i_bound; 3097 elt->stmt = at_stmt; 3098 elt->is_exit = is_exit; 3099 elt->next = loop->bounds; 3100 loop->bounds = elt; 3101 } 3102 3103 /* If statement is executed on every path to the loop latch, we can directly 3104 infer the upper bound on the # of iterations of the loop. */ 3105 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt))) 3106 upper = false; 3107 3108 /* Update the number of iteration estimates according to the bound. 3109 If at_stmt is an exit then the loop latch is executed at most BOUND times, 3110 otherwise it can be executed BOUND + 1 times. We will lower the estimate 3111 later if such statement must be executed on last iteration */ 3112 if (is_exit) 3113 delta = 0; 3114 else 3115 delta = 1; 3116 widest_int new_i_bound = i_bound + delta; 3117 3118 /* If an overflow occurred, ignore the result. */ 3119 if (wi::ltu_p (new_i_bound, delta)) 3120 return; 3121 3122 if (upper && !is_exit) 3123 do_warn_aggressive_loop_optimizations (loop, new_i_bound, at_stmt); 3124 record_niter_bound (loop, new_i_bound, realistic, upper); 3125 } 3126 3127 /* Records the control iv analyzed in NITER for LOOP if the iv is valid 3128 and doesn't overflow. */ 3129 3130 static void 3131 record_control_iv (struct loop *loop, struct tree_niter_desc *niter) 3132 { 3133 struct control_iv *iv; 3134 3135 if (!niter->control.base || !niter->control.step) 3136 return; 3137 3138 if (!integer_onep (niter->assumptions) || !niter->control.no_overflow) 3139 return; 3140 3141 iv = ggc_alloc<control_iv> (); 3142 iv->base = niter->control.base; 3143 iv->step = niter->control.step; 3144 iv->next = loop->control_ivs; 3145 loop->control_ivs = iv; 3146 3147 return; 3148 } 3149 3150 /* This function returns TRUE if below conditions are satisfied: 3151 1) VAR is SSA variable. 3152 2) VAR is an IV:{base, step} in its defining loop. 3153 3) IV doesn't overflow. 3154 4) Both base and step are integer constants. 3155 5) Base is the MIN/MAX value depends on IS_MIN. 3156 Store value of base to INIT correspondingly. */ 3157 3158 static bool 3159 get_cst_init_from_scev (tree var, wide_int *init, bool is_min) 3160 { 3161 if (TREE_CODE (var) != SSA_NAME) 3162 return false; 3163 3164 gimple *def_stmt = SSA_NAME_DEF_STMT (var); 3165 struct loop *loop = loop_containing_stmt (def_stmt); 3166 3167 if (loop == NULL) 3168 return false; 3169 3170 affine_iv iv; 3171 if (!simple_iv (loop, loop, var, &iv, false)) 3172 return false; 3173 3174 if (!iv.no_overflow) 3175 return false; 3176 3177 if (TREE_CODE (iv.base) != INTEGER_CST || TREE_CODE (iv.step) != INTEGER_CST) 3178 return false; 3179 3180 if (is_min == tree_int_cst_sign_bit (iv.step)) 3181 return false; 3182 3183 *init = wi::to_wide (iv.base); 3184 return true; 3185 } 3186 3187 /* Record the estimate on number of iterations of LOOP based on the fact that 3188 the induction variable BASE + STEP * i evaluated in STMT does not wrap and 3189 its values belong to the range <LOW, HIGH>. REALISTIC is true if the 3190 estimated number of iterations is expected to be close to the real one. 3191 UPPER is true if we are sure the induction variable does not wrap. */ 3192 3193 static void 3194 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple *stmt, 3195 tree low, tree high, bool realistic, bool upper) 3196 { 3197 tree niter_bound, extreme, delta; 3198 tree type = TREE_TYPE (base), unsigned_type; 3199 tree orig_base = base; 3200 3201 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step)) 3202 return; 3203 3204 if (dump_file && (dump_flags & TDF_DETAILS)) 3205 { 3206 fprintf (dump_file, "Induction variable ("); 3207 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM); 3208 fprintf (dump_file, ") "); 3209 print_generic_expr (dump_file, base, TDF_SLIM); 3210 fprintf (dump_file, " + "); 3211 print_generic_expr (dump_file, step, TDF_SLIM); 3212 fprintf (dump_file, " * iteration does not wrap in statement "); 3213 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 3214 fprintf (dump_file, " in loop %d.\n", loop->num); 3215 } 3216 3217 unsigned_type = unsigned_type_for (type); 3218 base = fold_convert (unsigned_type, base); 3219 step = fold_convert (unsigned_type, step); 3220 3221 if (tree_int_cst_sign_bit (step)) 3222 { 3223 wide_int min, max; 3224 extreme = fold_convert (unsigned_type, low); 3225 if (TREE_CODE (orig_base) == SSA_NAME 3226 && TREE_CODE (high) == INTEGER_CST 3227 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base)) 3228 && (get_range_info (orig_base, &min, &max) == VR_RANGE 3229 || get_cst_init_from_scev (orig_base, &max, false)) 3230 && wi::gts_p (wi::to_wide (high), max)) 3231 base = wide_int_to_tree (unsigned_type, max); 3232 else if (TREE_CODE (base) != INTEGER_CST 3233 && dominated_by_p (CDI_DOMINATORS, 3234 loop->latch, gimple_bb (stmt))) 3235 base = fold_convert (unsigned_type, high); 3236 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme); 3237 step = fold_build1 (NEGATE_EXPR, unsigned_type, step); 3238 } 3239 else 3240 { 3241 wide_int min, max; 3242 extreme = fold_convert (unsigned_type, high); 3243 if (TREE_CODE (orig_base) == SSA_NAME 3244 && TREE_CODE (low) == INTEGER_CST 3245 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base)) 3246 && (get_range_info (orig_base, &min, &max) == VR_RANGE 3247 || get_cst_init_from_scev (orig_base, &min, true)) 3248 && wi::gts_p (min, wi::to_wide (low))) 3249 base = wide_int_to_tree (unsigned_type, min); 3250 else if (TREE_CODE (base) != INTEGER_CST 3251 && dominated_by_p (CDI_DOMINATORS, 3252 loop->latch, gimple_bb (stmt))) 3253 base = fold_convert (unsigned_type, low); 3254 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base); 3255 } 3256 3257 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value 3258 would get out of the range. */ 3259 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step); 3260 widest_int max = derive_constant_upper_bound (niter_bound); 3261 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper); 3262 } 3263 3264 /* Determine information about number of iterations a LOOP from the index 3265 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is 3266 guaranteed to be executed in every iteration of LOOP. Callback for 3267 for_each_index. */ 3268 3269 struct ilb_data 3270 { 3271 struct loop *loop; 3272 gimple *stmt; 3273 }; 3274 3275 static bool 3276 idx_infer_loop_bounds (tree base, tree *idx, void *dta) 3277 { 3278 struct ilb_data *data = (struct ilb_data *) dta; 3279 tree ev, init, step; 3280 tree low, high, type, next; 3281 bool sign, upper = true, at_end = false; 3282 struct loop *loop = data->loop; 3283 3284 if (TREE_CODE (base) != ARRAY_REF) 3285 return true; 3286 3287 /* For arrays at the end of the structure, we are not guaranteed that they 3288 do not really extend over their declared size. However, for arrays of 3289 size greater than one, this is unlikely to be intended. */ 3290 if (array_at_struct_end_p (base)) 3291 { 3292 at_end = true; 3293 upper = false; 3294 } 3295 3296 struct loop *dloop = loop_containing_stmt (data->stmt); 3297 if (!dloop) 3298 return true; 3299 3300 ev = analyze_scalar_evolution (dloop, *idx); 3301 ev = instantiate_parameters (loop, ev); 3302 init = initial_condition (ev); 3303 step = evolution_part_in_loop_num (ev, loop->num); 3304 3305 if (!init 3306 || !step 3307 || TREE_CODE (step) != INTEGER_CST 3308 || integer_zerop (step) 3309 || tree_contains_chrecs (init, NULL) 3310 || chrec_contains_symbols_defined_in_loop (init, loop->num)) 3311 return true; 3312 3313 low = array_ref_low_bound (base); 3314 high = array_ref_up_bound (base); 3315 3316 /* The case of nonconstant bounds could be handled, but it would be 3317 complicated. */ 3318 if (TREE_CODE (low) != INTEGER_CST 3319 || !high 3320 || TREE_CODE (high) != INTEGER_CST) 3321 return true; 3322 sign = tree_int_cst_sign_bit (step); 3323 type = TREE_TYPE (step); 3324 3325 /* The array of length 1 at the end of a structure most likely extends 3326 beyond its bounds. */ 3327 if (at_end 3328 && operand_equal_p (low, high, 0)) 3329 return true; 3330 3331 /* In case the relevant bound of the array does not fit in type, or 3332 it does, but bound + step (in type) still belongs into the range of the 3333 array, the index may wrap and still stay within the range of the array 3334 (consider e.g. if the array is indexed by the full range of 3335 unsigned char). 3336 3337 To make things simpler, we require both bounds to fit into type, although 3338 there are cases where this would not be strictly necessary. */ 3339 if (!int_fits_type_p (high, type) 3340 || !int_fits_type_p (low, type)) 3341 return true; 3342 low = fold_convert (type, low); 3343 high = fold_convert (type, high); 3344 3345 if (sign) 3346 next = fold_binary (PLUS_EXPR, type, low, step); 3347 else 3348 next = fold_binary (PLUS_EXPR, type, high, step); 3349 3350 if (tree_int_cst_compare (low, next) <= 0 3351 && tree_int_cst_compare (next, high) <= 0) 3352 return true; 3353 3354 /* If access is not executed on every iteration, we must ensure that overlow 3355 may not make the access valid later. */ 3356 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt)) 3357 && scev_probably_wraps_p (NULL_TREE, 3358 initial_condition_in_loop_num (ev, loop->num), 3359 step, data->stmt, loop, true)) 3360 upper = false; 3361 3362 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, false, upper); 3363 return true; 3364 } 3365 3366 /* Determine information about number of iterations a LOOP from the bounds 3367 of arrays in the data reference REF accessed in STMT. RELIABLE is true if 3368 STMT is guaranteed to be executed in every iteration of LOOP.*/ 3369 3370 static void 3371 infer_loop_bounds_from_ref (struct loop *loop, gimple *stmt, tree ref) 3372 { 3373 struct ilb_data data; 3374 3375 data.loop = loop; 3376 data.stmt = stmt; 3377 for_each_index (&ref, idx_infer_loop_bounds, &data); 3378 } 3379 3380 /* Determine information about number of iterations of a LOOP from the way 3381 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be 3382 executed in every iteration of LOOP. */ 3383 3384 static void 3385 infer_loop_bounds_from_array (struct loop *loop, gimple *stmt) 3386 { 3387 if (is_gimple_assign (stmt)) 3388 { 3389 tree op0 = gimple_assign_lhs (stmt); 3390 tree op1 = gimple_assign_rhs1 (stmt); 3391 3392 /* For each memory access, analyze its access function 3393 and record a bound on the loop iteration domain. */ 3394 if (REFERENCE_CLASS_P (op0)) 3395 infer_loop_bounds_from_ref (loop, stmt, op0); 3396 3397 if (REFERENCE_CLASS_P (op1)) 3398 infer_loop_bounds_from_ref (loop, stmt, op1); 3399 } 3400 else if (is_gimple_call (stmt)) 3401 { 3402 tree arg, lhs; 3403 unsigned i, n = gimple_call_num_args (stmt); 3404 3405 lhs = gimple_call_lhs (stmt); 3406 if (lhs && REFERENCE_CLASS_P (lhs)) 3407 infer_loop_bounds_from_ref (loop, stmt, lhs); 3408 3409 for (i = 0; i < n; i++) 3410 { 3411 arg = gimple_call_arg (stmt, i); 3412 if (REFERENCE_CLASS_P (arg)) 3413 infer_loop_bounds_from_ref (loop, stmt, arg); 3414 } 3415 } 3416 } 3417 3418 /* Determine information about number of iterations of a LOOP from the fact 3419 that pointer arithmetics in STMT does not overflow. */ 3420 3421 static void 3422 infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple *stmt) 3423 { 3424 tree def, base, step, scev, type, low, high; 3425 tree var, ptr; 3426 3427 if (!is_gimple_assign (stmt) 3428 || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR) 3429 return; 3430 3431 def = gimple_assign_lhs (stmt); 3432 if (TREE_CODE (def) != SSA_NAME) 3433 return; 3434 3435 type = TREE_TYPE (def); 3436 if (!nowrap_type_p (type)) 3437 return; 3438 3439 ptr = gimple_assign_rhs1 (stmt); 3440 if (!expr_invariant_in_loop_p (loop, ptr)) 3441 return; 3442 3443 var = gimple_assign_rhs2 (stmt); 3444 if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var))) 3445 return; 3446 3447 struct loop *uloop = loop_containing_stmt (stmt); 3448 scev = instantiate_parameters (loop, analyze_scalar_evolution (uloop, def)); 3449 if (chrec_contains_undetermined (scev)) 3450 return; 3451 3452 base = initial_condition_in_loop_num (scev, loop->num); 3453 step = evolution_part_in_loop_num (scev, loop->num); 3454 3455 if (!base || !step 3456 || TREE_CODE (step) != INTEGER_CST 3457 || tree_contains_chrecs (base, NULL) 3458 || chrec_contains_symbols_defined_in_loop (base, loop->num)) 3459 return; 3460 3461 low = lower_bound_in_type (type, type); 3462 high = upper_bound_in_type (type, type); 3463 3464 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot 3465 produce a NULL pointer. The contrary would mean NULL points to an object, 3466 while NULL is supposed to compare unequal with the address of all objects. 3467 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a 3468 NULL pointer since that would mean wrapping, which we assume here not to 3469 happen. So, we can exclude NULL from the valid range of pointer 3470 arithmetic. */ 3471 if (flag_delete_null_pointer_checks && int_cst_value (low) == 0) 3472 low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type))); 3473 3474 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true); 3475 } 3476 3477 /* Determine information about number of iterations of a LOOP from the fact 3478 that signed arithmetics in STMT does not overflow. */ 3479 3480 static void 3481 infer_loop_bounds_from_signedness (struct loop *loop, gimple *stmt) 3482 { 3483 tree def, base, step, scev, type, low, high; 3484 3485 if (gimple_code (stmt) != GIMPLE_ASSIGN) 3486 return; 3487 3488 def = gimple_assign_lhs (stmt); 3489 3490 if (TREE_CODE (def) != SSA_NAME) 3491 return; 3492 3493 type = TREE_TYPE (def); 3494 if (!INTEGRAL_TYPE_P (type) 3495 || !TYPE_OVERFLOW_UNDEFINED (type)) 3496 return; 3497 3498 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def)); 3499 if (chrec_contains_undetermined (scev)) 3500 return; 3501 3502 base = initial_condition_in_loop_num (scev, loop->num); 3503 step = evolution_part_in_loop_num (scev, loop->num); 3504 3505 if (!base || !step 3506 || TREE_CODE (step) != INTEGER_CST 3507 || tree_contains_chrecs (base, NULL) 3508 || chrec_contains_symbols_defined_in_loop (base, loop->num)) 3509 return; 3510 3511 low = lower_bound_in_type (type, type); 3512 high = upper_bound_in_type (type, type); 3513 wide_int minv, maxv; 3514 if (get_range_info (def, &minv, &maxv) == VR_RANGE) 3515 { 3516 low = wide_int_to_tree (type, minv); 3517 high = wide_int_to_tree (type, maxv); 3518 } 3519 3520 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true); 3521 } 3522 3523 /* The following analyzers are extracting informations on the bounds 3524 of LOOP from the following undefined behaviors: 3525 3526 - data references should not access elements over the statically 3527 allocated size, 3528 3529 - signed variables should not overflow when flag_wrapv is not set. 3530 */ 3531 3532 static void 3533 infer_loop_bounds_from_undefined (struct loop *loop) 3534 { 3535 unsigned i; 3536 basic_block *bbs; 3537 gimple_stmt_iterator bsi; 3538 basic_block bb; 3539 bool reliable; 3540 3541 bbs = get_loop_body (loop); 3542 3543 for (i = 0; i < loop->num_nodes; i++) 3544 { 3545 bb = bbs[i]; 3546 3547 /* If BB is not executed in each iteration of the loop, we cannot 3548 use the operations in it to infer reliable upper bound on the 3549 # of iterations of the loop. However, we can use it as a guess. 3550 Reliable guesses come only from array bounds. */ 3551 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb); 3552 3553 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 3554 { 3555 gimple *stmt = gsi_stmt (bsi); 3556 3557 infer_loop_bounds_from_array (loop, stmt); 3558 3559 if (reliable) 3560 { 3561 infer_loop_bounds_from_signedness (loop, stmt); 3562 infer_loop_bounds_from_pointer_arith (loop, stmt); 3563 } 3564 } 3565 3566 } 3567 3568 free (bbs); 3569 } 3570 3571 /* Compare wide ints, callback for qsort. */ 3572 3573 static int 3574 wide_int_cmp (const void *p1, const void *p2) 3575 { 3576 const widest_int *d1 = (const widest_int *) p1; 3577 const widest_int *d2 = (const widest_int *) p2; 3578 return wi::cmpu (*d1, *d2); 3579 } 3580 3581 /* Return index of BOUND in BOUNDS array sorted in increasing order. 3582 Lookup by binary search. */ 3583 3584 static int 3585 bound_index (vec<widest_int> bounds, const widest_int &bound) 3586 { 3587 unsigned int end = bounds.length (); 3588 unsigned int begin = 0; 3589 3590 /* Find a matching index by means of a binary search. */ 3591 while (begin != end) 3592 { 3593 unsigned int middle = (begin + end) / 2; 3594 widest_int index = bounds[middle]; 3595 3596 if (index == bound) 3597 return middle; 3598 else if (wi::ltu_p (index, bound)) 3599 begin = middle + 1; 3600 else 3601 end = middle; 3602 } 3603 gcc_unreachable (); 3604 } 3605 3606 /* We recorded loop bounds only for statements dominating loop latch (and thus 3607 executed each loop iteration). If there are any bounds on statements not 3608 dominating the loop latch we can improve the estimate by walking the loop 3609 body and seeing if every path from loop header to loop latch contains 3610 some bounded statement. */ 3611 3612 static void 3613 discover_iteration_bound_by_body_walk (struct loop *loop) 3614 { 3615 struct nb_iter_bound *elt; 3616 auto_vec<widest_int> bounds; 3617 vec<vec<basic_block> > queues = vNULL; 3618 vec<basic_block> queue = vNULL; 3619 ptrdiff_t queue_index; 3620 ptrdiff_t latch_index = 0; 3621 3622 /* Discover what bounds may interest us. */ 3623 for (elt = loop->bounds; elt; elt = elt->next) 3624 { 3625 widest_int bound = elt->bound; 3626 3627 /* Exit terminates loop at given iteration, while non-exits produce undefined 3628 effect on the next iteration. */ 3629 if (!elt->is_exit) 3630 { 3631 bound += 1; 3632 /* If an overflow occurred, ignore the result. */ 3633 if (bound == 0) 3634 continue; 3635 } 3636 3637 if (!loop->any_upper_bound 3638 || wi::ltu_p (bound, loop->nb_iterations_upper_bound)) 3639 bounds.safe_push (bound); 3640 } 3641 3642 /* Exit early if there is nothing to do. */ 3643 if (!bounds.exists ()) 3644 return; 3645 3646 if (dump_file && (dump_flags & TDF_DETAILS)) 3647 fprintf (dump_file, " Trying to walk loop body to reduce the bound.\n"); 3648 3649 /* Sort the bounds in decreasing order. */ 3650 bounds.qsort (wide_int_cmp); 3651 3652 /* For every basic block record the lowest bound that is guaranteed to 3653 terminate the loop. */ 3654 3655 hash_map<basic_block, ptrdiff_t> bb_bounds; 3656 for (elt = loop->bounds; elt; elt = elt->next) 3657 { 3658 widest_int bound = elt->bound; 3659 if (!elt->is_exit) 3660 { 3661 bound += 1; 3662 /* If an overflow occurred, ignore the result. */ 3663 if (bound == 0) 3664 continue; 3665 } 3666 3667 if (!loop->any_upper_bound 3668 || wi::ltu_p (bound, loop->nb_iterations_upper_bound)) 3669 { 3670 ptrdiff_t index = bound_index (bounds, bound); 3671 ptrdiff_t *entry = bb_bounds.get (gimple_bb (elt->stmt)); 3672 if (!entry) 3673 bb_bounds.put (gimple_bb (elt->stmt), index); 3674 else if ((ptrdiff_t)*entry > index) 3675 *entry = index; 3676 } 3677 } 3678 3679 hash_map<basic_block, ptrdiff_t> block_priority; 3680 3681 /* Perform shortest path discovery loop->header ... loop->latch. 3682 3683 The "distance" is given by the smallest loop bound of basic block 3684 present in the path and we look for path with largest smallest bound 3685 on it. 3686 3687 To avoid the need for fibonacci heap on double ints we simply compress 3688 double ints into indexes to BOUNDS array and then represent the queue 3689 as arrays of queues for every index. 3690 Index of BOUNDS.length() means that the execution of given BB has 3691 no bounds determined. 3692 3693 VISITED is a pointer map translating basic block into smallest index 3694 it was inserted into the priority queue with. */ 3695 latch_index = -1; 3696 3697 /* Start walk in loop header with index set to infinite bound. */ 3698 queue_index = bounds.length (); 3699 queues.safe_grow_cleared (queue_index + 1); 3700 queue.safe_push (loop->header); 3701 queues[queue_index] = queue; 3702 block_priority.put (loop->header, queue_index); 3703 3704 for (; queue_index >= 0; queue_index--) 3705 { 3706 if (latch_index < queue_index) 3707 { 3708 while (queues[queue_index].length ()) 3709 { 3710 basic_block bb; 3711 ptrdiff_t bound_index = queue_index; 3712 edge e; 3713 edge_iterator ei; 3714 3715 queue = queues[queue_index]; 3716 bb = queue.pop (); 3717 3718 /* OK, we later inserted the BB with lower priority, skip it. */ 3719 if (*block_priority.get (bb) > queue_index) 3720 continue; 3721 3722 /* See if we can improve the bound. */ 3723 ptrdiff_t *entry = bb_bounds.get (bb); 3724 if (entry && *entry < bound_index) 3725 bound_index = *entry; 3726 3727 /* Insert succesors into the queue, watch for latch edge 3728 and record greatest index we saw. */ 3729 FOR_EACH_EDGE (e, ei, bb->succs) 3730 { 3731 bool insert = false; 3732 3733 if (loop_exit_edge_p (loop, e)) 3734 continue; 3735 3736 if (e == loop_latch_edge (loop) 3737 && latch_index < bound_index) 3738 latch_index = bound_index; 3739 else if (!(entry = block_priority.get (e->dest))) 3740 { 3741 insert = true; 3742 block_priority.put (e->dest, bound_index); 3743 } 3744 else if (*entry < bound_index) 3745 { 3746 insert = true; 3747 *entry = bound_index; 3748 } 3749 3750 if (insert) 3751 queues[bound_index].safe_push (e->dest); 3752 } 3753 } 3754 } 3755 queues[queue_index].release (); 3756 } 3757 3758 gcc_assert (latch_index >= 0); 3759 if ((unsigned)latch_index < bounds.length ()) 3760 { 3761 if (dump_file && (dump_flags & TDF_DETAILS)) 3762 { 3763 fprintf (dump_file, "Found better loop bound "); 3764 print_decu (bounds[latch_index], dump_file); 3765 fprintf (dump_file, "\n"); 3766 } 3767 record_niter_bound (loop, bounds[latch_index], false, true); 3768 } 3769 3770 queues.release (); 3771 } 3772 3773 /* See if every path cross the loop goes through a statement that is known 3774 to not execute at the last iteration. In that case we can decrese iteration 3775 count by 1. */ 3776 3777 static void 3778 maybe_lower_iteration_bound (struct loop *loop) 3779 { 3780 hash_set<gimple *> *not_executed_last_iteration = NULL; 3781 struct nb_iter_bound *elt; 3782 bool found_exit = false; 3783 auto_vec<basic_block> queue; 3784 bitmap visited; 3785 3786 /* Collect all statements with interesting (i.e. lower than 3787 nb_iterations_upper_bound) bound on them. 3788 3789 TODO: Due to the way record_estimate choose estimates to store, the bounds 3790 will be always nb_iterations_upper_bound-1. We can change this to record 3791 also statements not dominating the loop latch and update the walk bellow 3792 to the shortest path algorithm. */ 3793 for (elt = loop->bounds; elt; elt = elt->next) 3794 { 3795 if (!elt->is_exit 3796 && wi::ltu_p (elt->bound, loop->nb_iterations_upper_bound)) 3797 { 3798 if (!not_executed_last_iteration) 3799 not_executed_last_iteration = new hash_set<gimple *>; 3800 not_executed_last_iteration->add (elt->stmt); 3801 } 3802 } 3803 if (!not_executed_last_iteration) 3804 return; 3805 3806 /* Start DFS walk in the loop header and see if we can reach the 3807 loop latch or any of the exits (including statements with side 3808 effects that may terminate the loop otherwise) without visiting 3809 any of the statements known to have undefined effect on the last 3810 iteration. */ 3811 queue.safe_push (loop->header); 3812 visited = BITMAP_ALLOC (NULL); 3813 bitmap_set_bit (visited, loop->header->index); 3814 found_exit = false; 3815 3816 do 3817 { 3818 basic_block bb = queue.pop (); 3819 gimple_stmt_iterator gsi; 3820 bool stmt_found = false; 3821 3822 /* Loop for possible exits and statements bounding the execution. */ 3823 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 3824 { 3825 gimple *stmt = gsi_stmt (gsi); 3826 if (not_executed_last_iteration->contains (stmt)) 3827 { 3828 stmt_found = true; 3829 break; 3830 } 3831 if (gimple_has_side_effects (stmt)) 3832 { 3833 found_exit = true; 3834 break; 3835 } 3836 } 3837 if (found_exit) 3838 break; 3839 3840 /* If no bounding statement is found, continue the walk. */ 3841 if (!stmt_found) 3842 { 3843 edge e; 3844 edge_iterator ei; 3845 3846 FOR_EACH_EDGE (e, ei, bb->succs) 3847 { 3848 if (loop_exit_edge_p (loop, e) 3849 || e == loop_latch_edge (loop)) 3850 { 3851 found_exit = true; 3852 break; 3853 } 3854 if (bitmap_set_bit (visited, e->dest->index)) 3855 queue.safe_push (e->dest); 3856 } 3857 } 3858 } 3859 while (queue.length () && !found_exit); 3860 3861 /* If every path through the loop reach bounding statement before exit, 3862 then we know the last iteration of the loop will have undefined effect 3863 and we can decrease number of iterations. */ 3864 3865 if (!found_exit) 3866 { 3867 if (dump_file && (dump_flags & TDF_DETAILS)) 3868 fprintf (dump_file, "Reducing loop iteration estimate by 1; " 3869 "undefined statement must be executed at the last iteration.\n"); 3870 record_niter_bound (loop, loop->nb_iterations_upper_bound - 1, 3871 false, true); 3872 } 3873 3874 BITMAP_FREE (visited); 3875 delete not_executed_last_iteration; 3876 } 3877 3878 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P 3879 is true also use estimates derived from undefined behavior. */ 3880 3881 void 3882 estimate_numbers_of_iterations (struct loop *loop) 3883 { 3884 vec<edge> exits; 3885 tree niter, type; 3886 unsigned i; 3887 struct tree_niter_desc niter_desc; 3888 edge ex; 3889 widest_int bound; 3890 edge likely_exit; 3891 3892 /* Give up if we already have tried to compute an estimation. */ 3893 if (loop->estimate_state != EST_NOT_COMPUTED) 3894 return; 3895 3896 loop->estimate_state = EST_AVAILABLE; 3897 3898 /* If we have a measured profile, use it to estimate the number of 3899 iterations. Normally this is recorded by branch_prob right after 3900 reading the profile. In case we however found a new loop, record the 3901 information here. 3902 3903 Explicitly check for profile status so we do not report 3904 wrong prediction hitrates for guessed loop iterations heuristics. 3905 Do not recompute already recorded bounds - we ought to be better on 3906 updating iteration bounds than updating profile in general and thus 3907 recomputing iteration bounds later in the compilation process will just 3908 introduce random roundoff errors. */ 3909 if (!loop->any_estimate 3910 && loop->header->count.reliable_p ()) 3911 { 3912 gcov_type nit = expected_loop_iterations_unbounded (loop); 3913 bound = gcov_type_to_wide_int (nit); 3914 record_niter_bound (loop, bound, true, false); 3915 } 3916 3917 /* Ensure that loop->nb_iterations is computed if possible. If it turns out 3918 to be constant, we avoid undefined behavior implied bounds and instead 3919 diagnose those loops with -Waggressive-loop-optimizations. */ 3920 number_of_latch_executions (loop); 3921 3922 exits = get_loop_exit_edges (loop); 3923 likely_exit = single_likely_exit (loop); 3924 FOR_EACH_VEC_ELT (exits, i, ex) 3925 { 3926 if (!number_of_iterations_exit (loop, ex, &niter_desc, false, false)) 3927 continue; 3928 3929 niter = niter_desc.niter; 3930 type = TREE_TYPE (niter); 3931 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST) 3932 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero, 3933 build_int_cst (type, 0), 3934 niter); 3935 record_estimate (loop, niter, niter_desc.max, 3936 last_stmt (ex->src), 3937 true, ex == likely_exit, true); 3938 record_control_iv (loop, &niter_desc); 3939 } 3940 exits.release (); 3941 3942 if (flag_aggressive_loop_optimizations) 3943 infer_loop_bounds_from_undefined (loop); 3944 3945 discover_iteration_bound_by_body_walk (loop); 3946 3947 maybe_lower_iteration_bound (loop); 3948 3949 /* If we know the exact number of iterations of this loop, try to 3950 not break code with undefined behavior by not recording smaller 3951 maximum number of iterations. */ 3952 if (loop->nb_iterations 3953 && TREE_CODE (loop->nb_iterations) == INTEGER_CST) 3954 { 3955 loop->any_upper_bound = true; 3956 loop->nb_iterations_upper_bound = wi::to_widest (loop->nb_iterations); 3957 } 3958 } 3959 3960 /* Sets NIT to the estimated number of executions of the latch of the 3961 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as 3962 large as the number of iterations. If we have no reliable estimate, 3963 the function returns false, otherwise returns true. */ 3964 3965 bool 3966 estimated_loop_iterations (struct loop *loop, widest_int *nit) 3967 { 3968 /* When SCEV information is available, try to update loop iterations 3969 estimate. Otherwise just return whatever we recorded earlier. */ 3970 if (scev_initialized_p ()) 3971 estimate_numbers_of_iterations (loop); 3972 3973 return (get_estimated_loop_iterations (loop, nit)); 3974 } 3975 3976 /* Similar to estimated_loop_iterations, but returns the estimate only 3977 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate 3978 on the number of iterations of LOOP could not be derived, returns -1. */ 3979 3980 HOST_WIDE_INT 3981 estimated_loop_iterations_int (struct loop *loop) 3982 { 3983 widest_int nit; 3984 HOST_WIDE_INT hwi_nit; 3985 3986 if (!estimated_loop_iterations (loop, &nit)) 3987 return -1; 3988 3989 if (!wi::fits_shwi_p (nit)) 3990 return -1; 3991 hwi_nit = nit.to_shwi (); 3992 3993 return hwi_nit < 0 ? -1 : hwi_nit; 3994 } 3995 3996 3997 /* Sets NIT to an upper bound for the maximum number of executions of the 3998 latch of the LOOP. If we have no reliable estimate, the function returns 3999 false, otherwise returns true. */ 4000 4001 bool 4002 max_loop_iterations (struct loop *loop, widest_int *nit) 4003 { 4004 /* When SCEV information is available, try to update loop iterations 4005 estimate. Otherwise just return whatever we recorded earlier. */ 4006 if (scev_initialized_p ()) 4007 estimate_numbers_of_iterations (loop); 4008 4009 return get_max_loop_iterations (loop, nit); 4010 } 4011 4012 /* Similar to max_loop_iterations, but returns the estimate only 4013 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate 4014 on the number of iterations of LOOP could not be derived, returns -1. */ 4015 4016 HOST_WIDE_INT 4017 max_loop_iterations_int (struct loop *loop) 4018 { 4019 widest_int nit; 4020 HOST_WIDE_INT hwi_nit; 4021 4022 if (!max_loop_iterations (loop, &nit)) 4023 return -1; 4024 4025 if (!wi::fits_shwi_p (nit)) 4026 return -1; 4027 hwi_nit = nit.to_shwi (); 4028 4029 return hwi_nit < 0 ? -1 : hwi_nit; 4030 } 4031 4032 /* Sets NIT to an likely upper bound for the maximum number of executions of the 4033 latch of the LOOP. If we have no reliable estimate, the function returns 4034 false, otherwise returns true. */ 4035 4036 bool 4037 likely_max_loop_iterations (struct loop *loop, widest_int *nit) 4038 { 4039 /* When SCEV information is available, try to update loop iterations 4040 estimate. Otherwise just return whatever we recorded earlier. */ 4041 if (scev_initialized_p ()) 4042 estimate_numbers_of_iterations (loop); 4043 4044 return get_likely_max_loop_iterations (loop, nit); 4045 } 4046 4047 /* Similar to max_loop_iterations, but returns the estimate only 4048 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate 4049 on the number of iterations of LOOP could not be derived, returns -1. */ 4050 4051 HOST_WIDE_INT 4052 likely_max_loop_iterations_int (struct loop *loop) 4053 { 4054 widest_int nit; 4055 HOST_WIDE_INT hwi_nit; 4056 4057 if (!likely_max_loop_iterations (loop, &nit)) 4058 return -1; 4059 4060 if (!wi::fits_shwi_p (nit)) 4061 return -1; 4062 hwi_nit = nit.to_shwi (); 4063 4064 return hwi_nit < 0 ? -1 : hwi_nit; 4065 } 4066 4067 /* Returns an estimate for the number of executions of statements 4068 in the LOOP. For statements before the loop exit, this exceeds 4069 the number of execution of the latch by one. */ 4070 4071 HOST_WIDE_INT 4072 estimated_stmt_executions_int (struct loop *loop) 4073 { 4074 HOST_WIDE_INT nit = estimated_loop_iterations_int (loop); 4075 HOST_WIDE_INT snit; 4076 4077 if (nit == -1) 4078 return -1; 4079 4080 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1); 4081 4082 /* If the computation overflows, return -1. */ 4083 return snit < 0 ? -1 : snit; 4084 } 4085 4086 /* Sets NIT to the maximum number of executions of the latch of the 4087 LOOP, plus one. If we have no reliable estimate, the function returns 4088 false, otherwise returns true. */ 4089 4090 bool 4091 max_stmt_executions (struct loop *loop, widest_int *nit) 4092 { 4093 widest_int nit_minus_one; 4094 4095 if (!max_loop_iterations (loop, nit)) 4096 return false; 4097 4098 nit_minus_one = *nit; 4099 4100 *nit += 1; 4101 4102 return wi::gtu_p (*nit, nit_minus_one); 4103 } 4104 4105 /* Sets NIT to the estimated maximum number of executions of the latch of the 4106 LOOP, plus one. If we have no likely estimate, the function returns 4107 false, otherwise returns true. */ 4108 4109 bool 4110 likely_max_stmt_executions (struct loop *loop, widest_int *nit) 4111 { 4112 widest_int nit_minus_one; 4113 4114 if (!likely_max_loop_iterations (loop, nit)) 4115 return false; 4116 4117 nit_minus_one = *nit; 4118 4119 *nit += 1; 4120 4121 return wi::gtu_p (*nit, nit_minus_one); 4122 } 4123 4124 /* Sets NIT to the estimated number of executions of the latch of the 4125 LOOP, plus one. If we have no reliable estimate, the function returns 4126 false, otherwise returns true. */ 4127 4128 bool 4129 estimated_stmt_executions (struct loop *loop, widest_int *nit) 4130 { 4131 widest_int nit_minus_one; 4132 4133 if (!estimated_loop_iterations (loop, nit)) 4134 return false; 4135 4136 nit_minus_one = *nit; 4137 4138 *nit += 1; 4139 4140 return wi::gtu_p (*nit, nit_minus_one); 4141 } 4142 4143 /* Records estimates on numbers of iterations of loops. */ 4144 4145 void 4146 estimate_numbers_of_iterations (function *fn) 4147 { 4148 struct loop *loop; 4149 4150 /* We don't want to issue signed overflow warnings while getting 4151 loop iteration estimates. */ 4152 fold_defer_overflow_warnings (); 4153 4154 FOR_EACH_LOOP_FN (fn, loop, 0) 4155 estimate_numbers_of_iterations (loop); 4156 4157 fold_undefer_and_ignore_overflow_warnings (); 4158 } 4159 4160 /* Returns true if statement S1 dominates statement S2. */ 4161 4162 bool 4163 stmt_dominates_stmt_p (gimple *s1, gimple *s2) 4164 { 4165 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2); 4166 4167 if (!bb1 4168 || s1 == s2) 4169 return true; 4170 4171 if (bb1 == bb2) 4172 { 4173 gimple_stmt_iterator bsi; 4174 4175 if (gimple_code (s2) == GIMPLE_PHI) 4176 return false; 4177 4178 if (gimple_code (s1) == GIMPLE_PHI) 4179 return true; 4180 4181 for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi)) 4182 if (gsi_stmt (bsi) == s1) 4183 return true; 4184 4185 return false; 4186 } 4187 4188 return dominated_by_p (CDI_DOMINATORS, bb2, bb1); 4189 } 4190 4191 /* Returns true when we can prove that the number of executions of 4192 STMT in the loop is at most NITER, according to the bound on 4193 the number of executions of the statement NITER_BOUND->stmt recorded in 4194 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT. 4195 4196 ??? This code can become quite a CPU hog - we can have many bounds, 4197 and large basic block forcing stmt_dominates_stmt_p to be queried 4198 many times on a large basic blocks, so the whole thing is O(n^2) 4199 for scev_probably_wraps_p invocation (that can be done n times). 4200 4201 It would make more sense (and give better answers) to remember BB 4202 bounds computed by discover_iteration_bound_by_body_walk. */ 4203 4204 static bool 4205 n_of_executions_at_most (gimple *stmt, 4206 struct nb_iter_bound *niter_bound, 4207 tree niter) 4208 { 4209 widest_int bound = niter_bound->bound; 4210 tree nit_type = TREE_TYPE (niter), e; 4211 enum tree_code cmp; 4212 4213 gcc_assert (TYPE_UNSIGNED (nit_type)); 4214 4215 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that 4216 the number of iterations is small. */ 4217 if (!wi::fits_to_tree_p (bound, nit_type)) 4218 return false; 4219 4220 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1 4221 times. This means that: 4222 4223 -- if NITER_BOUND->is_exit is true, then everything after 4224 it at most NITER_BOUND->bound times. 4225 4226 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT 4227 is executed, then NITER_BOUND->stmt is executed as well in the same 4228 iteration then STMT is executed at most NITER_BOUND->bound + 1 times. 4229 4230 If we can determine that NITER_BOUND->stmt is always executed 4231 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times. 4232 We conclude that if both statements belong to the same 4233 basic block and STMT is before NITER_BOUND->stmt and there are no 4234 statements with side effects in between. */ 4235 4236 if (niter_bound->is_exit) 4237 { 4238 if (stmt == niter_bound->stmt 4239 || !stmt_dominates_stmt_p (niter_bound->stmt, stmt)) 4240 return false; 4241 cmp = GE_EXPR; 4242 } 4243 else 4244 { 4245 if (!stmt_dominates_stmt_p (niter_bound->stmt, stmt)) 4246 { 4247 gimple_stmt_iterator bsi; 4248 if (gimple_bb (stmt) != gimple_bb (niter_bound->stmt) 4249 || gimple_code (stmt) == GIMPLE_PHI 4250 || gimple_code (niter_bound->stmt) == GIMPLE_PHI) 4251 return false; 4252 4253 /* By stmt_dominates_stmt_p we already know that STMT appears 4254 before NITER_BOUND->STMT. Still need to test that the loop 4255 can not be terinated by a side effect in between. */ 4256 for (bsi = gsi_for_stmt (stmt); gsi_stmt (bsi) != niter_bound->stmt; 4257 gsi_next (&bsi)) 4258 if (gimple_has_side_effects (gsi_stmt (bsi))) 4259 return false; 4260 bound += 1; 4261 if (bound == 0 4262 || !wi::fits_to_tree_p (bound, nit_type)) 4263 return false; 4264 } 4265 cmp = GT_EXPR; 4266 } 4267 4268 e = fold_binary (cmp, boolean_type_node, 4269 niter, wide_int_to_tree (nit_type, bound)); 4270 return e && integer_nonzerop (e); 4271 } 4272 4273 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */ 4274 4275 bool 4276 nowrap_type_p (tree type) 4277 { 4278 if (ANY_INTEGRAL_TYPE_P (type) 4279 && TYPE_OVERFLOW_UNDEFINED (type)) 4280 return true; 4281 4282 if (POINTER_TYPE_P (type)) 4283 return true; 4284 4285 return false; 4286 } 4287 4288 /* Return true if we can prove LOOP is exited before evolution of induction 4289 variable {BASE, STEP} overflows with respect to its type bound. */ 4290 4291 static bool 4292 loop_exits_before_overflow (tree base, tree step, 4293 gimple *at_stmt, struct loop *loop) 4294 { 4295 widest_int niter; 4296 struct control_iv *civ; 4297 struct nb_iter_bound *bound; 4298 tree e, delta, step_abs, unsigned_base; 4299 tree type = TREE_TYPE (step); 4300 tree unsigned_type, valid_niter; 4301 4302 /* Don't issue signed overflow warnings. */ 4303 fold_defer_overflow_warnings (); 4304 4305 /* Compute the number of iterations before we reach the bound of the 4306 type, and verify that the loop is exited before this occurs. */ 4307 unsigned_type = unsigned_type_for (type); 4308 unsigned_base = fold_convert (unsigned_type, base); 4309 4310 if (tree_int_cst_sign_bit (step)) 4311 { 4312 tree extreme = fold_convert (unsigned_type, 4313 lower_bound_in_type (type, type)); 4314 delta = fold_build2 (MINUS_EXPR, unsigned_type, unsigned_base, extreme); 4315 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type, 4316 fold_convert (unsigned_type, step)); 4317 } 4318 else 4319 { 4320 tree extreme = fold_convert (unsigned_type, 4321 upper_bound_in_type (type, type)); 4322 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, unsigned_base); 4323 step_abs = fold_convert (unsigned_type, step); 4324 } 4325 4326 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs); 4327 4328 estimate_numbers_of_iterations (loop); 4329 4330 if (max_loop_iterations (loop, &niter) 4331 && wi::fits_to_tree_p (niter, TREE_TYPE (valid_niter)) 4332 && (e = fold_binary (GT_EXPR, boolean_type_node, valid_niter, 4333 wide_int_to_tree (TREE_TYPE (valid_niter), 4334 niter))) != NULL 4335 && integer_nonzerop (e)) 4336 { 4337 fold_undefer_and_ignore_overflow_warnings (); 4338 return true; 4339 } 4340 if (at_stmt) 4341 for (bound = loop->bounds; bound; bound = bound->next) 4342 { 4343 if (n_of_executions_at_most (at_stmt, bound, valid_niter)) 4344 { 4345 fold_undefer_and_ignore_overflow_warnings (); 4346 return true; 4347 } 4348 } 4349 fold_undefer_and_ignore_overflow_warnings (); 4350 4351 /* Try to prove loop is exited before {base, step} overflows with the 4352 help of analyzed loop control IV. This is done only for IVs with 4353 constant step because otherwise we don't have the information. */ 4354 if (TREE_CODE (step) == INTEGER_CST) 4355 { 4356 for (civ = loop->control_ivs; civ; civ = civ->next) 4357 { 4358 enum tree_code code; 4359 tree civ_type = TREE_TYPE (civ->step); 4360 4361 /* Have to consider type difference because operand_equal_p ignores 4362 that for constants. */ 4363 if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (civ_type) 4364 || element_precision (type) != element_precision (civ_type)) 4365 continue; 4366 4367 /* Only consider control IV with same step. */ 4368 if (!operand_equal_p (step, civ->step, 0)) 4369 continue; 4370 4371 /* Done proving if this is a no-overflow control IV. */ 4372 if (operand_equal_p (base, civ->base, 0)) 4373 return true; 4374 4375 /* Control IV is recorded after expanding simple operations, 4376 Here we expand base and compare it too. */ 4377 tree expanded_base = expand_simple_operations (base); 4378 if (operand_equal_p (expanded_base, civ->base, 0)) 4379 return true; 4380 4381 /* If this is a before stepping control IV, in other words, we have 4382 4383 {civ_base, step} = {base + step, step} 4384 4385 Because civ {base + step, step} doesn't overflow during loop 4386 iterations, {base, step} will not overflow if we can prove the 4387 operation "base + step" does not overflow. Specifically, we try 4388 to prove below conditions are satisfied: 4389 4390 base <= UPPER_BOUND (type) - step ;;step > 0 4391 base >= LOWER_BOUND (type) - step ;;step < 0 4392 4393 by proving the reverse conditions are false using loop's initial 4394 condition. */ 4395 if (POINTER_TYPE_P (TREE_TYPE (base))) 4396 code = POINTER_PLUS_EXPR; 4397 else 4398 code = PLUS_EXPR; 4399 4400 tree stepped = fold_build2 (code, TREE_TYPE (base), base, step); 4401 tree expanded_stepped = fold_build2 (code, TREE_TYPE (base), 4402 expanded_base, step); 4403 if (operand_equal_p (stepped, civ->base, 0) 4404 || operand_equal_p (expanded_stepped, civ->base, 0)) 4405 { 4406 tree extreme; 4407 4408 if (tree_int_cst_sign_bit (step)) 4409 { 4410 code = LT_EXPR; 4411 extreme = lower_bound_in_type (type, type); 4412 } 4413 else 4414 { 4415 code = GT_EXPR; 4416 extreme = upper_bound_in_type (type, type); 4417 } 4418 extreme = fold_build2 (MINUS_EXPR, type, extreme, step); 4419 e = fold_build2 (code, boolean_type_node, base, extreme); 4420 e = simplify_using_initial_conditions (loop, e); 4421 if (integer_zerop (e)) 4422 return true; 4423 } 4424 } 4425 } 4426 4427 return false; 4428 } 4429 4430 /* VAR is scev variable whose evolution part is constant STEP, this function 4431 proves that VAR can't overflow by using value range info. If VAR's value 4432 range is [MIN, MAX], it can be proven by: 4433 MAX + step doesn't overflow ; if step > 0 4434 or 4435 MIN + step doesn't underflow ; if step < 0. 4436 4437 We can only do this if var is computed in every loop iteration, i.e, var's 4438 definition has to dominate loop latch. Consider below example: 4439 4440 { 4441 unsigned int i; 4442 4443 <bb 3>: 4444 4445 <bb 4>: 4446 # RANGE [0, 4294967294] NONZERO 65535 4447 # i_21 = PHI <0(3), i_18(9)> 4448 if (i_21 != 0) 4449 goto <bb 6>; 4450 else 4451 goto <bb 8>; 4452 4453 <bb 6>: 4454 # RANGE [0, 65533] NONZERO 65535 4455 _6 = i_21 + 4294967295; 4456 # RANGE [0, 65533] NONZERO 65535 4457 _7 = (long unsigned int) _6; 4458 # RANGE [0, 524264] NONZERO 524280 4459 _8 = _7 * 8; 4460 # PT = nonlocal escaped 4461 _9 = a_14 + _8; 4462 *_9 = 0; 4463 4464 <bb 8>: 4465 # RANGE [1, 65535] NONZERO 65535 4466 i_18 = i_21 + 1; 4467 if (i_18 >= 65535) 4468 goto <bb 10>; 4469 else 4470 goto <bb 9>; 4471 4472 <bb 9>: 4473 goto <bb 4>; 4474 4475 <bb 10>: 4476 return; 4477 } 4478 4479 VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we 4480 can't use _6 to prove no-overlfow for _7. In fact, var _7 takes value 4481 sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than 4482 (4294967295, 4294967296, ...). */ 4483 4484 static bool 4485 scev_var_range_cant_overflow (tree var, tree step, struct loop *loop) 4486 { 4487 tree type; 4488 wide_int minv, maxv, diff, step_wi; 4489 enum value_range_type rtype; 4490 4491 if (TREE_CODE (step) != INTEGER_CST || !INTEGRAL_TYPE_P (TREE_TYPE (var))) 4492 return false; 4493 4494 /* Check if VAR evaluates in every loop iteration. It's not the case 4495 if VAR is default definition or does not dominate loop's latch. */ 4496 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var)); 4497 if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb)) 4498 return false; 4499 4500 rtype = get_range_info (var, &minv, &maxv); 4501 if (rtype != VR_RANGE) 4502 return false; 4503 4504 /* VAR is a scev whose evolution part is STEP and value range info 4505 is [MIN, MAX], we can prove its no-overflowness by conditions: 4506 4507 type_MAX - MAX >= step ; if step > 0 4508 MIN - type_MIN >= |step| ; if step < 0. 4509 4510 Or VAR must take value outside of value range, which is not true. */ 4511 step_wi = wi::to_wide (step); 4512 type = TREE_TYPE (var); 4513 if (tree_int_cst_sign_bit (step)) 4514 { 4515 diff = minv - wi::to_wide (lower_bound_in_type (type, type)); 4516 step_wi = - step_wi; 4517 } 4518 else 4519 diff = wi::to_wide (upper_bound_in_type (type, type)) - maxv; 4520 4521 return (wi::geu_p (diff, step_wi)); 4522 } 4523 4524 /* Return false only when the induction variable BASE + STEP * I is 4525 known to not overflow: i.e. when the number of iterations is small 4526 enough with respect to the step and initial condition in order to 4527 keep the evolution confined in TYPEs bounds. Return true when the 4528 iv is known to overflow or when the property is not computable. 4529 4530 USE_OVERFLOW_SEMANTICS is true if this function should assume that 4531 the rules for overflow of the given language apply (e.g., that signed 4532 arithmetics in C does not overflow). 4533 4534 If VAR is a ssa variable, this function also returns false if VAR can 4535 be proven not overflow with value range info. */ 4536 4537 bool 4538 scev_probably_wraps_p (tree var, tree base, tree step, 4539 gimple *at_stmt, struct loop *loop, 4540 bool use_overflow_semantics) 4541 { 4542 /* FIXME: We really need something like 4543 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html. 4544 4545 We used to test for the following situation that frequently appears 4546 during address arithmetics: 4547 4548 D.1621_13 = (long unsigned intD.4) D.1620_12; 4549 D.1622_14 = D.1621_13 * 8; 4550 D.1623_15 = (doubleD.29 *) D.1622_14; 4551 4552 And derived that the sequence corresponding to D_14 4553 can be proved to not wrap because it is used for computing a 4554 memory access; however, this is not really the case -- for example, 4555 if D_12 = (unsigned char) [254,+,1], then D_14 has values 4556 2032, 2040, 0, 8, ..., but the code is still legal. */ 4557 4558 if (chrec_contains_undetermined (base) 4559 || chrec_contains_undetermined (step)) 4560 return true; 4561 4562 if (integer_zerop (step)) 4563 return false; 4564 4565 /* If we can use the fact that signed and pointer arithmetics does not 4566 wrap, we are done. */ 4567 if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base))) 4568 return false; 4569 4570 /* To be able to use estimates on number of iterations of the loop, 4571 we must have an upper bound on the absolute value of the step. */ 4572 if (TREE_CODE (step) != INTEGER_CST) 4573 return true; 4574 4575 /* Check if var can be proven not overflow with value range info. */ 4576 if (var && TREE_CODE (var) == SSA_NAME 4577 && scev_var_range_cant_overflow (var, step, loop)) 4578 return false; 4579 4580 if (loop_exits_before_overflow (base, step, at_stmt, loop)) 4581 return false; 4582 4583 /* At this point we still don't have a proof that the iv does not 4584 overflow: give up. */ 4585 return true; 4586 } 4587 4588 /* Frees the information on upper bounds on numbers of iterations of LOOP. */ 4589 4590 void 4591 free_numbers_of_iterations_estimates (struct loop *loop) 4592 { 4593 struct control_iv *civ; 4594 struct nb_iter_bound *bound; 4595 4596 loop->nb_iterations = NULL; 4597 loop->estimate_state = EST_NOT_COMPUTED; 4598 for (bound = loop->bounds; bound;) 4599 { 4600 struct nb_iter_bound *next = bound->next; 4601 ggc_free (bound); 4602 bound = next; 4603 } 4604 loop->bounds = NULL; 4605 4606 for (civ = loop->control_ivs; civ;) 4607 { 4608 struct control_iv *next = civ->next; 4609 ggc_free (civ); 4610 civ = next; 4611 } 4612 loop->control_ivs = NULL; 4613 } 4614 4615 /* Frees the information on upper bounds on numbers of iterations of loops. */ 4616 4617 void 4618 free_numbers_of_iterations_estimates (function *fn) 4619 { 4620 struct loop *loop; 4621 4622 FOR_EACH_LOOP_FN (fn, loop, 0) 4623 free_numbers_of_iterations_estimates (loop); 4624 } 4625 4626 /* Substitute value VAL for ssa name NAME inside expressions held 4627 at LOOP. */ 4628 4629 void 4630 substitute_in_loop_info (struct loop *loop, tree name, tree val) 4631 { 4632 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val); 4633 } 4634