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