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