1 /* Rtl-level induction variable analysis. 2 Copyright (C) 2004-2013 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 /* This is a simple analysis of induction variables of the loop. The major use 21 is for determining the number of iterations of a loop for loop unrolling, 22 doloop optimization and branch prediction. The iv information is computed 23 on demand. 24 25 Induction variables are analyzed by walking the use-def chains. When 26 a basic induction variable (biv) is found, it is cached in the bivs 27 hash table. When register is proved to be a biv, its description 28 is stored to DF_REF_DATA of the def reference. 29 30 The analysis works always with one loop -- you must call 31 iv_analysis_loop_init (loop) for it. All the other functions then work with 32 this loop. When you need to work with another loop, just call 33 iv_analysis_loop_init for it. When you no longer need iv analysis, call 34 iv_analysis_done () to clean up the memory. 35 36 The available functions are: 37 38 iv_analyze (insn, reg, iv): Stores the description of the induction variable 39 corresponding to the use of register REG in INSN to IV. Returns true if 40 REG is an induction variable in INSN. false otherwise. 41 If use of REG is not found in INSN, following insns are scanned (so that 42 we may call this function on insn returned by get_condition). 43 iv_analyze_result (insn, def, iv): Stores to IV the description of the iv 44 corresponding to DEF, which is a register defined in INSN. 45 iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv 46 corresponding to expression EXPR evaluated at INSN. All registers used bu 47 EXPR must also be used in INSN. 48 */ 49 50 #include "config.h" 51 #include "system.h" 52 #include "coretypes.h" 53 #include "tm.h" 54 #include "rtl.h" 55 #include "hard-reg-set.h" 56 #include "obstack.h" 57 #include "basic-block.h" 58 #include "cfgloop.h" 59 #include "expr.h" 60 #include "intl.h" 61 #include "diagnostic-core.h" 62 #include "df.h" 63 #include "hashtab.h" 64 #include "dumpfile.h" 65 66 /* Possible return values of iv_get_reaching_def. */ 67 68 enum iv_grd_result 69 { 70 /* More than one reaching def, or reaching def that does not 71 dominate the use. */ 72 GRD_INVALID, 73 74 /* The use is trivial invariant of the loop, i.e. is not changed 75 inside the loop. */ 76 GRD_INVARIANT, 77 78 /* The use is reached by initial value and a value from the 79 previous iteration. */ 80 GRD_MAYBE_BIV, 81 82 /* The use has single dominating def. */ 83 GRD_SINGLE_DOM 84 }; 85 86 /* Information about a biv. */ 87 88 struct biv_entry 89 { 90 unsigned regno; /* The register of the biv. */ 91 struct rtx_iv iv; /* Value of the biv. */ 92 }; 93 94 static bool clean_slate = true; 95 96 static unsigned int iv_ref_table_size = 0; 97 98 /* Table of rtx_ivs indexed by the df_ref uid field. */ 99 static struct rtx_iv ** iv_ref_table; 100 101 /* Induction variable stored at the reference. */ 102 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID(REF)] 103 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID(REF)] = (IV) 104 105 /* The current loop. */ 106 107 static struct loop *current_loop; 108 109 /* Bivs of the current loop. */ 110 111 static htab_t bivs; 112 113 static bool iv_analyze_op (rtx, rtx, struct rtx_iv *); 114 115 /* Return the RTX code corresponding to the IV extend code EXTEND. */ 116 static inline enum rtx_code 117 iv_extend_to_rtx_code (enum iv_extend_code extend) 118 { 119 switch (extend) 120 { 121 case IV_SIGN_EXTEND: 122 return SIGN_EXTEND; 123 case IV_ZERO_EXTEND: 124 return ZERO_EXTEND; 125 case IV_UNKNOWN_EXTEND: 126 return UNKNOWN; 127 } 128 gcc_unreachable (); 129 } 130 131 /* Dumps information about IV to FILE. */ 132 133 extern void dump_iv_info (FILE *, struct rtx_iv *); 134 void 135 dump_iv_info (FILE *file, struct rtx_iv *iv) 136 { 137 if (!iv->base) 138 { 139 fprintf (file, "not simple"); 140 return; 141 } 142 143 if (iv->step == const0_rtx 144 && !iv->first_special) 145 fprintf (file, "invariant "); 146 147 print_rtl (file, iv->base); 148 if (iv->step != const0_rtx) 149 { 150 fprintf (file, " + "); 151 print_rtl (file, iv->step); 152 fprintf (file, " * iteration"); 153 } 154 fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode)); 155 156 if (iv->mode != iv->extend_mode) 157 fprintf (file, " %s to %s", 158 rtx_name[iv_extend_to_rtx_code (iv->extend)], 159 GET_MODE_NAME (iv->extend_mode)); 160 161 if (iv->mult != const1_rtx) 162 { 163 fprintf (file, " * "); 164 print_rtl (file, iv->mult); 165 } 166 if (iv->delta != const0_rtx) 167 { 168 fprintf (file, " + "); 169 print_rtl (file, iv->delta); 170 } 171 if (iv->first_special) 172 fprintf (file, " (first special)"); 173 } 174 175 /* Generates a subreg to get the least significant part of EXPR (in mode 176 INNER_MODE) to OUTER_MODE. */ 177 178 rtx 179 lowpart_subreg (enum machine_mode outer_mode, rtx expr, 180 enum machine_mode inner_mode) 181 { 182 return simplify_gen_subreg (outer_mode, expr, inner_mode, 183 subreg_lowpart_offset (outer_mode, inner_mode)); 184 } 185 186 static void 187 check_iv_ref_table_size (void) 188 { 189 if (iv_ref_table_size < DF_DEFS_TABLE_SIZE()) 190 { 191 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4); 192 iv_ref_table = XRESIZEVEC (struct rtx_iv *, iv_ref_table, new_size); 193 memset (&iv_ref_table[iv_ref_table_size], 0, 194 (new_size - iv_ref_table_size) * sizeof (struct rtx_iv *)); 195 iv_ref_table_size = new_size; 196 } 197 } 198 199 200 /* Checks whether REG is a well-behaved register. */ 201 202 static bool 203 simple_reg_p (rtx reg) 204 { 205 unsigned r; 206 207 if (GET_CODE (reg) == SUBREG) 208 { 209 if (!subreg_lowpart_p (reg)) 210 return false; 211 reg = SUBREG_REG (reg); 212 } 213 214 if (!REG_P (reg)) 215 return false; 216 217 r = REGNO (reg); 218 if (HARD_REGISTER_NUM_P (r)) 219 return false; 220 221 if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT) 222 return false; 223 224 return true; 225 } 226 227 /* Clears the information about ivs stored in df. */ 228 229 static void 230 clear_iv_info (void) 231 { 232 unsigned i, n_defs = DF_DEFS_TABLE_SIZE (); 233 struct rtx_iv *iv; 234 235 check_iv_ref_table_size (); 236 for (i = 0; i < n_defs; i++) 237 { 238 iv = iv_ref_table[i]; 239 if (iv) 240 { 241 free (iv); 242 iv_ref_table[i] = NULL; 243 } 244 } 245 246 htab_empty (bivs); 247 } 248 249 /* Returns hash value for biv B. */ 250 251 static hashval_t 252 biv_hash (const void *b) 253 { 254 return ((const struct biv_entry *) b)->regno; 255 } 256 257 /* Compares biv B and register R. */ 258 259 static int 260 biv_eq (const void *b, const void *r) 261 { 262 return ((const struct biv_entry *) b)->regno == REGNO ((const_rtx) r); 263 } 264 265 /* Prepare the data for an induction variable analysis of a LOOP. */ 266 267 void 268 iv_analysis_loop_init (struct loop *loop) 269 { 270 basic_block *body = get_loop_body_in_dom_order (loop), bb; 271 bitmap blocks = BITMAP_ALLOC (NULL); 272 unsigned i; 273 274 current_loop = loop; 275 276 /* Clear the information from the analysis of the previous loop. */ 277 if (clean_slate) 278 { 279 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN); 280 bivs = htab_create (10, biv_hash, biv_eq, free); 281 clean_slate = false; 282 } 283 else 284 clear_iv_info (); 285 286 for (i = 0; i < loop->num_nodes; i++) 287 { 288 bb = body[i]; 289 bitmap_set_bit (blocks, bb->index); 290 } 291 /* Get rid of the ud chains before processing the rescans. Then add 292 the problem back. */ 293 df_remove_problem (df_chain); 294 df_process_deferred_rescans (); 295 df_set_flags (DF_RD_PRUNE_DEAD_DEFS); 296 df_chain_add_problem (DF_UD_CHAIN); 297 df_note_add_problem (); 298 df_set_blocks (blocks); 299 df_analyze (); 300 if (dump_file) 301 df_dump_region (dump_file); 302 303 check_iv_ref_table_size (); 304 BITMAP_FREE (blocks); 305 free (body); 306 } 307 308 /* Finds the definition of REG that dominates loop latch and stores 309 it to DEF. Returns false if there is not a single definition 310 dominating the latch. If REG has no definition in loop, DEF 311 is set to NULL and true is returned. */ 312 313 static bool 314 latch_dominating_def (rtx reg, df_ref *def) 315 { 316 df_ref single_rd = NULL, adef; 317 unsigned regno = REGNO (reg); 318 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch); 319 320 for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = DF_REF_NEXT_REG (adef)) 321 { 322 if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef)) 323 || !bitmap_bit_p (&bb_info->out, DF_REF_ID (adef))) 324 continue; 325 326 /* More than one reaching definition. */ 327 if (single_rd) 328 return false; 329 330 if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef))) 331 return false; 332 333 single_rd = adef; 334 } 335 336 *def = single_rd; 337 return true; 338 } 339 340 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */ 341 342 static enum iv_grd_result 343 iv_get_reaching_def (rtx insn, rtx reg, df_ref *def) 344 { 345 df_ref use, adef; 346 basic_block def_bb, use_bb; 347 rtx def_insn; 348 bool dom_p; 349 350 *def = NULL; 351 if (!simple_reg_p (reg)) 352 return GRD_INVALID; 353 if (GET_CODE (reg) == SUBREG) 354 reg = SUBREG_REG (reg); 355 gcc_assert (REG_P (reg)); 356 357 use = df_find_use (insn, reg); 358 gcc_assert (use != NULL); 359 360 if (!DF_REF_CHAIN (use)) 361 return GRD_INVARIANT; 362 363 /* More than one reaching def. */ 364 if (DF_REF_CHAIN (use)->next) 365 return GRD_INVALID; 366 367 adef = DF_REF_CHAIN (use)->ref; 368 369 /* We do not handle setting only part of the register. */ 370 if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE) 371 return GRD_INVALID; 372 373 def_insn = DF_REF_INSN (adef); 374 def_bb = DF_REF_BB (adef); 375 use_bb = BLOCK_FOR_INSN (insn); 376 377 if (use_bb == def_bb) 378 dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn)); 379 else 380 dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb); 381 382 if (dom_p) 383 { 384 *def = adef; 385 return GRD_SINGLE_DOM; 386 } 387 388 /* The definition does not dominate the use. This is still OK if 389 this may be a use of a biv, i.e. if the def_bb dominates loop 390 latch. */ 391 if (just_once_each_iteration_p (current_loop, def_bb)) 392 return GRD_MAYBE_BIV; 393 394 return GRD_INVALID; 395 } 396 397 /* Sets IV to invariant CST in MODE. Always returns true (just for 398 consistency with other iv manipulation functions that may fail). */ 399 400 static bool 401 iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode) 402 { 403 if (mode == VOIDmode) 404 mode = GET_MODE (cst); 405 406 iv->mode = mode; 407 iv->base = cst; 408 iv->step = const0_rtx; 409 iv->first_special = false; 410 iv->extend = IV_UNKNOWN_EXTEND; 411 iv->extend_mode = iv->mode; 412 iv->delta = const0_rtx; 413 iv->mult = const1_rtx; 414 415 return true; 416 } 417 418 /* Evaluates application of subreg to MODE on IV. */ 419 420 static bool 421 iv_subreg (struct rtx_iv *iv, enum machine_mode mode) 422 { 423 /* If iv is invariant, just calculate the new value. */ 424 if (iv->step == const0_rtx 425 && !iv->first_special) 426 { 427 rtx val = get_iv_value (iv, const0_rtx); 428 val = lowpart_subreg (mode, val, 429 iv->extend == IV_UNKNOWN_EXTEND 430 ? iv->mode : iv->extend_mode); 431 432 iv->base = val; 433 iv->extend = IV_UNKNOWN_EXTEND; 434 iv->mode = iv->extend_mode = mode; 435 iv->delta = const0_rtx; 436 iv->mult = const1_rtx; 437 return true; 438 } 439 440 if (iv->extend_mode == mode) 441 return true; 442 443 if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode)) 444 return false; 445 446 iv->extend = IV_UNKNOWN_EXTEND; 447 iv->mode = mode; 448 449 iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta, 450 simplify_gen_binary (MULT, iv->extend_mode, 451 iv->base, iv->mult)); 452 iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult); 453 iv->mult = const1_rtx; 454 iv->delta = const0_rtx; 455 iv->first_special = false; 456 457 return true; 458 } 459 460 /* Evaluates application of EXTEND to MODE on IV. */ 461 462 static bool 463 iv_extend (struct rtx_iv *iv, enum iv_extend_code extend, enum machine_mode mode) 464 { 465 /* If iv is invariant, just calculate the new value. */ 466 if (iv->step == const0_rtx 467 && !iv->first_special) 468 { 469 rtx val = get_iv_value (iv, const0_rtx); 470 if (iv->extend_mode != iv->mode 471 && iv->extend != IV_UNKNOWN_EXTEND 472 && iv->extend != extend) 473 val = lowpart_subreg (iv->mode, val, iv->extend_mode); 474 val = simplify_gen_unary (iv_extend_to_rtx_code (extend), mode, 475 val, 476 iv->extend == extend 477 ? iv->extend_mode : iv->mode); 478 iv->base = val; 479 iv->extend = IV_UNKNOWN_EXTEND; 480 iv->mode = iv->extend_mode = mode; 481 iv->delta = const0_rtx; 482 iv->mult = const1_rtx; 483 return true; 484 } 485 486 if (mode != iv->extend_mode) 487 return false; 488 489 if (iv->extend != IV_UNKNOWN_EXTEND 490 && iv->extend != extend) 491 return false; 492 493 iv->extend = extend; 494 495 return true; 496 } 497 498 /* Evaluates negation of IV. */ 499 500 static bool 501 iv_neg (struct rtx_iv *iv) 502 { 503 if (iv->extend == IV_UNKNOWN_EXTEND) 504 { 505 iv->base = simplify_gen_unary (NEG, iv->extend_mode, 506 iv->base, iv->extend_mode); 507 iv->step = simplify_gen_unary (NEG, iv->extend_mode, 508 iv->step, iv->extend_mode); 509 } 510 else 511 { 512 iv->delta = simplify_gen_unary (NEG, iv->extend_mode, 513 iv->delta, iv->extend_mode); 514 iv->mult = simplify_gen_unary (NEG, iv->extend_mode, 515 iv->mult, iv->extend_mode); 516 } 517 518 return true; 519 } 520 521 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */ 522 523 static bool 524 iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op) 525 { 526 enum machine_mode mode; 527 rtx arg; 528 529 /* Extend the constant to extend_mode of the other operand if necessary. */ 530 if (iv0->extend == IV_UNKNOWN_EXTEND 531 && iv0->mode == iv0->extend_mode 532 && iv0->step == const0_rtx 533 && GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode)) 534 { 535 iv0->extend_mode = iv1->extend_mode; 536 iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode, 537 iv0->base, iv0->mode); 538 } 539 if (iv1->extend == IV_UNKNOWN_EXTEND 540 && iv1->mode == iv1->extend_mode 541 && iv1->step == const0_rtx 542 && GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode)) 543 { 544 iv1->extend_mode = iv0->extend_mode; 545 iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode, 546 iv1->base, iv1->mode); 547 } 548 549 mode = iv0->extend_mode; 550 if (mode != iv1->extend_mode) 551 return false; 552 553 if (iv0->extend == IV_UNKNOWN_EXTEND 554 && iv1->extend == IV_UNKNOWN_EXTEND) 555 { 556 if (iv0->mode != iv1->mode) 557 return false; 558 559 iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base); 560 iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step); 561 562 return true; 563 } 564 565 /* Handle addition of constant. */ 566 if (iv1->extend == IV_UNKNOWN_EXTEND 567 && iv1->mode == mode 568 && iv1->step == const0_rtx) 569 { 570 iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base); 571 return true; 572 } 573 574 if (iv0->extend == IV_UNKNOWN_EXTEND 575 && iv0->mode == mode 576 && iv0->step == const0_rtx) 577 { 578 arg = iv0->base; 579 *iv0 = *iv1; 580 if (op == MINUS 581 && !iv_neg (iv0)) 582 return false; 583 584 iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg); 585 return true; 586 } 587 588 return false; 589 } 590 591 /* Evaluates multiplication of IV by constant CST. */ 592 593 static bool 594 iv_mult (struct rtx_iv *iv, rtx mby) 595 { 596 enum machine_mode mode = iv->extend_mode; 597 598 if (GET_MODE (mby) != VOIDmode 599 && GET_MODE (mby) != mode) 600 return false; 601 602 if (iv->extend == IV_UNKNOWN_EXTEND) 603 { 604 iv->base = simplify_gen_binary (MULT, mode, iv->base, mby); 605 iv->step = simplify_gen_binary (MULT, mode, iv->step, mby); 606 } 607 else 608 { 609 iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby); 610 iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby); 611 } 612 613 return true; 614 } 615 616 /* Evaluates shift of IV by constant CST. */ 617 618 static bool 619 iv_shift (struct rtx_iv *iv, rtx mby) 620 { 621 enum machine_mode mode = iv->extend_mode; 622 623 if (GET_MODE (mby) != VOIDmode 624 && GET_MODE (mby) != mode) 625 return false; 626 627 if (iv->extend == IV_UNKNOWN_EXTEND) 628 { 629 iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby); 630 iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby); 631 } 632 else 633 { 634 iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby); 635 iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby); 636 } 637 638 return true; 639 } 640 641 /* The recursive part of get_biv_step. Gets the value of the single value 642 defined by DEF wrto initial value of REG inside loop, in shape described 643 at get_biv_step. */ 644 645 static bool 646 get_biv_step_1 (df_ref def, rtx reg, 647 rtx *inner_step, enum machine_mode *inner_mode, 648 enum iv_extend_code *extend, enum machine_mode outer_mode, 649 rtx *outer_step) 650 { 651 rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX; 652 rtx next, nextr, tmp; 653 enum rtx_code code; 654 rtx insn = DF_REF_INSN (def); 655 df_ref next_def; 656 enum iv_grd_result res; 657 658 set = single_set (insn); 659 if (!set) 660 return false; 661 662 rhs = find_reg_equal_equiv_note (insn); 663 if (rhs) 664 rhs = XEXP (rhs, 0); 665 else 666 rhs = SET_SRC (set); 667 668 code = GET_CODE (rhs); 669 switch (code) 670 { 671 case SUBREG: 672 case REG: 673 next = rhs; 674 break; 675 676 case PLUS: 677 case MINUS: 678 op0 = XEXP (rhs, 0); 679 op1 = XEXP (rhs, 1); 680 681 if (code == PLUS && CONSTANT_P (op0)) 682 { 683 tmp = op0; op0 = op1; op1 = tmp; 684 } 685 686 if (!simple_reg_p (op0) 687 || !CONSTANT_P (op1)) 688 return false; 689 690 if (GET_MODE (rhs) != outer_mode) 691 { 692 /* ppc64 uses expressions like 693 694 (set x:SI (plus:SI (subreg:SI y:DI) 1)). 695 696 this is equivalent to 697 698 (set x':DI (plus:DI y:DI 1)) 699 (set x:SI (subreg:SI (x':DI)). */ 700 if (GET_CODE (op0) != SUBREG) 701 return false; 702 if (GET_MODE (SUBREG_REG (op0)) != outer_mode) 703 return false; 704 } 705 706 next = op0; 707 break; 708 709 case SIGN_EXTEND: 710 case ZERO_EXTEND: 711 if (GET_MODE (rhs) != outer_mode) 712 return false; 713 714 op0 = XEXP (rhs, 0); 715 if (!simple_reg_p (op0)) 716 return false; 717 718 next = op0; 719 break; 720 721 default: 722 return false; 723 } 724 725 if (GET_CODE (next) == SUBREG) 726 { 727 if (!subreg_lowpart_p (next)) 728 return false; 729 730 nextr = SUBREG_REG (next); 731 if (GET_MODE (nextr) != outer_mode) 732 return false; 733 } 734 else 735 nextr = next; 736 737 res = iv_get_reaching_def (insn, nextr, &next_def); 738 739 if (res == GRD_INVALID || res == GRD_INVARIANT) 740 return false; 741 742 if (res == GRD_MAYBE_BIV) 743 { 744 if (!rtx_equal_p (nextr, reg)) 745 return false; 746 747 *inner_step = const0_rtx; 748 *extend = IV_UNKNOWN_EXTEND; 749 *inner_mode = outer_mode; 750 *outer_step = const0_rtx; 751 } 752 else if (!get_biv_step_1 (next_def, reg, 753 inner_step, inner_mode, extend, outer_mode, 754 outer_step)) 755 return false; 756 757 if (GET_CODE (next) == SUBREG) 758 { 759 enum machine_mode amode = GET_MODE (next); 760 761 if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode)) 762 return false; 763 764 *inner_mode = amode; 765 *inner_step = simplify_gen_binary (PLUS, outer_mode, 766 *inner_step, *outer_step); 767 *outer_step = const0_rtx; 768 *extend = IV_UNKNOWN_EXTEND; 769 } 770 771 switch (code) 772 { 773 case REG: 774 case SUBREG: 775 break; 776 777 case PLUS: 778 case MINUS: 779 if (*inner_mode == outer_mode 780 /* See comment in previous switch. */ 781 || GET_MODE (rhs) != outer_mode) 782 *inner_step = simplify_gen_binary (code, outer_mode, 783 *inner_step, op1); 784 else 785 *outer_step = simplify_gen_binary (code, outer_mode, 786 *outer_step, op1); 787 break; 788 789 case SIGN_EXTEND: 790 case ZERO_EXTEND: 791 gcc_assert (GET_MODE (op0) == *inner_mode 792 && *extend == IV_UNKNOWN_EXTEND 793 && *outer_step == const0_rtx); 794 795 *extend = (code == SIGN_EXTEND) ? IV_SIGN_EXTEND : IV_ZERO_EXTEND; 796 break; 797 798 default: 799 return false; 800 } 801 802 return true; 803 } 804 805 /* Gets the operation on register REG inside loop, in shape 806 807 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP)) 808 809 If the operation cannot be described in this shape, return false. 810 LAST_DEF is the definition of REG that dominates loop latch. */ 811 812 static bool 813 get_biv_step (df_ref last_def, rtx reg, rtx *inner_step, 814 enum machine_mode *inner_mode, enum iv_extend_code *extend, 815 enum machine_mode *outer_mode, rtx *outer_step) 816 { 817 *outer_mode = GET_MODE (reg); 818 819 if (!get_biv_step_1 (last_def, reg, 820 inner_step, inner_mode, extend, *outer_mode, 821 outer_step)) 822 return false; 823 824 gcc_assert ((*inner_mode == *outer_mode) != (*extend != IV_UNKNOWN_EXTEND)); 825 gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx); 826 827 return true; 828 } 829 830 /* Records information that DEF is induction variable IV. */ 831 832 static void 833 record_iv (df_ref def, struct rtx_iv *iv) 834 { 835 struct rtx_iv *recorded_iv = XNEW (struct rtx_iv); 836 837 *recorded_iv = *iv; 838 check_iv_ref_table_size (); 839 DF_REF_IV_SET (def, recorded_iv); 840 } 841 842 /* If DEF was already analyzed for bivness, store the description of the biv to 843 IV and return true. Otherwise return false. */ 844 845 static bool 846 analyzed_for_bivness_p (rtx def, struct rtx_iv *iv) 847 { 848 struct biv_entry *biv = 849 (struct biv_entry *) htab_find_with_hash (bivs, def, REGNO (def)); 850 851 if (!biv) 852 return false; 853 854 *iv = biv->iv; 855 return true; 856 } 857 858 static void 859 record_biv (rtx def, struct rtx_iv *iv) 860 { 861 struct biv_entry *biv = XNEW (struct biv_entry); 862 void **slot = htab_find_slot_with_hash (bivs, def, REGNO (def), INSERT); 863 864 biv->regno = REGNO (def); 865 biv->iv = *iv; 866 gcc_assert (!*slot); 867 *slot = biv; 868 } 869 870 /* Determines whether DEF is a biv and if so, stores its description 871 to *IV. */ 872 873 static bool 874 iv_analyze_biv (rtx def, struct rtx_iv *iv) 875 { 876 rtx inner_step, outer_step; 877 enum machine_mode inner_mode, outer_mode; 878 enum iv_extend_code extend; 879 df_ref last_def; 880 881 if (dump_file) 882 { 883 fprintf (dump_file, "Analyzing "); 884 print_rtl (dump_file, def); 885 fprintf (dump_file, " for bivness.\n"); 886 } 887 888 if (!REG_P (def)) 889 { 890 if (!CONSTANT_P (def)) 891 return false; 892 893 return iv_constant (iv, def, VOIDmode); 894 } 895 896 if (!latch_dominating_def (def, &last_def)) 897 { 898 if (dump_file) 899 fprintf (dump_file, " not simple.\n"); 900 return false; 901 } 902 903 if (!last_def) 904 return iv_constant (iv, def, VOIDmode); 905 906 if (analyzed_for_bivness_p (def, iv)) 907 { 908 if (dump_file) 909 fprintf (dump_file, " already analysed.\n"); 910 return iv->base != NULL_RTX; 911 } 912 913 if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend, 914 &outer_mode, &outer_step)) 915 { 916 iv->base = NULL_RTX; 917 goto end; 918 } 919 920 /* Loop transforms base to es (base + inner_step) + outer_step, 921 where es means extend of subreg between inner_mode and outer_mode. 922 The corresponding induction variable is 923 924 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */ 925 926 iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step); 927 iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step); 928 iv->mode = inner_mode; 929 iv->extend_mode = outer_mode; 930 iv->extend = extend; 931 iv->mult = const1_rtx; 932 iv->delta = outer_step; 933 iv->first_special = inner_mode != outer_mode; 934 935 end: 936 if (dump_file) 937 { 938 fprintf (dump_file, " "); 939 dump_iv_info (dump_file, iv); 940 fprintf (dump_file, "\n"); 941 } 942 943 record_biv (def, iv); 944 return iv->base != NULL_RTX; 945 } 946 947 /* Analyzes expression RHS used at INSN and stores the result to *IV. 948 The mode of the induction variable is MODE. */ 949 950 bool 951 iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv) 952 { 953 rtx mby = NULL_RTX, tmp; 954 rtx op0 = NULL_RTX, op1 = NULL_RTX; 955 struct rtx_iv iv0, iv1; 956 enum rtx_code code = GET_CODE (rhs); 957 enum machine_mode omode = mode; 958 959 iv->mode = VOIDmode; 960 iv->base = NULL_RTX; 961 iv->step = NULL_RTX; 962 963 gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode); 964 965 if (CONSTANT_P (rhs) 966 || REG_P (rhs) 967 || code == SUBREG) 968 { 969 if (!iv_analyze_op (insn, rhs, iv)) 970 return false; 971 972 if (iv->mode == VOIDmode) 973 { 974 iv->mode = mode; 975 iv->extend_mode = mode; 976 } 977 978 return true; 979 } 980 981 switch (code) 982 { 983 case REG: 984 op0 = rhs; 985 break; 986 987 case SIGN_EXTEND: 988 case ZERO_EXTEND: 989 case NEG: 990 op0 = XEXP (rhs, 0); 991 omode = GET_MODE (op0); 992 break; 993 994 case PLUS: 995 case MINUS: 996 op0 = XEXP (rhs, 0); 997 op1 = XEXP (rhs, 1); 998 break; 999 1000 case MULT: 1001 op0 = XEXP (rhs, 0); 1002 mby = XEXP (rhs, 1); 1003 if (!CONSTANT_P (mby)) 1004 { 1005 tmp = op0; 1006 op0 = mby; 1007 mby = tmp; 1008 } 1009 if (!CONSTANT_P (mby)) 1010 return false; 1011 break; 1012 1013 case ASHIFT: 1014 op0 = XEXP (rhs, 0); 1015 mby = XEXP (rhs, 1); 1016 if (!CONSTANT_P (mby)) 1017 return false; 1018 break; 1019 1020 default: 1021 return false; 1022 } 1023 1024 if (op0 1025 && !iv_analyze_expr (insn, op0, omode, &iv0)) 1026 return false; 1027 1028 if (op1 1029 && !iv_analyze_expr (insn, op1, omode, &iv1)) 1030 return false; 1031 1032 switch (code) 1033 { 1034 case SIGN_EXTEND: 1035 if (!iv_extend (&iv0, IV_SIGN_EXTEND, mode)) 1036 return false; 1037 break; 1038 1039 case ZERO_EXTEND: 1040 if (!iv_extend (&iv0, IV_ZERO_EXTEND, mode)) 1041 return false; 1042 break; 1043 1044 case NEG: 1045 if (!iv_neg (&iv0)) 1046 return false; 1047 break; 1048 1049 case PLUS: 1050 case MINUS: 1051 if (!iv_add (&iv0, &iv1, code)) 1052 return false; 1053 break; 1054 1055 case MULT: 1056 if (!iv_mult (&iv0, mby)) 1057 return false; 1058 break; 1059 1060 case ASHIFT: 1061 if (!iv_shift (&iv0, mby)) 1062 return false; 1063 break; 1064 1065 default: 1066 break; 1067 } 1068 1069 *iv = iv0; 1070 return iv->base != NULL_RTX; 1071 } 1072 1073 /* Analyzes iv DEF and stores the result to *IV. */ 1074 1075 static bool 1076 iv_analyze_def (df_ref def, struct rtx_iv *iv) 1077 { 1078 rtx insn = DF_REF_INSN (def); 1079 rtx reg = DF_REF_REG (def); 1080 rtx set, rhs; 1081 1082 if (dump_file) 1083 { 1084 fprintf (dump_file, "Analyzing def of "); 1085 print_rtl (dump_file, reg); 1086 fprintf (dump_file, " in insn "); 1087 print_rtl_single (dump_file, insn); 1088 } 1089 1090 check_iv_ref_table_size (); 1091 if (DF_REF_IV (def)) 1092 { 1093 if (dump_file) 1094 fprintf (dump_file, " already analysed.\n"); 1095 *iv = *DF_REF_IV (def); 1096 return iv->base != NULL_RTX; 1097 } 1098 1099 iv->mode = VOIDmode; 1100 iv->base = NULL_RTX; 1101 iv->step = NULL_RTX; 1102 1103 if (!REG_P (reg)) 1104 return false; 1105 1106 set = single_set (insn); 1107 if (!set) 1108 return false; 1109 1110 if (!REG_P (SET_DEST (set))) 1111 return false; 1112 1113 gcc_assert (SET_DEST (set) == reg); 1114 rhs = find_reg_equal_equiv_note (insn); 1115 if (rhs) 1116 rhs = XEXP (rhs, 0); 1117 else 1118 rhs = SET_SRC (set); 1119 1120 iv_analyze_expr (insn, rhs, GET_MODE (reg), iv); 1121 record_iv (def, iv); 1122 1123 if (dump_file) 1124 { 1125 print_rtl (dump_file, reg); 1126 fprintf (dump_file, " in insn "); 1127 print_rtl_single (dump_file, insn); 1128 fprintf (dump_file, " is "); 1129 dump_iv_info (dump_file, iv); 1130 fprintf (dump_file, "\n"); 1131 } 1132 1133 return iv->base != NULL_RTX; 1134 } 1135 1136 /* Analyzes operand OP of INSN and stores the result to *IV. */ 1137 1138 static bool 1139 iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv) 1140 { 1141 df_ref def = NULL; 1142 enum iv_grd_result res; 1143 1144 if (dump_file) 1145 { 1146 fprintf (dump_file, "Analyzing operand "); 1147 print_rtl (dump_file, op); 1148 fprintf (dump_file, " of insn "); 1149 print_rtl_single (dump_file, insn); 1150 } 1151 1152 if (function_invariant_p (op)) 1153 res = GRD_INVARIANT; 1154 else if (GET_CODE (op) == SUBREG) 1155 { 1156 if (!subreg_lowpart_p (op)) 1157 return false; 1158 1159 if (!iv_analyze_op (insn, SUBREG_REG (op), iv)) 1160 return false; 1161 1162 return iv_subreg (iv, GET_MODE (op)); 1163 } 1164 else 1165 { 1166 res = iv_get_reaching_def (insn, op, &def); 1167 if (res == GRD_INVALID) 1168 { 1169 if (dump_file) 1170 fprintf (dump_file, " not simple.\n"); 1171 return false; 1172 } 1173 } 1174 1175 if (res == GRD_INVARIANT) 1176 { 1177 iv_constant (iv, op, VOIDmode); 1178 1179 if (dump_file) 1180 { 1181 fprintf (dump_file, " "); 1182 dump_iv_info (dump_file, iv); 1183 fprintf (dump_file, "\n"); 1184 } 1185 return true; 1186 } 1187 1188 if (res == GRD_MAYBE_BIV) 1189 return iv_analyze_biv (op, iv); 1190 1191 return iv_analyze_def (def, iv); 1192 } 1193 1194 /* Analyzes value VAL at INSN and stores the result to *IV. */ 1195 1196 bool 1197 iv_analyze (rtx insn, rtx val, struct rtx_iv *iv) 1198 { 1199 rtx reg; 1200 1201 /* We must find the insn in that val is used, so that we get to UD chains. 1202 Since the function is sometimes called on result of get_condition, 1203 this does not necessarily have to be directly INSN; scan also the 1204 following insns. */ 1205 if (simple_reg_p (val)) 1206 { 1207 if (GET_CODE (val) == SUBREG) 1208 reg = SUBREG_REG (val); 1209 else 1210 reg = val; 1211 1212 while (!df_find_use (insn, reg)) 1213 insn = NEXT_INSN (insn); 1214 } 1215 1216 return iv_analyze_op (insn, val, iv); 1217 } 1218 1219 /* Analyzes definition of DEF in INSN and stores the result to IV. */ 1220 1221 bool 1222 iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv) 1223 { 1224 df_ref adef; 1225 1226 adef = df_find_def (insn, def); 1227 if (!adef) 1228 return false; 1229 1230 return iv_analyze_def (adef, iv); 1231 } 1232 1233 /* Checks whether definition of register REG in INSN is a basic induction 1234 variable. IV analysis must have been initialized (via a call to 1235 iv_analysis_loop_init) for this function to produce a result. */ 1236 1237 bool 1238 biv_p (rtx insn, rtx reg) 1239 { 1240 struct rtx_iv iv; 1241 df_ref def, last_def; 1242 1243 if (!simple_reg_p (reg)) 1244 return false; 1245 1246 def = df_find_def (insn, reg); 1247 gcc_assert (def != NULL); 1248 if (!latch_dominating_def (reg, &last_def)) 1249 return false; 1250 if (last_def != def) 1251 return false; 1252 1253 if (!iv_analyze_biv (reg, &iv)) 1254 return false; 1255 1256 return iv.step != const0_rtx; 1257 } 1258 1259 /* Calculates value of IV at ITERATION-th iteration. */ 1260 1261 rtx 1262 get_iv_value (struct rtx_iv *iv, rtx iteration) 1263 { 1264 rtx val; 1265 1266 /* We would need to generate some if_then_else patterns, and so far 1267 it is not needed anywhere. */ 1268 gcc_assert (!iv->first_special); 1269 1270 if (iv->step != const0_rtx && iteration != const0_rtx) 1271 val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base, 1272 simplify_gen_binary (MULT, iv->extend_mode, 1273 iv->step, iteration)); 1274 else 1275 val = iv->base; 1276 1277 if (iv->extend_mode == iv->mode) 1278 return val; 1279 1280 val = lowpart_subreg (iv->mode, val, iv->extend_mode); 1281 1282 if (iv->extend == IV_UNKNOWN_EXTEND) 1283 return val; 1284 1285 val = simplify_gen_unary (iv_extend_to_rtx_code (iv->extend), 1286 iv->extend_mode, val, iv->mode); 1287 val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta, 1288 simplify_gen_binary (MULT, iv->extend_mode, 1289 iv->mult, val)); 1290 1291 return val; 1292 } 1293 1294 /* Free the data for an induction variable analysis. */ 1295 1296 void 1297 iv_analysis_done (void) 1298 { 1299 if (!clean_slate) 1300 { 1301 clear_iv_info (); 1302 clean_slate = true; 1303 df_finish_pass (true); 1304 htab_delete (bivs); 1305 free (iv_ref_table); 1306 iv_ref_table = NULL; 1307 iv_ref_table_size = 0; 1308 bivs = NULL; 1309 } 1310 } 1311 1312 /* Computes inverse to X modulo (1 << MOD). */ 1313 1314 static unsigned HOST_WIDEST_INT 1315 inverse (unsigned HOST_WIDEST_INT x, int mod) 1316 { 1317 unsigned HOST_WIDEST_INT mask = 1318 ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1; 1319 unsigned HOST_WIDEST_INT rslt = 1; 1320 int i; 1321 1322 for (i = 0; i < mod - 1; i++) 1323 { 1324 rslt = (rslt * x) & mask; 1325 x = (x * x) & mask; 1326 } 1327 1328 return rslt; 1329 } 1330 1331 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */ 1332 1333 static int 1334 altered_reg_used (rtx *reg, void *alt) 1335 { 1336 if (!REG_P (*reg)) 1337 return 0; 1338 1339 return REGNO_REG_SET_P ((bitmap) alt, REGNO (*reg)); 1340 } 1341 1342 /* Marks registers altered by EXPR in set ALT. */ 1343 1344 static void 1345 mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED, void *alt) 1346 { 1347 if (GET_CODE (expr) == SUBREG) 1348 expr = SUBREG_REG (expr); 1349 if (!REG_P (expr)) 1350 return; 1351 1352 SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr)); 1353 } 1354 1355 /* Checks whether RHS is simple enough to process. */ 1356 1357 static bool 1358 simple_rhs_p (rtx rhs) 1359 { 1360 rtx op0, op1; 1361 1362 if (function_invariant_p (rhs) 1363 || (REG_P (rhs) && !HARD_REGISTER_P (rhs))) 1364 return true; 1365 1366 switch (GET_CODE (rhs)) 1367 { 1368 case PLUS: 1369 case MINUS: 1370 case AND: 1371 op0 = XEXP (rhs, 0); 1372 op1 = XEXP (rhs, 1); 1373 /* Allow reg OP const and reg OP reg. */ 1374 if (!(REG_P (op0) && !HARD_REGISTER_P (op0)) 1375 && !function_invariant_p (op0)) 1376 return false; 1377 if (!(REG_P (op1) && !HARD_REGISTER_P (op1)) 1378 && !function_invariant_p (op1)) 1379 return false; 1380 1381 return true; 1382 1383 case ASHIFT: 1384 case ASHIFTRT: 1385 case LSHIFTRT: 1386 case MULT: 1387 op0 = XEXP (rhs, 0); 1388 op1 = XEXP (rhs, 1); 1389 /* Allow reg OP const. */ 1390 if (!(REG_P (op0) && !HARD_REGISTER_P (op0))) 1391 return false; 1392 if (!function_invariant_p (op1)) 1393 return false; 1394 1395 return true; 1396 1397 default: 1398 return false; 1399 } 1400 } 1401 1402 /* If REG has a single definition, replace it with its known value in EXPR. 1403 Callback for for_each_rtx. */ 1404 1405 static int 1406 replace_single_def_regs (rtx *reg, void *expr1) 1407 { 1408 unsigned regno; 1409 df_ref adef; 1410 rtx set, src; 1411 rtx *expr = (rtx *)expr1; 1412 1413 if (!REG_P (*reg)) 1414 return 0; 1415 1416 regno = REGNO (*reg); 1417 for (;;) 1418 { 1419 rtx note; 1420 adef = DF_REG_DEF_CHAIN (regno); 1421 if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL 1422 || DF_REF_IS_ARTIFICIAL (adef)) 1423 return -1; 1424 1425 set = single_set (DF_REF_INSN (adef)); 1426 if (set == NULL || !REG_P (SET_DEST (set)) 1427 || REGNO (SET_DEST (set)) != regno) 1428 return -1; 1429 1430 note = find_reg_equal_equiv_note (DF_REF_INSN (adef)); 1431 1432 if (note && function_invariant_p (XEXP (note, 0))) 1433 { 1434 src = XEXP (note, 0); 1435 break; 1436 } 1437 src = SET_SRC (set); 1438 1439 if (REG_P (src)) 1440 { 1441 regno = REGNO (src); 1442 continue; 1443 } 1444 break; 1445 } 1446 if (!function_invariant_p (src)) 1447 return -1; 1448 1449 *expr = simplify_replace_rtx (*expr, *reg, src); 1450 return 1; 1451 } 1452 1453 /* A subroutine of simplify_using_initial_values, this function examines INSN 1454 to see if it contains a suitable set that we can use to make a replacement. 1455 If it is suitable, return true and set DEST and SRC to the lhs and rhs of 1456 the set; return false otherwise. */ 1457 1458 static bool 1459 suitable_set_for_replacement (rtx insn, rtx *dest, rtx *src) 1460 { 1461 rtx set = single_set (insn); 1462 rtx lhs = NULL_RTX, rhs; 1463 1464 if (!set) 1465 return false; 1466 1467 lhs = SET_DEST (set); 1468 if (!REG_P (lhs)) 1469 return false; 1470 1471 rhs = find_reg_equal_equiv_note (insn); 1472 if (rhs) 1473 rhs = XEXP (rhs, 0); 1474 else 1475 rhs = SET_SRC (set); 1476 1477 if (!simple_rhs_p (rhs)) 1478 return false; 1479 1480 *dest = lhs; 1481 *src = rhs; 1482 return true; 1483 } 1484 1485 /* Using the data returned by suitable_set_for_replacement, replace DEST 1486 with SRC in *EXPR and return the new expression. Also call 1487 replace_single_def_regs if the replacement changed something. */ 1488 static void 1489 replace_in_expr (rtx *expr, rtx dest, rtx src) 1490 { 1491 rtx old = *expr; 1492 *expr = simplify_replace_rtx (*expr, dest, src); 1493 if (old == *expr) 1494 return; 1495 while (for_each_rtx (expr, replace_single_def_regs, expr) != 0) 1496 continue; 1497 } 1498 1499 /* Checks whether A implies B. */ 1500 1501 static bool 1502 implies_p (rtx a, rtx b) 1503 { 1504 rtx op0, op1, opb0, opb1, r; 1505 enum machine_mode mode; 1506 1507 if (rtx_equal_p (a, b)) 1508 return true; 1509 1510 if (GET_CODE (a) == EQ) 1511 { 1512 op0 = XEXP (a, 0); 1513 op1 = XEXP (a, 1); 1514 1515 if (REG_P (op0) 1516 || (GET_CODE (op0) == SUBREG 1517 && REG_P (SUBREG_REG (op0)))) 1518 { 1519 r = simplify_replace_rtx (b, op0, op1); 1520 if (r == const_true_rtx) 1521 return true; 1522 } 1523 1524 if (REG_P (op1) 1525 || (GET_CODE (op1) == SUBREG 1526 && REG_P (SUBREG_REG (op1)))) 1527 { 1528 r = simplify_replace_rtx (b, op1, op0); 1529 if (r == const_true_rtx) 1530 return true; 1531 } 1532 } 1533 1534 if (b == const_true_rtx) 1535 return true; 1536 1537 if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE 1538 && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE) 1539 || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE 1540 && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE)) 1541 return false; 1542 1543 op0 = XEXP (a, 0); 1544 op1 = XEXP (a, 1); 1545 opb0 = XEXP (b, 0); 1546 opb1 = XEXP (b, 1); 1547 1548 mode = GET_MODE (op0); 1549 if (mode != GET_MODE (opb0)) 1550 mode = VOIDmode; 1551 else if (mode == VOIDmode) 1552 { 1553 mode = GET_MODE (op1); 1554 if (mode != GET_MODE (opb1)) 1555 mode = VOIDmode; 1556 } 1557 1558 /* A < B implies A + 1 <= B. */ 1559 if ((GET_CODE (a) == GT || GET_CODE (a) == LT) 1560 && (GET_CODE (b) == GE || GET_CODE (b) == LE)) 1561 { 1562 1563 if (GET_CODE (a) == GT) 1564 { 1565 r = op0; 1566 op0 = op1; 1567 op1 = r; 1568 } 1569 1570 if (GET_CODE (b) == GE) 1571 { 1572 r = opb0; 1573 opb0 = opb1; 1574 opb1 = r; 1575 } 1576 1577 if (SCALAR_INT_MODE_P (mode) 1578 && rtx_equal_p (op1, opb1) 1579 && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx) 1580 return true; 1581 return false; 1582 } 1583 1584 /* A < B or A > B imply A != B. TODO: Likewise 1585 A + n < B implies A != B + n if neither wraps. */ 1586 if (GET_CODE (b) == NE 1587 && (GET_CODE (a) == GT || GET_CODE (a) == GTU 1588 || GET_CODE (a) == LT || GET_CODE (a) == LTU)) 1589 { 1590 if (rtx_equal_p (op0, opb0) 1591 && rtx_equal_p (op1, opb1)) 1592 return true; 1593 } 1594 1595 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */ 1596 if (GET_CODE (a) == NE 1597 && op1 == const0_rtx) 1598 { 1599 if ((GET_CODE (b) == GTU 1600 && opb1 == const0_rtx) 1601 || (GET_CODE (b) == GEU 1602 && opb1 == const1_rtx)) 1603 return rtx_equal_p (op0, opb0); 1604 } 1605 1606 /* A != N is equivalent to A - (N + 1) <u -1. */ 1607 if (GET_CODE (a) == NE 1608 && CONST_INT_P (op1) 1609 && GET_CODE (b) == LTU 1610 && opb1 == constm1_rtx 1611 && GET_CODE (opb0) == PLUS 1612 && CONST_INT_P (XEXP (opb0, 1)) 1613 /* Avoid overflows. */ 1614 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1)) 1615 != ((unsigned HOST_WIDE_INT)1 1616 << (HOST_BITS_PER_WIDE_INT - 1)) - 1) 1617 && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1)) 1618 return rtx_equal_p (op0, XEXP (opb0, 0)); 1619 1620 /* Likewise, A != N implies A - N > 0. */ 1621 if (GET_CODE (a) == NE 1622 && CONST_INT_P (op1)) 1623 { 1624 if (GET_CODE (b) == GTU 1625 && GET_CODE (opb0) == PLUS 1626 && opb1 == const0_rtx 1627 && CONST_INT_P (XEXP (opb0, 1)) 1628 /* Avoid overflows. */ 1629 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1)) 1630 != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))) 1631 && rtx_equal_p (XEXP (opb0, 0), op0)) 1632 return INTVAL (op1) == -INTVAL (XEXP (opb0, 1)); 1633 if (GET_CODE (b) == GEU 1634 && GET_CODE (opb0) == PLUS 1635 && opb1 == const1_rtx 1636 && CONST_INT_P (XEXP (opb0, 1)) 1637 /* Avoid overflows. */ 1638 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1)) 1639 != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))) 1640 && rtx_equal_p (XEXP (opb0, 0), op0)) 1641 return INTVAL (op1) == -INTVAL (XEXP (opb0, 1)); 1642 } 1643 1644 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */ 1645 if ((GET_CODE (a) == GT || GET_CODE (a) == GE) 1646 && CONST_INT_P (op1) 1647 && ((GET_CODE (a) == GT && op1 == constm1_rtx) 1648 || INTVAL (op1) >= 0) 1649 && GET_CODE (b) == LTU 1650 && CONST_INT_P (opb1) 1651 && rtx_equal_p (op0, opb0)) 1652 return INTVAL (opb1) < 0; 1653 1654 return false; 1655 } 1656 1657 /* Canonicalizes COND so that 1658 1659 (1) Ensure that operands are ordered according to 1660 swap_commutative_operands_p. 1661 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly 1662 for GE, GEU, and LEU. */ 1663 1664 rtx 1665 canon_condition (rtx cond) 1666 { 1667 rtx tem; 1668 rtx op0, op1; 1669 enum rtx_code code; 1670 enum machine_mode mode; 1671 1672 code = GET_CODE (cond); 1673 op0 = XEXP (cond, 0); 1674 op1 = XEXP (cond, 1); 1675 1676 if (swap_commutative_operands_p (op0, op1)) 1677 { 1678 code = swap_condition (code); 1679 tem = op0; 1680 op0 = op1; 1681 op1 = tem; 1682 } 1683 1684 mode = GET_MODE (op0); 1685 if (mode == VOIDmode) 1686 mode = GET_MODE (op1); 1687 gcc_assert (mode != VOIDmode); 1688 1689 if (CONST_INT_P (op1) 1690 && GET_MODE_CLASS (mode) != MODE_CC 1691 && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT) 1692 { 1693 HOST_WIDE_INT const_val = INTVAL (op1); 1694 unsigned HOST_WIDE_INT uconst_val = const_val; 1695 unsigned HOST_WIDE_INT max_val 1696 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode); 1697 1698 switch (code) 1699 { 1700 case LE: 1701 if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1) 1702 code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0)); 1703 break; 1704 1705 /* When cross-compiling, const_val might be sign-extended from 1706 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */ 1707 case GE: 1708 if ((HOST_WIDE_INT) (const_val & max_val) 1709 != (((HOST_WIDE_INT) 1 1710 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1)))) 1711 code = GT, op1 = gen_int_mode (const_val - 1, mode); 1712 break; 1713 1714 case LEU: 1715 if (uconst_val < max_val) 1716 code = LTU, op1 = gen_int_mode (uconst_val + 1, mode); 1717 break; 1718 1719 case GEU: 1720 if (uconst_val != 0) 1721 code = GTU, op1 = gen_int_mode (uconst_val - 1, mode); 1722 break; 1723 1724 default: 1725 break; 1726 } 1727 } 1728 1729 if (op0 != XEXP (cond, 0) 1730 || op1 != XEXP (cond, 1) 1731 || code != GET_CODE (cond) 1732 || GET_MODE (cond) != SImode) 1733 cond = gen_rtx_fmt_ee (code, SImode, op0, op1); 1734 1735 return cond; 1736 } 1737 1738 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the 1739 set of altered regs. */ 1740 1741 void 1742 simplify_using_condition (rtx cond, rtx *expr, regset altered) 1743 { 1744 rtx rev, reve, exp = *expr; 1745 1746 /* If some register gets altered later, we do not really speak about its 1747 value at the time of comparison. */ 1748 if (altered 1749 && for_each_rtx (&cond, altered_reg_used, altered)) 1750 return; 1751 1752 if (GET_CODE (cond) == EQ 1753 && REG_P (XEXP (cond, 0)) && CONSTANT_P (XEXP (cond, 1))) 1754 { 1755 *expr = simplify_replace_rtx (*expr, XEXP (cond, 0), XEXP (cond, 1)); 1756 return; 1757 } 1758 1759 if (!COMPARISON_P (exp)) 1760 return; 1761 1762 rev = reversed_condition (cond); 1763 reve = reversed_condition (exp); 1764 1765 cond = canon_condition (cond); 1766 exp = canon_condition (exp); 1767 if (rev) 1768 rev = canon_condition (rev); 1769 if (reve) 1770 reve = canon_condition (reve); 1771 1772 if (rtx_equal_p (exp, cond)) 1773 { 1774 *expr = const_true_rtx; 1775 return; 1776 } 1777 1778 if (rev && rtx_equal_p (exp, rev)) 1779 { 1780 *expr = const0_rtx; 1781 return; 1782 } 1783 1784 if (implies_p (cond, exp)) 1785 { 1786 *expr = const_true_rtx; 1787 return; 1788 } 1789 1790 if (reve && implies_p (cond, reve)) 1791 { 1792 *expr = const0_rtx; 1793 return; 1794 } 1795 1796 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must 1797 be false. */ 1798 if (rev && implies_p (exp, rev)) 1799 { 1800 *expr = const0_rtx; 1801 return; 1802 } 1803 1804 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */ 1805 if (rev && reve && implies_p (reve, rev)) 1806 { 1807 *expr = const_true_rtx; 1808 return; 1809 } 1810 1811 /* We would like to have some other tests here. TODO. */ 1812 1813 return; 1814 } 1815 1816 /* Use relationship between A and *B to eventually eliminate *B. 1817 OP is the operation we consider. */ 1818 1819 static void 1820 eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b) 1821 { 1822 switch (op) 1823 { 1824 case AND: 1825 /* If A implies *B, we may replace *B by true. */ 1826 if (implies_p (a, *b)) 1827 *b = const_true_rtx; 1828 break; 1829 1830 case IOR: 1831 /* If *B implies A, we may replace *B by false. */ 1832 if (implies_p (*b, a)) 1833 *b = const0_rtx; 1834 break; 1835 1836 default: 1837 gcc_unreachable (); 1838 } 1839 } 1840 1841 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the 1842 operation we consider. */ 1843 1844 static void 1845 eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail) 1846 { 1847 rtx elt; 1848 1849 for (elt = tail; elt; elt = XEXP (elt, 1)) 1850 eliminate_implied_condition (op, *head, &XEXP (elt, 0)); 1851 for (elt = tail; elt; elt = XEXP (elt, 1)) 1852 eliminate_implied_condition (op, XEXP (elt, 0), head); 1853 } 1854 1855 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR 1856 is a list, its elements are assumed to be combined using OP. */ 1857 1858 static void 1859 simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) 1860 { 1861 bool expression_valid; 1862 rtx head, tail, insn, cond_list, last_valid_expr; 1863 rtx neutral, aggr; 1864 regset altered, this_altered; 1865 edge e; 1866 1867 if (!*expr) 1868 return; 1869 1870 if (CONSTANT_P (*expr)) 1871 return; 1872 1873 if (GET_CODE (*expr) == EXPR_LIST) 1874 { 1875 head = XEXP (*expr, 0); 1876 tail = XEXP (*expr, 1); 1877 1878 eliminate_implied_conditions (op, &head, tail); 1879 1880 switch (op) 1881 { 1882 case AND: 1883 neutral = const_true_rtx; 1884 aggr = const0_rtx; 1885 break; 1886 1887 case IOR: 1888 neutral = const0_rtx; 1889 aggr = const_true_rtx; 1890 break; 1891 1892 default: 1893 gcc_unreachable (); 1894 } 1895 1896 simplify_using_initial_values (loop, UNKNOWN, &head); 1897 if (head == aggr) 1898 { 1899 XEXP (*expr, 0) = aggr; 1900 XEXP (*expr, 1) = NULL_RTX; 1901 return; 1902 } 1903 else if (head == neutral) 1904 { 1905 *expr = tail; 1906 simplify_using_initial_values (loop, op, expr); 1907 return; 1908 } 1909 simplify_using_initial_values (loop, op, &tail); 1910 1911 if (tail && XEXP (tail, 0) == aggr) 1912 { 1913 *expr = tail; 1914 return; 1915 } 1916 1917 XEXP (*expr, 0) = head; 1918 XEXP (*expr, 1) = tail; 1919 return; 1920 } 1921 1922 gcc_assert (op == UNKNOWN); 1923 1924 for (;;) 1925 if (for_each_rtx (expr, replace_single_def_regs, expr) == 0) 1926 break; 1927 if (CONSTANT_P (*expr)) 1928 return; 1929 1930 e = loop_preheader_edge (loop); 1931 if (e->src == ENTRY_BLOCK_PTR) 1932 return; 1933 1934 altered = ALLOC_REG_SET (®_obstack); 1935 this_altered = ALLOC_REG_SET (®_obstack); 1936 1937 expression_valid = true; 1938 last_valid_expr = *expr; 1939 cond_list = NULL_RTX; 1940 while (1) 1941 { 1942 insn = BB_END (e->src); 1943 if (any_condjump_p (insn)) 1944 { 1945 rtx cond = get_condition (BB_END (e->src), NULL, false, true); 1946 1947 if (cond && (e->flags & EDGE_FALLTHRU)) 1948 cond = reversed_condition (cond); 1949 if (cond) 1950 { 1951 rtx old = *expr; 1952 simplify_using_condition (cond, expr, altered); 1953 if (old != *expr) 1954 { 1955 rtx note; 1956 if (CONSTANT_P (*expr)) 1957 goto out; 1958 for (note = cond_list; note; note = XEXP (note, 1)) 1959 { 1960 simplify_using_condition (XEXP (note, 0), expr, altered); 1961 if (CONSTANT_P (*expr)) 1962 goto out; 1963 } 1964 } 1965 cond_list = alloc_EXPR_LIST (0, cond, cond_list); 1966 } 1967 } 1968 1969 FOR_BB_INSNS_REVERSE (e->src, insn) 1970 { 1971 rtx src, dest; 1972 rtx old = *expr; 1973 1974 if (!INSN_P (insn)) 1975 continue; 1976 1977 CLEAR_REG_SET (this_altered); 1978 note_stores (PATTERN (insn), mark_altered, this_altered); 1979 if (CALL_P (insn)) 1980 { 1981 /* Kill all call clobbered registers. */ 1982 unsigned int i; 1983 hard_reg_set_iterator hrsi; 1984 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call, 1985 0, i, hrsi) 1986 SET_REGNO_REG_SET (this_altered, i); 1987 } 1988 1989 if (suitable_set_for_replacement (insn, &dest, &src)) 1990 { 1991 rtx *pnote, *pnote_next; 1992 1993 replace_in_expr (expr, dest, src); 1994 if (CONSTANT_P (*expr)) 1995 goto out; 1996 1997 for (pnote = &cond_list; *pnote; pnote = pnote_next) 1998 { 1999 rtx note = *pnote; 2000 rtx old_cond = XEXP (note, 0); 2001 2002 pnote_next = &XEXP (note, 1); 2003 replace_in_expr (&XEXP (note, 0), dest, src); 2004 2005 /* We can no longer use a condition that has been simplified 2006 to a constant, and simplify_using_condition will abort if 2007 we try. */ 2008 if (CONSTANT_P (XEXP (note, 0))) 2009 { 2010 *pnote = *pnote_next; 2011 pnote_next = pnote; 2012 free_EXPR_LIST_node (note); 2013 } 2014 /* Retry simplifications with this condition if either the 2015 expression or the condition changed. */ 2016 else if (old_cond != XEXP (note, 0) || old != *expr) 2017 simplify_using_condition (XEXP (note, 0), expr, altered); 2018 } 2019 } 2020 else 2021 { 2022 rtx *pnote, *pnote_next; 2023 2024 /* If we did not use this insn to make a replacement, any overlap 2025 between stores in this insn and our expression will cause the 2026 expression to become invalid. */ 2027 if (for_each_rtx (expr, altered_reg_used, this_altered)) 2028 goto out; 2029 2030 /* Likewise for the conditions. */ 2031 for (pnote = &cond_list; *pnote; pnote = pnote_next) 2032 { 2033 rtx note = *pnote; 2034 rtx old_cond = XEXP (note, 0); 2035 2036 pnote_next = &XEXP (note, 1); 2037 if (for_each_rtx (&old_cond, altered_reg_used, this_altered)) 2038 { 2039 *pnote = *pnote_next; 2040 pnote_next = pnote; 2041 free_EXPR_LIST_node (note); 2042 } 2043 } 2044 } 2045 2046 if (CONSTANT_P (*expr)) 2047 goto out; 2048 2049 IOR_REG_SET (altered, this_altered); 2050 2051 /* If the expression now contains regs that have been altered, we 2052 can't return it to the caller. However, it is still valid for 2053 further simplification, so keep searching to see if we can 2054 eventually turn it into a constant. */ 2055 if (for_each_rtx (expr, altered_reg_used, altered)) 2056 expression_valid = false; 2057 if (expression_valid) 2058 last_valid_expr = *expr; 2059 } 2060 2061 if (!single_pred_p (e->src) 2062 || single_pred (e->src) == ENTRY_BLOCK_PTR) 2063 break; 2064 e = single_pred_edge (e->src); 2065 } 2066 2067 out: 2068 free_EXPR_LIST_list (&cond_list); 2069 if (!CONSTANT_P (*expr)) 2070 *expr = last_valid_expr; 2071 FREE_REG_SET (altered); 2072 FREE_REG_SET (this_altered); 2073 } 2074 2075 /* Transforms invariant IV into MODE. Adds assumptions based on the fact 2076 that IV occurs as left operands of comparison COND and its signedness 2077 is SIGNED_P to DESC. */ 2078 2079 static void 2080 shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode, 2081 enum rtx_code cond, bool signed_p, struct niter_desc *desc) 2082 { 2083 rtx mmin, mmax, cond_over, cond_under; 2084 2085 get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax); 2086 cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode, 2087 iv->base, mmin); 2088 cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode, 2089 iv->base, mmax); 2090 2091 switch (cond) 2092 { 2093 case LE: 2094 case LT: 2095 case LEU: 2096 case LTU: 2097 if (cond_under != const0_rtx) 2098 desc->infinite = 2099 alloc_EXPR_LIST (0, cond_under, desc->infinite); 2100 if (cond_over != const0_rtx) 2101 desc->noloop_assumptions = 2102 alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions); 2103 break; 2104 2105 case GE: 2106 case GT: 2107 case GEU: 2108 case GTU: 2109 if (cond_over != const0_rtx) 2110 desc->infinite = 2111 alloc_EXPR_LIST (0, cond_over, desc->infinite); 2112 if (cond_under != const0_rtx) 2113 desc->noloop_assumptions = 2114 alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions); 2115 break; 2116 2117 case NE: 2118 if (cond_over != const0_rtx) 2119 desc->infinite = 2120 alloc_EXPR_LIST (0, cond_over, desc->infinite); 2121 if (cond_under != const0_rtx) 2122 desc->infinite = 2123 alloc_EXPR_LIST (0, cond_under, desc->infinite); 2124 break; 2125 2126 default: 2127 gcc_unreachable (); 2128 } 2129 2130 iv->mode = mode; 2131 iv->extend = signed_p ? IV_SIGN_EXTEND : IV_ZERO_EXTEND; 2132 } 2133 2134 /* Transforms IV0 and IV1 compared by COND so that they are both compared as 2135 subregs of the same mode if possible (sometimes it is necessary to add 2136 some assumptions to DESC). */ 2137 2138 static bool 2139 canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1, 2140 enum rtx_code cond, struct niter_desc *desc) 2141 { 2142 enum machine_mode comp_mode; 2143 bool signed_p; 2144 2145 /* If the ivs behave specially in the first iteration, or are 2146 added/multiplied after extending, we ignore them. */ 2147 if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx) 2148 return false; 2149 if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx) 2150 return false; 2151 2152 /* If there is some extend, it must match signedness of the comparison. */ 2153 switch (cond) 2154 { 2155 case LE: 2156 case LT: 2157 if (iv0->extend == IV_ZERO_EXTEND 2158 || iv1->extend == IV_ZERO_EXTEND) 2159 return false; 2160 signed_p = true; 2161 break; 2162 2163 case LEU: 2164 case LTU: 2165 if (iv0->extend == IV_SIGN_EXTEND 2166 || iv1->extend == IV_SIGN_EXTEND) 2167 return false; 2168 signed_p = false; 2169 break; 2170 2171 case NE: 2172 if (iv0->extend != IV_UNKNOWN_EXTEND 2173 && iv1->extend != IV_UNKNOWN_EXTEND 2174 && iv0->extend != iv1->extend) 2175 return false; 2176 2177 signed_p = false; 2178 if (iv0->extend != IV_UNKNOWN_EXTEND) 2179 signed_p = iv0->extend == IV_SIGN_EXTEND; 2180 if (iv1->extend != IV_UNKNOWN_EXTEND) 2181 signed_p = iv1->extend == IV_SIGN_EXTEND; 2182 break; 2183 2184 default: 2185 gcc_unreachable (); 2186 } 2187 2188 /* Values of both variables should be computed in the same mode. These 2189 might indeed be different, if we have comparison like 2190 2191 (compare (subreg:SI (iv0)) (subreg:SI (iv1))) 2192 2193 and iv0 and iv1 are both ivs iterating in SI mode, but calculated 2194 in different modes. This does not seem impossible to handle, but 2195 it hardly ever occurs in practice. 2196 2197 The only exception is the case when one of operands is invariant. 2198 For example pentium 3 generates comparisons like 2199 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we 2200 definitely do not want this prevent the optimization. */ 2201 comp_mode = iv0->extend_mode; 2202 if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode)) 2203 comp_mode = iv1->extend_mode; 2204 2205 if (iv0->extend_mode != comp_mode) 2206 { 2207 if (iv0->mode != iv0->extend_mode 2208 || iv0->step != const0_rtx) 2209 return false; 2210 2211 iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND, 2212 comp_mode, iv0->base, iv0->mode); 2213 iv0->extend_mode = comp_mode; 2214 } 2215 2216 if (iv1->extend_mode != comp_mode) 2217 { 2218 if (iv1->mode != iv1->extend_mode 2219 || iv1->step != const0_rtx) 2220 return false; 2221 2222 iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND, 2223 comp_mode, iv1->base, iv1->mode); 2224 iv1->extend_mode = comp_mode; 2225 } 2226 2227 /* Check that both ivs belong to a range of a single mode. If one of the 2228 operands is an invariant, we may need to shorten it into the common 2229 mode. */ 2230 if (iv0->mode == iv0->extend_mode 2231 && iv0->step == const0_rtx 2232 && iv0->mode != iv1->mode) 2233 shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc); 2234 2235 if (iv1->mode == iv1->extend_mode 2236 && iv1->step == const0_rtx 2237 && iv0->mode != iv1->mode) 2238 shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc); 2239 2240 if (iv0->mode != iv1->mode) 2241 return false; 2242 2243 desc->mode = iv0->mode; 2244 desc->signed_p = signed_p; 2245 2246 return true; 2247 } 2248 2249 /* Tries to estimate the maximum number of iterations in LOOP, and return the 2250 result. This function is called from iv_number_of_iterations with 2251 a number of fields in DESC already filled in. OLD_NITER is the original 2252 expression for the number of iterations, before we tried to simplify it. */ 2253 2254 static unsigned HOST_WIDEST_INT 2255 determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter) 2256 { 2257 rtx niter = desc->niter_expr; 2258 rtx mmin, mmax, cmp; 2259 unsigned HOST_WIDEST_INT nmax, inc; 2260 unsigned HOST_WIDEST_INT andmax = 0; 2261 2262 /* We used to look for constant operand 0 of AND, 2263 but canonicalization should always make this impossible. */ 2264 gcc_checking_assert (GET_CODE (niter) != AND 2265 || !CONST_INT_P (XEXP (niter, 0))); 2266 2267 if (GET_CODE (niter) == AND 2268 && CONST_INT_P (XEXP (niter, 1))) 2269 { 2270 andmax = UINTVAL (XEXP (niter, 1)); 2271 niter = XEXP (niter, 0); 2272 } 2273 2274 get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax); 2275 nmax = INTVAL (mmax) - INTVAL (mmin); 2276 2277 if (GET_CODE (niter) == UDIV) 2278 { 2279 if (!CONST_INT_P (XEXP (niter, 1))) 2280 return nmax; 2281 inc = INTVAL (XEXP (niter, 1)); 2282 niter = XEXP (niter, 0); 2283 } 2284 else 2285 inc = 1; 2286 2287 /* We could use a binary search here, but for now improving the upper 2288 bound by just one eliminates one important corner case. */ 2289 cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode, 2290 desc->mode, old_niter, mmax); 2291 simplify_using_initial_values (loop, UNKNOWN, &cmp); 2292 if (cmp == const_true_rtx) 2293 { 2294 nmax--; 2295 2296 if (dump_file) 2297 fprintf (dump_file, ";; improved upper bound by one.\n"); 2298 } 2299 nmax /= inc; 2300 if (andmax) 2301 nmax = MIN (nmax, andmax); 2302 if (dump_file) 2303 fprintf (dump_file, ";; Determined upper bound "HOST_WIDEST_INT_PRINT_DEC".\n", 2304 nmax); 2305 return nmax; 2306 } 2307 2308 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores 2309 the result into DESC. Very similar to determine_number_of_iterations 2310 (basically its rtl version), complicated by things like subregs. */ 2311 2312 static void 2313 iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, 2314 struct niter_desc *desc) 2315 { 2316 rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1; 2317 struct rtx_iv iv0, iv1, tmp_iv; 2318 rtx assumption, may_not_xform; 2319 enum rtx_code cond; 2320 enum machine_mode mode, comp_mode; 2321 rtx mmin, mmax, mode_mmin, mode_mmax; 2322 unsigned HOST_WIDEST_INT s, size, d, inv, max; 2323 HOST_WIDEST_INT up, down, inc, step_val; 2324 int was_sharp = false; 2325 rtx old_niter; 2326 bool step_is_pow2; 2327 2328 /* The meaning of these assumptions is this: 2329 if !assumptions 2330 then the rest of information does not have to be valid 2331 if noloop_assumptions then the loop does not roll 2332 if infinite then this exit is never used */ 2333 2334 desc->assumptions = NULL_RTX; 2335 desc->noloop_assumptions = NULL_RTX; 2336 desc->infinite = NULL_RTX; 2337 desc->simple_p = true; 2338 2339 desc->const_iter = false; 2340 desc->niter_expr = NULL_RTX; 2341 2342 cond = GET_CODE (condition); 2343 gcc_assert (COMPARISON_P (condition)); 2344 2345 mode = GET_MODE (XEXP (condition, 0)); 2346 if (mode == VOIDmode) 2347 mode = GET_MODE (XEXP (condition, 1)); 2348 /* The constant comparisons should be folded. */ 2349 gcc_assert (mode != VOIDmode); 2350 2351 /* We only handle integers or pointers. */ 2352 if (GET_MODE_CLASS (mode) != MODE_INT 2353 && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT) 2354 goto fail; 2355 2356 op0 = XEXP (condition, 0); 2357 if (!iv_analyze (insn, op0, &iv0)) 2358 goto fail; 2359 if (iv0.extend_mode == VOIDmode) 2360 iv0.mode = iv0.extend_mode = mode; 2361 2362 op1 = XEXP (condition, 1); 2363 if (!iv_analyze (insn, op1, &iv1)) 2364 goto fail; 2365 if (iv1.extend_mode == VOIDmode) 2366 iv1.mode = iv1.extend_mode = mode; 2367 2368 if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT 2369 || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT) 2370 goto fail; 2371 2372 /* Check condition and normalize it. */ 2373 2374 switch (cond) 2375 { 2376 case GE: 2377 case GT: 2378 case GEU: 2379 case GTU: 2380 tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv; 2381 cond = swap_condition (cond); 2382 break; 2383 case NE: 2384 case LE: 2385 case LEU: 2386 case LT: 2387 case LTU: 2388 break; 2389 default: 2390 goto fail; 2391 } 2392 2393 /* Handle extends. This is relatively nontrivial, so we only try in some 2394 easy cases, when we can canonicalize the ivs (possibly by adding some 2395 assumptions) to shape subreg (base + i * step). This function also fills 2396 in desc->mode and desc->signed_p. */ 2397 2398 if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc)) 2399 goto fail; 2400 2401 comp_mode = iv0.extend_mode; 2402 mode = iv0.mode; 2403 size = GET_MODE_BITSIZE (mode); 2404 get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax); 2405 mode_mmin = lowpart_subreg (mode, mmin, comp_mode); 2406 mode_mmax = lowpart_subreg (mode, mmax, comp_mode); 2407 2408 if (!CONST_INT_P (iv0.step) || !CONST_INT_P (iv1.step)) 2409 goto fail; 2410 2411 /* We can take care of the case of two induction variables chasing each other 2412 if the test is NE. I have never seen a loop using it, but still it is 2413 cool. */ 2414 if (iv0.step != const0_rtx && iv1.step != const0_rtx) 2415 { 2416 if (cond != NE) 2417 goto fail; 2418 2419 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step); 2420 iv1.step = const0_rtx; 2421 } 2422 2423 iv0.step = lowpart_subreg (mode, iv0.step, comp_mode); 2424 iv1.step = lowpart_subreg (mode, iv1.step, comp_mode); 2425 2426 /* This is either infinite loop or the one that ends immediately, depending 2427 on initial values. Unswitching should remove this kind of conditions. */ 2428 if (iv0.step == const0_rtx && iv1.step == const0_rtx) 2429 goto fail; 2430 2431 if (cond != NE) 2432 { 2433 if (iv0.step == const0_rtx) 2434 step_val = -INTVAL (iv1.step); 2435 else 2436 step_val = INTVAL (iv0.step); 2437 2438 /* Ignore loops of while (i-- < 10) type. */ 2439 if (step_val < 0) 2440 goto fail; 2441 2442 step_is_pow2 = !(step_val & (step_val - 1)); 2443 } 2444 else 2445 { 2446 /* We do not care about whether the step is power of two in this 2447 case. */ 2448 step_is_pow2 = false; 2449 step_val = 0; 2450 } 2451 2452 /* Some more condition normalization. We must record some assumptions 2453 due to overflows. */ 2454 switch (cond) 2455 { 2456 case LT: 2457 case LTU: 2458 /* We want to take care only of non-sharp relationals; this is easy, 2459 as in cases the overflow would make the transformation unsafe 2460 the loop does not roll. Seemingly it would make more sense to want 2461 to take care of sharp relationals instead, as NE is more similar to 2462 them, but the problem is that here the transformation would be more 2463 difficult due to possibly infinite loops. */ 2464 if (iv0.step == const0_rtx) 2465 { 2466 tmp = lowpart_subreg (mode, iv0.base, comp_mode); 2467 assumption = simplify_gen_relational (EQ, SImode, mode, tmp, 2468 mode_mmax); 2469 if (assumption == const_true_rtx) 2470 goto zero_iter_simplify; 2471 iv0.base = simplify_gen_binary (PLUS, comp_mode, 2472 iv0.base, const1_rtx); 2473 } 2474 else 2475 { 2476 tmp = lowpart_subreg (mode, iv1.base, comp_mode); 2477 assumption = simplify_gen_relational (EQ, SImode, mode, tmp, 2478 mode_mmin); 2479 if (assumption == const_true_rtx) 2480 goto zero_iter_simplify; 2481 iv1.base = simplify_gen_binary (PLUS, comp_mode, 2482 iv1.base, constm1_rtx); 2483 } 2484 2485 if (assumption != const0_rtx) 2486 desc->noloop_assumptions = 2487 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions); 2488 cond = (cond == LT) ? LE : LEU; 2489 2490 /* It will be useful to be able to tell the difference once more in 2491 LE -> NE reduction. */ 2492 was_sharp = true; 2493 break; 2494 default: ; 2495 } 2496 2497 /* Take care of trivially infinite loops. */ 2498 if (cond != NE) 2499 { 2500 if (iv0.step == const0_rtx) 2501 { 2502 tmp = lowpart_subreg (mode, iv0.base, comp_mode); 2503 if (rtx_equal_p (tmp, mode_mmin)) 2504 { 2505 desc->infinite = 2506 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX); 2507 /* Fill in the remaining fields somehow. */ 2508 goto zero_iter_simplify; 2509 } 2510 } 2511 else 2512 { 2513 tmp = lowpart_subreg (mode, iv1.base, comp_mode); 2514 if (rtx_equal_p (tmp, mode_mmax)) 2515 { 2516 desc->infinite = 2517 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX); 2518 /* Fill in the remaining fields somehow. */ 2519 goto zero_iter_simplify; 2520 } 2521 } 2522 } 2523 2524 /* If we can we want to take care of NE conditions instead of size 2525 comparisons, as they are much more friendly (most importantly 2526 this takes care of special handling of loops with step 1). We can 2527 do it if we first check that upper bound is greater or equal to 2528 lower bound, their difference is constant c modulo step and that 2529 there is not an overflow. */ 2530 if (cond != NE) 2531 { 2532 if (iv0.step == const0_rtx) 2533 step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode); 2534 else 2535 step = iv0.step; 2536 step = lowpart_subreg (mode, step, comp_mode); 2537 delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base); 2538 delta = lowpart_subreg (mode, delta, comp_mode); 2539 delta = simplify_gen_binary (UMOD, mode, delta, step); 2540 may_xform = const0_rtx; 2541 may_not_xform = const_true_rtx; 2542 2543 if (CONST_INT_P (delta)) 2544 { 2545 if (was_sharp && INTVAL (delta) == INTVAL (step) - 1) 2546 { 2547 /* A special case. We have transformed condition of type 2548 for (i = 0; i < 4; i += 4) 2549 into 2550 for (i = 0; i <= 3; i += 4) 2551 obviously if the test for overflow during that transformation 2552 passed, we cannot overflow here. Most importantly any 2553 loop with sharp end condition and step 1 falls into this 2554 category, so handling this case specially is definitely 2555 worth the troubles. */ 2556 may_xform = const_true_rtx; 2557 } 2558 else if (iv0.step == const0_rtx) 2559 { 2560 bound = simplify_gen_binary (PLUS, comp_mode, mmin, step); 2561 bound = simplify_gen_binary (MINUS, comp_mode, bound, delta); 2562 bound = lowpart_subreg (mode, bound, comp_mode); 2563 tmp = lowpart_subreg (mode, iv0.base, comp_mode); 2564 may_xform = simplify_gen_relational (cond, SImode, mode, 2565 bound, tmp); 2566 may_not_xform = simplify_gen_relational (reverse_condition (cond), 2567 SImode, mode, 2568 bound, tmp); 2569 } 2570 else 2571 { 2572 bound = simplify_gen_binary (MINUS, comp_mode, mmax, step); 2573 bound = simplify_gen_binary (PLUS, comp_mode, bound, delta); 2574 bound = lowpart_subreg (mode, bound, comp_mode); 2575 tmp = lowpart_subreg (mode, iv1.base, comp_mode); 2576 may_xform = simplify_gen_relational (cond, SImode, mode, 2577 tmp, bound); 2578 may_not_xform = simplify_gen_relational (reverse_condition (cond), 2579 SImode, mode, 2580 tmp, bound); 2581 } 2582 } 2583 2584 if (may_xform != const0_rtx) 2585 { 2586 /* We perform the transformation always provided that it is not 2587 completely senseless. This is OK, as we would need this assumption 2588 to determine the number of iterations anyway. */ 2589 if (may_xform != const_true_rtx) 2590 { 2591 /* If the step is a power of two and the final value we have 2592 computed overflows, the cycle is infinite. Otherwise it 2593 is nontrivial to compute the number of iterations. */ 2594 if (step_is_pow2) 2595 desc->infinite = alloc_EXPR_LIST (0, may_not_xform, 2596 desc->infinite); 2597 else 2598 desc->assumptions = alloc_EXPR_LIST (0, may_xform, 2599 desc->assumptions); 2600 } 2601 2602 /* We are going to lose some information about upper bound on 2603 number of iterations in this step, so record the information 2604 here. */ 2605 inc = INTVAL (iv0.step) - INTVAL (iv1.step); 2606 if (CONST_INT_P (iv1.base)) 2607 up = INTVAL (iv1.base); 2608 else 2609 up = INTVAL (mode_mmax) - inc; 2610 down = INTVAL (CONST_INT_P (iv0.base) 2611 ? iv0.base 2612 : mode_mmin); 2613 max = (up - down) / inc + 1; 2614 if (!desc->infinite 2615 && !desc->assumptions) 2616 record_niter_bound (loop, double_int::from_uhwi (max), 2617 false, true); 2618 2619 if (iv0.step == const0_rtx) 2620 { 2621 iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta); 2622 iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step); 2623 } 2624 else 2625 { 2626 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta); 2627 iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step); 2628 } 2629 2630 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode); 2631 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); 2632 assumption = simplify_gen_relational (reverse_condition (cond), 2633 SImode, mode, tmp0, tmp1); 2634 if (assumption == const_true_rtx) 2635 goto zero_iter_simplify; 2636 else if (assumption != const0_rtx) 2637 desc->noloop_assumptions = 2638 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions); 2639 cond = NE; 2640 } 2641 } 2642 2643 /* Count the number of iterations. */ 2644 if (cond == NE) 2645 { 2646 /* Everything we do here is just arithmetics modulo size of mode. This 2647 makes us able to do more involved computations of number of iterations 2648 than in other cases. First transform the condition into shape 2649 s * i <> c, with s positive. */ 2650 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base); 2651 iv0.base = const0_rtx; 2652 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step); 2653 iv1.step = const0_rtx; 2654 if (INTVAL (iv0.step) < 0) 2655 { 2656 iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode); 2657 iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode); 2658 } 2659 iv0.step = lowpart_subreg (mode, iv0.step, comp_mode); 2660 2661 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop 2662 is infinite. Otherwise, the number of iterations is 2663 (inverse(s/d) * (c/d)) mod (size of mode/d). */ 2664 s = INTVAL (iv0.step); d = 1; 2665 while (s % 2 != 1) 2666 { 2667 s /= 2; 2668 d *= 2; 2669 size--; 2670 } 2671 bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1); 2672 2673 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); 2674 tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d)); 2675 assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx); 2676 desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite); 2677 2678 tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d)); 2679 inv = inverse (s, size); 2680 tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode)); 2681 desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound); 2682 } 2683 else 2684 { 2685 if (iv1.step == const0_rtx) 2686 /* Condition in shape a + s * i <= b 2687 We must know that b + s does not overflow and a <= b + s and then we 2688 can compute number of iterations as (b + s - a) / s. (It might 2689 seem that we in fact could be more clever about testing the b + s 2690 overflow condition using some information about b - a mod s, 2691 but it was already taken into account during LE -> NE transform). */ 2692 { 2693 step = iv0.step; 2694 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode); 2695 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); 2696 2697 bound = simplify_gen_binary (MINUS, mode, mode_mmax, 2698 lowpart_subreg (mode, step, 2699 comp_mode)); 2700 if (step_is_pow2) 2701 { 2702 rtx t0, t1; 2703 2704 /* If s is power of 2, we know that the loop is infinite if 2705 a % s <= b % s and b + s overflows. */ 2706 assumption = simplify_gen_relational (reverse_condition (cond), 2707 SImode, mode, 2708 tmp1, bound); 2709 2710 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step); 2711 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step); 2712 tmp = simplify_gen_relational (cond, SImode, mode, t0, t1); 2713 assumption = simplify_gen_binary (AND, SImode, assumption, tmp); 2714 desc->infinite = 2715 alloc_EXPR_LIST (0, assumption, desc->infinite); 2716 } 2717 else 2718 { 2719 assumption = simplify_gen_relational (cond, SImode, mode, 2720 tmp1, bound); 2721 desc->assumptions = 2722 alloc_EXPR_LIST (0, assumption, desc->assumptions); 2723 } 2724 2725 tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step); 2726 tmp = lowpart_subreg (mode, tmp, comp_mode); 2727 assumption = simplify_gen_relational (reverse_condition (cond), 2728 SImode, mode, tmp0, tmp); 2729 2730 delta = simplify_gen_binary (PLUS, mode, tmp1, step); 2731 delta = simplify_gen_binary (MINUS, mode, delta, tmp0); 2732 } 2733 else 2734 { 2735 /* Condition in shape a <= b - s * i 2736 We must know that a - s does not overflow and a - s <= b and then 2737 we can again compute number of iterations as (b - (a - s)) / s. */ 2738 step = simplify_gen_unary (NEG, mode, iv1.step, mode); 2739 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode); 2740 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); 2741 2742 bound = simplify_gen_binary (PLUS, mode, mode_mmin, 2743 lowpart_subreg (mode, step, comp_mode)); 2744 if (step_is_pow2) 2745 { 2746 rtx t0, t1; 2747 2748 /* If s is power of 2, we know that the loop is infinite if 2749 a % s <= b % s and a - s overflows. */ 2750 assumption = simplify_gen_relational (reverse_condition (cond), 2751 SImode, mode, 2752 bound, tmp0); 2753 2754 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step); 2755 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step); 2756 tmp = simplify_gen_relational (cond, SImode, mode, t0, t1); 2757 assumption = simplify_gen_binary (AND, SImode, assumption, tmp); 2758 desc->infinite = 2759 alloc_EXPR_LIST (0, assumption, desc->infinite); 2760 } 2761 else 2762 { 2763 assumption = simplify_gen_relational (cond, SImode, mode, 2764 bound, tmp0); 2765 desc->assumptions = 2766 alloc_EXPR_LIST (0, assumption, desc->assumptions); 2767 } 2768 2769 tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step); 2770 tmp = lowpart_subreg (mode, tmp, comp_mode); 2771 assumption = simplify_gen_relational (reverse_condition (cond), 2772 SImode, mode, 2773 tmp, tmp1); 2774 delta = simplify_gen_binary (MINUS, mode, tmp0, step); 2775 delta = simplify_gen_binary (MINUS, mode, tmp1, delta); 2776 } 2777 if (assumption == const_true_rtx) 2778 goto zero_iter_simplify; 2779 else if (assumption != const0_rtx) 2780 desc->noloop_assumptions = 2781 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions); 2782 delta = simplify_gen_binary (UDIV, mode, delta, step); 2783 desc->niter_expr = delta; 2784 } 2785 2786 old_niter = desc->niter_expr; 2787 2788 simplify_using_initial_values (loop, AND, &desc->assumptions); 2789 if (desc->assumptions 2790 && XEXP (desc->assumptions, 0) == const0_rtx) 2791 goto fail; 2792 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions); 2793 simplify_using_initial_values (loop, IOR, &desc->infinite); 2794 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr); 2795 2796 /* Rerun the simplification. Consider code (created by copying loop headers) 2797 2798 i = 0; 2799 2800 if (0 < n) 2801 { 2802 do 2803 { 2804 i++; 2805 } while (i < n); 2806 } 2807 2808 The first pass determines that i = 0, the second pass uses it to eliminate 2809 noloop assumption. */ 2810 2811 simplify_using_initial_values (loop, AND, &desc->assumptions); 2812 if (desc->assumptions 2813 && XEXP (desc->assumptions, 0) == const0_rtx) 2814 goto fail; 2815 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions); 2816 simplify_using_initial_values (loop, IOR, &desc->infinite); 2817 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr); 2818 2819 if (desc->noloop_assumptions 2820 && XEXP (desc->noloop_assumptions, 0) == const_true_rtx) 2821 goto zero_iter; 2822 2823 if (CONST_INT_P (desc->niter_expr)) 2824 { 2825 unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr); 2826 2827 desc->const_iter = true; 2828 desc->niter = val & GET_MODE_MASK (desc->mode); 2829 if (!desc->infinite 2830 && !desc->assumptions) 2831 record_niter_bound (loop, double_int::from_uhwi (desc->niter), 2832 false, true); 2833 } 2834 else 2835 { 2836 max = determine_max_iter (loop, desc, old_niter); 2837 if (!max) 2838 goto zero_iter_simplify; 2839 if (!desc->infinite 2840 && !desc->assumptions) 2841 record_niter_bound (loop, double_int::from_uhwi (max), 2842 false, true); 2843 2844 /* simplify_using_initial_values does a copy propagation on the registers 2845 in the expression for the number of iterations. This prolongs life 2846 ranges of registers and increases register pressure, and usually 2847 brings no gain (and if it happens to do, the cse pass will take care 2848 of it anyway). So prevent this behavior, unless it enabled us to 2849 derive that the number of iterations is a constant. */ 2850 desc->niter_expr = old_niter; 2851 } 2852 2853 return; 2854 2855 zero_iter_simplify: 2856 /* Simplify the assumptions. */ 2857 simplify_using_initial_values (loop, AND, &desc->assumptions); 2858 if (desc->assumptions 2859 && XEXP (desc->assumptions, 0) == const0_rtx) 2860 goto fail; 2861 simplify_using_initial_values (loop, IOR, &desc->infinite); 2862 2863 /* Fallthru. */ 2864 zero_iter: 2865 desc->const_iter = true; 2866 desc->niter = 0; 2867 record_niter_bound (loop, double_int_zero, 2868 true, true); 2869 desc->noloop_assumptions = NULL_RTX; 2870 desc->niter_expr = const0_rtx; 2871 return; 2872 2873 fail: 2874 desc->simple_p = false; 2875 return; 2876 } 2877 2878 /* Checks whether E is a simple exit from LOOP and stores its description 2879 into DESC. */ 2880 2881 static void 2882 check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc) 2883 { 2884 basic_block exit_bb; 2885 rtx condition, at; 2886 edge ein; 2887 2888 exit_bb = e->src; 2889 desc->simple_p = false; 2890 2891 /* It must belong directly to the loop. */ 2892 if (exit_bb->loop_father != loop) 2893 return; 2894 2895 /* It must be tested (at least) once during any iteration. */ 2896 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb)) 2897 return; 2898 2899 /* It must end in a simple conditional jump. */ 2900 if (!any_condjump_p (BB_END (exit_bb))) 2901 return; 2902 2903 ein = EDGE_SUCC (exit_bb, 0); 2904 if (ein == e) 2905 ein = EDGE_SUCC (exit_bb, 1); 2906 2907 desc->out_edge = e; 2908 desc->in_edge = ein; 2909 2910 /* Test whether the condition is suitable. */ 2911 if (!(condition = get_condition (BB_END (ein->src), &at, false, false))) 2912 return; 2913 2914 if (ein->flags & EDGE_FALLTHRU) 2915 { 2916 condition = reversed_condition (condition); 2917 if (!condition) 2918 return; 2919 } 2920 2921 /* Check that we are able to determine number of iterations and fill 2922 in information about it. */ 2923 iv_number_of_iterations (loop, at, condition, desc); 2924 } 2925 2926 /* Finds a simple exit of LOOP and stores its description into DESC. */ 2927 2928 void 2929 find_simple_exit (struct loop *loop, struct niter_desc *desc) 2930 { 2931 unsigned i; 2932 basic_block *body; 2933 edge e; 2934 struct niter_desc act; 2935 bool any = false; 2936 edge_iterator ei; 2937 2938 desc->simple_p = false; 2939 body = get_loop_body (loop); 2940 2941 for (i = 0; i < loop->num_nodes; i++) 2942 { 2943 FOR_EACH_EDGE (e, ei, body[i]->succs) 2944 { 2945 if (flow_bb_inside_loop_p (loop, e->dest)) 2946 continue; 2947 2948 check_simple_exit (loop, e, &act); 2949 if (!act.simple_p) 2950 continue; 2951 2952 if (!any) 2953 any = true; 2954 else 2955 { 2956 /* Prefer constant iterations; the less the better. */ 2957 if (!act.const_iter 2958 || (desc->const_iter && act.niter >= desc->niter)) 2959 continue; 2960 2961 /* Also if the actual exit may be infinite, while the old one 2962 not, prefer the old one. */ 2963 if (act.infinite && !desc->infinite) 2964 continue; 2965 } 2966 2967 *desc = act; 2968 } 2969 } 2970 2971 if (dump_file) 2972 { 2973 if (desc->simple_p) 2974 { 2975 fprintf (dump_file, "Loop %d is simple:\n", loop->num); 2976 fprintf (dump_file, " simple exit %d -> %d\n", 2977 desc->out_edge->src->index, 2978 desc->out_edge->dest->index); 2979 if (desc->assumptions) 2980 { 2981 fprintf (dump_file, " assumptions: "); 2982 print_rtl (dump_file, desc->assumptions); 2983 fprintf (dump_file, "\n"); 2984 } 2985 if (desc->noloop_assumptions) 2986 { 2987 fprintf (dump_file, " does not roll if: "); 2988 print_rtl (dump_file, desc->noloop_assumptions); 2989 fprintf (dump_file, "\n"); 2990 } 2991 if (desc->infinite) 2992 { 2993 fprintf (dump_file, " infinite if: "); 2994 print_rtl (dump_file, desc->infinite); 2995 fprintf (dump_file, "\n"); 2996 } 2997 2998 fprintf (dump_file, " number of iterations: "); 2999 print_rtl (dump_file, desc->niter_expr); 3000 fprintf (dump_file, "\n"); 3001 3002 fprintf (dump_file, " upper bound: %li\n", 3003 (long)max_loop_iterations_int (loop)); 3004 fprintf (dump_file, " realistic bound: %li\n", 3005 (long)estimated_loop_iterations_int (loop)); 3006 } 3007 else 3008 fprintf (dump_file, "Loop %d is not simple.\n", loop->num); 3009 } 3010 3011 free (body); 3012 } 3013 3014 /* Creates a simple loop description of LOOP if it was not computed 3015 already. */ 3016 3017 struct niter_desc * 3018 get_simple_loop_desc (struct loop *loop) 3019 { 3020 struct niter_desc *desc = simple_loop_desc (loop); 3021 3022 if (desc) 3023 return desc; 3024 3025 /* At least desc->infinite is not always initialized by 3026 find_simple_loop_exit. */ 3027 desc = XCNEW (struct niter_desc); 3028 iv_analysis_loop_init (loop); 3029 find_simple_exit (loop, desc); 3030 loop->aux = desc; 3031 3032 if (desc->simple_p && (desc->assumptions || desc->infinite)) 3033 { 3034 const char *wording; 3035 3036 /* Assume that no overflow happens and that the loop is finite. 3037 We already warned at the tree level if we ran optimizations there. */ 3038 if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations) 3039 { 3040 if (desc->infinite) 3041 { 3042 wording = 3043 flag_unsafe_loop_optimizations 3044 ? N_("assuming that the loop is not infinite") 3045 : N_("cannot optimize possibly infinite loops"); 3046 warning (OPT_Wunsafe_loop_optimizations, "%s", 3047 gettext (wording)); 3048 } 3049 if (desc->assumptions) 3050 { 3051 wording = 3052 flag_unsafe_loop_optimizations 3053 ? N_("assuming that the loop counter does not overflow") 3054 : N_("cannot optimize loop, the loop counter may overflow"); 3055 warning (OPT_Wunsafe_loop_optimizations, "%s", 3056 gettext (wording)); 3057 } 3058 } 3059 3060 if (flag_unsafe_loop_optimizations) 3061 { 3062 desc->assumptions = NULL_RTX; 3063 desc->infinite = NULL_RTX; 3064 } 3065 } 3066 3067 return desc; 3068 } 3069 3070 /* Releases simple loop description for LOOP. */ 3071 3072 void 3073 free_simple_loop_desc (struct loop *loop) 3074 { 3075 struct niter_desc *desc = simple_loop_desc (loop); 3076 3077 if (!desc) 3078 return; 3079 3080 free (desc); 3081 loop->aux = NULL; 3082 } 3083