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