1/* RTL-level loop invariant motion. 2 Copyright (C) 2004, 2005, 2006 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 implements the loop invariant motion pass. It is very simple 22 (no calls, libcalls, etc.). This should be sufficient to cleanup things 23 like address arithmetics -- other more complicated invariants should be 24 eliminated on tree level either in tree-ssa-loop-im.c or in tree-ssa-pre.c. 25 26 We proceed loop by loop -- it is simpler than trying to handle things 27 globally and should not lose much. First we inspect all sets inside loop 28 and create a dependency graph on insns (saying "to move this insn, you must 29 also move the following insns"). 30 31 We then need to determine what to move. We estimate the number of registers 32 used and move as many invariants as possible while we still have enough free 33 registers. We prefer the expensive invariants. 34 35 Then we move the selected invariants out of the loop, creating a new 36 temporaries for them if necessary. */ 37 38#include "config.h" 39#include "system.h" 40#include "coretypes.h" 41#include "tm.h" 42#include "rtl.h" 43#include "tm_p.h" 44#include "hard-reg-set.h" 45#include "obstack.h" 46#include "basic-block.h" 47#include "cfgloop.h" 48#include "expr.h" 49#include "recog.h" 50#include "output.h" 51#include "function.h" 52#include "flags.h" 53#include "df.h" 54#include "hashtab.h" 55#include "except.h" 56 57/* The data stored for the loop. */ 58 59struct loop_data 60{ 61 struct loop *outermost_exit; /* The outermost exit of the loop. */ 62 bool has_call; /* True if the loop contains a call. */ 63}; 64 65#define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux) 66 67/* The description of an use. */ 68 69struct use 70{ 71 rtx *pos; /* Position of the use. */ 72 rtx insn; /* The insn in that the use occurs. */ 73 74 struct use *next; /* Next use in the list. */ 75}; 76 77/* The description of a def. */ 78 79struct def 80{ 81 struct use *uses; /* The list of uses that are uniquely reached 82 by it. */ 83 unsigned n_uses; /* Number of such uses. */ 84 unsigned invno; /* The corresponding invariant. */ 85}; 86 87/* The data stored for each invariant. */ 88 89struct invariant 90{ 91 /* The number of the invariant. */ 92 unsigned invno; 93 94 /* The number of the invariant with the same value. */ 95 unsigned eqto; 96 97 /* If we moved the invariant out of the loop, the register that contains its 98 value. */ 99 rtx reg; 100 101 /* The definition of the invariant. */ 102 struct def *def; 103 104 /* The insn in that it is defined. */ 105 rtx insn; 106 107 /* Whether it is always executed. */ 108 bool always_executed; 109 110 /* Whether to move the invariant. */ 111 bool move; 112 113 /* Cost of the invariant. */ 114 unsigned cost; 115 116 /* The invariants it depends on. */ 117 bitmap depends_on; 118 119 /* Used for detecting already visited invariants during determining 120 costs of movements. */ 121 unsigned stamp; 122}; 123 124/* Entry for hash table of invariant expressions. */ 125 126struct invariant_expr_entry 127{ 128 /* The invariant. */ 129 struct invariant *inv; 130 131 /* Its value. */ 132 rtx expr; 133 134 /* Its mode. */ 135 enum machine_mode mode; 136 137 /* Its hash. */ 138 hashval_t hash; 139}; 140 141/* The actual stamp for marking already visited invariants during determining 142 costs of movements. */ 143 144static unsigned actual_stamp; 145 146typedef struct invariant *invariant_p; 147 148DEF_VEC_P(invariant_p); 149DEF_VEC_ALLOC_P(invariant_p, heap); 150 151/* The invariants. */ 152 153static VEC(invariant_p,heap) *invariants; 154 155/* The dataflow object. */ 156 157static struct df *df = NULL; 158 159/* Test for possibility of invariantness of X. */ 160 161static bool 162check_maybe_invariant (rtx x) 163{ 164 enum rtx_code code = GET_CODE (x); 165 int i, j; 166 const char *fmt; 167 168 switch (code) 169 { 170 case CONST_INT: 171 case CONST_DOUBLE: 172 case SYMBOL_REF: 173 case CONST: 174 case LABEL_REF: 175 return true; 176 177 case PC: 178 case CC0: 179 case UNSPEC_VOLATILE: 180 case CALL: 181 return false; 182 183 case REG: 184 return true; 185 186 case MEM: 187 /* Load/store motion is done elsewhere. ??? Perhaps also add it here? 188 It should not be hard, and might be faster than "elsewhere". */ 189 190 /* Just handle the most trivial case where we load from an unchanging 191 location (most importantly, pic tables). */ 192 if (MEM_READONLY_P (x)) 193 break; 194 195 return false; 196 197 case ASM_OPERANDS: 198 /* Don't mess with insns declared volatile. */ 199 if (MEM_VOLATILE_P (x)) 200 return false; 201 break; 202 203 default: 204 break; 205 } 206 207 fmt = GET_RTX_FORMAT (code); 208 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 209 { 210 if (fmt[i] == 'e') 211 { 212 if (!check_maybe_invariant (XEXP (x, i))) 213 return false; 214 } 215 else if (fmt[i] == 'E') 216 { 217 for (j = 0; j < XVECLEN (x, i); j++) 218 if (!check_maybe_invariant (XVECEXP (x, i, j))) 219 return false; 220 } 221 } 222 223 return true; 224} 225 226/* Returns the invariant definition for USE, or NULL if USE is not 227 invariant. */ 228 229static struct invariant * 230invariant_for_use (struct df_ref *use) 231{ 232 struct df_link *defs; 233 struct df_ref *def; 234 basic_block bb = BLOCK_FOR_INSN (use->insn), def_bb; 235 236 if (use->flags & DF_REF_READ_WRITE) 237 return NULL; 238 239 defs = DF_REF_CHAIN (use); 240 if (!defs || defs->next) 241 return NULL; 242 def = defs->ref; 243 if (!DF_REF_DATA (def)) 244 return NULL; 245 246 def_bb = DF_REF_BB (def); 247 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb)) 248 return NULL; 249 return DF_REF_DATA (def); 250} 251 252/* Computes hash value for invariant expression X in INSN. */ 253 254static hashval_t 255hash_invariant_expr_1 (rtx insn, rtx x) 256{ 257 enum rtx_code code = GET_CODE (x); 258 int i, j; 259 const char *fmt; 260 hashval_t val = code; 261 int do_not_record_p; 262 struct df_ref *use; 263 struct invariant *inv; 264 265 switch (code) 266 { 267 case CONST_INT: 268 case CONST_DOUBLE: 269 case SYMBOL_REF: 270 case CONST: 271 case LABEL_REF: 272 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false); 273 274 case REG: 275 use = df_find_use (df, insn, x); 276 if (!use) 277 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false); 278 inv = invariant_for_use (use); 279 if (!inv) 280 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false); 281 282 gcc_assert (inv->eqto != ~0u); 283 return inv->eqto; 284 285 default: 286 break; 287 } 288 289 fmt = GET_RTX_FORMAT (code); 290 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 291 { 292 if (fmt[i] == 'e') 293 val ^= hash_invariant_expr_1 (insn, XEXP (x, i)); 294 else if (fmt[i] == 'E') 295 { 296 for (j = 0; j < XVECLEN (x, i); j++) 297 val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j)); 298 } 299 else if (fmt[i] == 'i' || fmt[i] == 'n') 300 val ^= XINT (x, i); 301 } 302 303 return val; 304} 305 306/* Returns true if the invariant expressions E1 and E2 used in insns INSN1 307 and INSN2 have always the same value. */ 308 309static bool 310invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2) 311{ 312 enum rtx_code code = GET_CODE (e1); 313 int i, j; 314 const char *fmt; 315 struct df_ref *use1, *use2; 316 struct invariant *inv1 = NULL, *inv2 = NULL; 317 rtx sub1, sub2; 318 319 /* If mode of only one of the operands is VOIDmode, it is not equivalent to 320 the other one. If both are VOIDmode, we rely on the caller of this 321 function to verify that their modes are the same. */ 322 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2)) 323 return false; 324 325 switch (code) 326 { 327 case CONST_INT: 328 case CONST_DOUBLE: 329 case SYMBOL_REF: 330 case CONST: 331 case LABEL_REF: 332 return rtx_equal_p (e1, e2); 333 334 case REG: 335 use1 = df_find_use (df, insn1, e1); 336 use2 = df_find_use (df, insn2, e2); 337 if (use1) 338 inv1 = invariant_for_use (use1); 339 if (use2) 340 inv2 = invariant_for_use (use2); 341 342 if (!inv1 && !inv2) 343 return rtx_equal_p (e1, e2); 344 345 if (!inv1 || !inv2) 346 return false; 347 348 gcc_assert (inv1->eqto != ~0u); 349 gcc_assert (inv2->eqto != ~0u); 350 return inv1->eqto == inv2->eqto; 351 352 default: 353 break; 354 } 355 356 fmt = GET_RTX_FORMAT (code); 357 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 358 { 359 if (fmt[i] == 'e') 360 { 361 sub1 = XEXP (e1, i); 362 sub2 = XEXP (e2, i); 363 364 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2)) 365 return false; 366 } 367 368 else if (fmt[i] == 'E') 369 { 370 if (XVECLEN (e1, i) != XVECLEN (e2, i)) 371 return false; 372 373 for (j = 0; j < XVECLEN (e1, i); j++) 374 { 375 sub1 = XVECEXP (e1, i, j); 376 sub2 = XVECEXP (e2, i, j); 377 378 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2)) 379 return false; 380 } 381 } 382 else if (fmt[i] == 'i' || fmt[i] == 'n') 383 { 384 if (XINT (e1, i) != XINT (e2, i)) 385 return false; 386 } 387 /* Unhandled type of subexpression, we fail conservatively. */ 388 else 389 return false; 390 } 391 392 return true; 393} 394 395/* Returns hash value for invariant expression entry E. */ 396 397static hashval_t 398hash_invariant_expr (const void *e) 399{ 400 const struct invariant_expr_entry *entry = e; 401 402 return entry->hash; 403} 404 405/* Compares invariant expression entries E1 and E2. */ 406 407static int 408eq_invariant_expr (const void *e1, const void *e2) 409{ 410 const struct invariant_expr_entry *entry1 = e1; 411 const struct invariant_expr_entry *entry2 = e2; 412 413 if (entry1->mode != entry2->mode) 414 return 0; 415 416 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr, 417 entry2->inv->insn, entry2->expr); 418} 419 420/* Checks whether invariant with value EXPR in machine mode MODE is 421 recorded in EQ. If this is the case, return the invariant. Otherwise 422 insert INV to the table for this expression and return INV. */ 423 424static struct invariant * 425find_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode, 426 struct invariant *inv) 427{ 428 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr); 429 struct invariant_expr_entry *entry; 430 struct invariant_expr_entry pentry; 431 PTR *slot; 432 433 pentry.expr = expr; 434 pentry.inv = inv; 435 pentry.mode = mode; 436 slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT); 437 entry = *slot; 438 439 if (entry) 440 return entry->inv; 441 442 entry = XNEW (struct invariant_expr_entry); 443 entry->inv = inv; 444 entry->expr = expr; 445 entry->mode = mode; 446 entry->hash = hash; 447 *slot = entry; 448 449 return inv; 450} 451 452/* Finds invariants identical to INV and records the equivalence. EQ is the 453 hash table of the invariants. */ 454 455static void 456find_identical_invariants (htab_t eq, struct invariant *inv) 457{ 458 unsigned depno; 459 bitmap_iterator bi; 460 struct invariant *dep; 461 rtx expr, set; 462 enum machine_mode mode; 463 464 if (inv->eqto != ~0u) 465 return; 466 467 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi) 468 { 469 dep = VEC_index (invariant_p, invariants, depno); 470 find_identical_invariants (eq, dep); 471 } 472 473 set = single_set (inv->insn); 474 expr = SET_SRC (set); 475 mode = GET_MODE (expr); 476 if (mode == VOIDmode) 477 mode = GET_MODE (SET_DEST (set)); 478 inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno; 479 480 if (dump_file && inv->eqto != inv->invno) 481 fprintf (dump_file, 482 "Invariant %d is equivalent to invariant %d.\n", 483 inv->invno, inv->eqto); 484} 485 486/* Find invariants with the same value and record the equivalences. */ 487 488static void 489merge_identical_invariants (void) 490{ 491 unsigned i; 492 struct invariant *inv; 493 htab_t eq = htab_create (VEC_length (invariant_p, invariants), 494 hash_invariant_expr, eq_invariant_expr, free); 495 496 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) 497 find_identical_invariants (eq, inv); 498 499 htab_delete (eq); 500} 501 502/* Determines the basic blocks inside LOOP that are always executed and 503 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of 504 basic blocks that may either exit the loop, or contain the call that 505 does not have to return. BODY is body of the loop obtained by 506 get_loop_body_in_dom_order. */ 507 508static void 509compute_always_reached (struct loop *loop, basic_block *body, 510 bitmap may_exit, bitmap always_reached) 511{ 512 unsigned i; 513 514 for (i = 0; i < loop->num_nodes; i++) 515 { 516 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i])) 517 bitmap_set_bit (always_reached, i); 518 519 if (bitmap_bit_p (may_exit, i)) 520 return; 521 } 522} 523 524/* Finds exits out of the LOOP with body BODY. Marks blocks in that we may 525 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT 526 additionally mark blocks that may exit due to a call. */ 527 528static void 529find_exits (struct loop *loop, basic_block *body, 530 bitmap may_exit, bitmap has_exit) 531{ 532 unsigned i; 533 edge_iterator ei; 534 edge e; 535 struct loop *outermost_exit = loop, *aexit; 536 bool has_call = false; 537 rtx insn; 538 539 for (i = 0; i < loop->num_nodes; i++) 540 { 541 if (body[i]->loop_father == loop) 542 { 543 FOR_BB_INSNS (body[i], insn) 544 { 545 if (CALL_P (insn) 546 && !CONST_OR_PURE_CALL_P (insn)) 547 { 548 has_call = true; 549 bitmap_set_bit (may_exit, i); 550 break; 551 } 552 } 553 554 FOR_EACH_EDGE (e, ei, body[i]->succs) 555 { 556 if (flow_bb_inside_loop_p (loop, e->dest)) 557 continue; 558 559 bitmap_set_bit (may_exit, i); 560 bitmap_set_bit (has_exit, i); 561 outermost_exit = find_common_loop (outermost_exit, 562 e->dest->loop_father); 563 } 564 continue; 565 } 566 567 /* Use the data stored for the subloop to decide whether we may exit 568 through it. It is sufficient to do this for header of the loop, 569 as other basic blocks inside it must be dominated by it. */ 570 if (body[i]->loop_father->header != body[i]) 571 continue; 572 573 if (LOOP_DATA (body[i]->loop_father)->has_call) 574 { 575 has_call = true; 576 bitmap_set_bit (may_exit, i); 577 } 578 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit; 579 if (aexit != loop) 580 { 581 bitmap_set_bit (may_exit, i); 582 bitmap_set_bit (has_exit, i); 583 584 if (flow_loop_nested_p (aexit, outermost_exit)) 585 outermost_exit = aexit; 586 } 587 } 588 589 loop->aux = xcalloc (1, sizeof (struct loop_data)); 590 LOOP_DATA (loop)->outermost_exit = outermost_exit; 591 LOOP_DATA (loop)->has_call = has_call; 592} 593 594/* Check whether we may assign a value to X from a register. */ 595 596static bool 597may_assign_reg_p (rtx x) 598{ 599 return (GET_MODE (x) != VOIDmode 600 && GET_MODE (x) != BLKmode 601 && can_copy_p (GET_MODE (x)) 602 && (!REG_P (x) 603 || !HARD_REGISTER_P (x) 604 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS)); 605} 606 607/* Finds definitions that may correspond to invariants in LOOP with body 608 BODY. */ 609 610static void 611find_defs (struct loop *loop, basic_block *body) 612{ 613 unsigned i; 614 bitmap blocks = BITMAP_ALLOC (NULL); 615 616 for (i = 0; i < loop->num_nodes; i++) 617 bitmap_set_bit (blocks, body[i]->index); 618 619 df_set_blocks (df, blocks); 620 df_analyze (df); 621 BITMAP_FREE (blocks); 622} 623 624/* Creates a new invariant for definition DEF in INSN, depending on invariants 625 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed, 626 unless the program ends due to a function call. The newly created invariant 627 is returned. */ 628 629static struct invariant * 630create_new_invariant (struct def *def, rtx insn, bitmap depends_on, 631 bool always_executed) 632{ 633 struct invariant *inv = XNEW (struct invariant); 634 rtx set = single_set (insn); 635 636 inv->def = def; 637 inv->always_executed = always_executed; 638 inv->depends_on = depends_on; 639 640 /* If the set is simple, usually by moving it we move the whole store out of 641 the loop. Otherwise we save only cost of the computation. */ 642 if (def) 643 inv->cost = rtx_cost (set, SET); 644 else 645 inv->cost = rtx_cost (SET_SRC (set), SET); 646 647 inv->move = false; 648 inv->reg = NULL_RTX; 649 inv->stamp = 0; 650 inv->insn = insn; 651 652 inv->invno = VEC_length (invariant_p, invariants); 653 inv->eqto = ~0u; 654 if (def) 655 def->invno = inv->invno; 656 VEC_safe_push (invariant_p, heap, invariants, inv); 657 658 if (dump_file) 659 { 660 fprintf (dump_file, 661 "Set in insn %d is invariant (%d), cost %d, depends on ", 662 INSN_UID (insn), inv->invno, inv->cost); 663 dump_bitmap (dump_file, inv->depends_on); 664 } 665 666 return inv; 667} 668 669/* Record USE at DEF. */ 670 671static void 672record_use (struct def *def, rtx *use, rtx insn) 673{ 674 struct use *u = XNEW (struct use); 675 676 if (GET_CODE (*use) == SUBREG) 677 use = &SUBREG_REG (*use); 678 gcc_assert (REG_P (*use)); 679 680 u->pos = use; 681 u->insn = insn; 682 u->next = def->uses; 683 def->uses = u; 684 def->n_uses++; 685} 686 687/* Finds the invariants INSN depends on and store them to the DEPENDS_ON 688 bitmap. Returns true if all dependencies of INSN are known to be 689 loop invariants, false otherwise. */ 690 691static bool 692check_dependencies (rtx insn, bitmap depends_on) 693{ 694 struct df_link *defs; 695 struct df_ref *use, *def; 696 basic_block bb = BLOCK_FOR_INSN (insn), def_bb; 697 struct def *def_data; 698 struct invariant *inv; 699 700 for (use = DF_INSN_GET (df, insn)->uses; use; use = use->next_ref) 701 { 702 if (use->flags & DF_REF_READ_WRITE) 703 return false; 704 705 defs = DF_REF_CHAIN (use); 706 if (!defs) 707 continue; 708 709 if (defs->next) 710 return false; 711 712 def = defs->ref; 713 inv = DF_REF_DATA (def); 714 if (!inv) 715 return false; 716 717 def_data = inv->def; 718 gcc_assert (def_data != NULL); 719 720 def_bb = DF_REF_BB (def); 721 /* Note that in case bb == def_bb, we know that the definition dominates 722 insn, because def has DF_REF_DATA defined and we process the insns 723 in the basic block bb sequentially. */ 724 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb)) 725 return false; 726 727 bitmap_set_bit (depends_on, def_data->invno); 728 } 729 730 return true; 731} 732 733/* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always 734 executed. ALWAYS_EXECUTED is true if the insn is always executed, 735 unless the program ends due to a function call. */ 736 737static void 738find_invariant_insn (rtx insn, bool always_reached, bool always_executed) 739{ 740 struct df_ref *ref; 741 struct def *def; 742 bitmap depends_on; 743 rtx set, dest; 744 bool simple = true; 745 struct invariant *inv; 746 747 /* Until we get rid of LIBCALLS. */ 748 if (find_reg_note (insn, REG_RETVAL, NULL_RTX) 749 || find_reg_note (insn, REG_LIBCALL, NULL_RTX) 750 || find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX)) 751 return; 752 753#ifdef HAVE_cc0 754 /* We can't move a CC0 setter without the user. */ 755 if (sets_cc0_p (insn)) 756 return; 757#endif 758 759 set = single_set (insn); 760 if (!set) 761 return; 762 dest = SET_DEST (set); 763 764 if (!REG_P (dest) 765 || HARD_REGISTER_P (dest)) 766 simple = false; 767 768 if (!may_assign_reg_p (SET_DEST (set)) 769 || !check_maybe_invariant (SET_SRC (set))) 770 return; 771 772 /* If the insn can throw exception, we cannot move it at all without changing 773 cfg. */ 774 if (can_throw_internal (insn)) 775 return; 776 777 /* We cannot make trapping insn executed, unless it was executed before. */ 778 if (may_trap_after_code_motion_p (PATTERN (insn)) && !always_reached) 779 return; 780 781 depends_on = BITMAP_ALLOC (NULL); 782 if (!check_dependencies (insn, depends_on)) 783 { 784 BITMAP_FREE (depends_on); 785 return; 786 } 787 788 if (simple) 789 def = XCNEW (struct def); 790 else 791 def = NULL; 792 793 inv = create_new_invariant (def, insn, depends_on, always_executed); 794 795 if (simple) 796 { 797 ref = df_find_def (df, insn, dest); 798 DF_REF_DATA (ref) = inv; 799 } 800} 801 802/* Record registers used in INSN that have a unique invariant definition. */ 803 804static void 805record_uses (rtx insn) 806{ 807 struct df_ref *use; 808 struct invariant *inv; 809 810 for (use = DF_INSN_GET (df, insn)->uses; use; use = use->next_ref) 811 { 812 inv = invariant_for_use (use); 813 if (inv) 814 record_use (inv->def, DF_REF_LOC (use), DF_REF_INSN (use)); 815 } 816} 817 818/* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always 819 executed. ALWAYS_EXECUTED is true if the insn is always executed, 820 unless the program ends due to a function call. */ 821 822static void 823find_invariants_insn (rtx insn, bool always_reached, bool always_executed) 824{ 825 find_invariant_insn (insn, always_reached, always_executed); 826 record_uses (insn); 827} 828 829/* Finds invariants in basic block BB. ALWAYS_REACHED is true if the 830 basic block is always executed. ALWAYS_EXECUTED is true if the basic 831 block is always executed, unless the program ends due to a function 832 call. */ 833 834static void 835find_invariants_bb (basic_block bb, bool always_reached, bool always_executed) 836{ 837 rtx insn; 838 839 FOR_BB_INSNS (bb, insn) 840 { 841 if (!INSN_P (insn)) 842 continue; 843 844 find_invariants_insn (insn, always_reached, always_executed); 845 846 if (always_reached 847 && CALL_P (insn) 848 && !CONST_OR_PURE_CALL_P (insn)) 849 always_reached = false; 850 } 851} 852 853/* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of 854 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the 855 bitmap of basic blocks in BODY that are always executed unless the program 856 ends due to a function call. */ 857 858static void 859find_invariants_body (struct loop *loop, basic_block *body, 860 bitmap always_reached, bitmap always_executed) 861{ 862 unsigned i; 863 864 for (i = 0; i < loop->num_nodes; i++) 865 find_invariants_bb (body[i], 866 bitmap_bit_p (always_reached, i), 867 bitmap_bit_p (always_executed, i)); 868} 869 870/* Finds invariants in LOOP. */ 871 872static void 873find_invariants (struct loop *loop) 874{ 875 bitmap may_exit = BITMAP_ALLOC (NULL); 876 bitmap always_reached = BITMAP_ALLOC (NULL); 877 bitmap has_exit = BITMAP_ALLOC (NULL); 878 bitmap always_executed = BITMAP_ALLOC (NULL); 879 basic_block *body = get_loop_body_in_dom_order (loop); 880 881 find_exits (loop, body, may_exit, has_exit); 882 compute_always_reached (loop, body, may_exit, always_reached); 883 compute_always_reached (loop, body, has_exit, always_executed); 884 885 find_defs (loop, body); 886 find_invariants_body (loop, body, always_reached, always_executed); 887 merge_identical_invariants (); 888 889 BITMAP_FREE (always_reached); 890 BITMAP_FREE (always_executed); 891 BITMAP_FREE (may_exit); 892 BITMAP_FREE (has_exit); 893 free (body); 894} 895 896/* Frees a list of uses USE. */ 897 898static void 899free_use_list (struct use *use) 900{ 901 struct use *next; 902 903 for (; use; use = next) 904 { 905 next = use->next; 906 free (use); 907 } 908} 909 910/* Calculates cost and number of registers needed for moving invariant INV 911 out of the loop and stores them to *COST and *REGS_NEEDED. */ 912 913static void 914get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed) 915{ 916 int acomp_cost; 917 unsigned aregs_needed; 918 unsigned depno; 919 struct invariant *dep; 920 bitmap_iterator bi; 921 922 /* Find the representative of the class of the equivalent invariants. */ 923 inv = VEC_index (invariant_p, invariants, inv->eqto); 924 925 *comp_cost = 0; 926 *regs_needed = 0; 927 if (inv->move 928 || inv->stamp == actual_stamp) 929 return; 930 inv->stamp = actual_stamp; 931 932 (*regs_needed)++; 933 (*comp_cost) += inv->cost; 934 935#ifdef STACK_REGS 936 { 937 /* Hoisting constant pool constants into stack regs may cost more than 938 just single register. On x87, the balance is affected both by the 939 small number of FP registers, and by its register stack organization, 940 that forces us to add compensation code in and around the loop to 941 shuffle the operands to the top of stack before use, and pop them 942 from the stack after the loop finishes. 943 944 To model this effect, we increase the number of registers needed for 945 stack registers by two: one register push, and one register pop. 946 This usually has the effect that FP constant loads from the constant 947 pool are not moved out of the loop. 948 949 Note that this also means that dependent invariants can not be moved. 950 However, the primary purpose of this pass is to move loop invariant 951 address arithmetic out of loops, and address arithmetic that depends 952 on floating point constants is unlikely to ever occur. */ 953 rtx set = single_set (inv->insn); 954 if (set 955 && IS_STACK_MODE (GET_MODE (SET_SRC (set))) 956 && constant_pool_constant_p (SET_SRC (set))) 957 (*regs_needed) += 2; 958 } 959#endif 960 961 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi) 962 { 963 dep = VEC_index (invariant_p, invariants, depno); 964 965 get_inv_cost (dep, &acomp_cost, &aregs_needed); 966 967 if (aregs_needed 968 /* We need to check always_executed, since if the original value of 969 the invariant may be preserved, we may need to keep it in a 970 separate register. TODO check whether the register has an 971 use outside of the loop. */ 972 && dep->always_executed 973 && !dep->def->uses->next) 974 { 975 /* If this is a single use, after moving the dependency we will not 976 need a new register. */ 977 aregs_needed--; 978 } 979 980 (*regs_needed) += aregs_needed; 981 (*comp_cost) += acomp_cost; 982 } 983} 984 985/* Calculates gain for eliminating invariant INV. REGS_USED is the number 986 of registers used in the loop, N_INV_USES is the number of uses of 987 invariants, NEW_REGS is the number of new variables already added due to 988 the invariant motion. The number of registers needed for it is stored in 989 *REGS_NEEDED. */ 990 991static int 992gain_for_invariant (struct invariant *inv, unsigned *regs_needed, 993 unsigned new_regs, unsigned regs_used, unsigned n_inv_uses) 994{ 995 int comp_cost, size_cost; 996 997 get_inv_cost (inv, &comp_cost, regs_needed); 998 actual_stamp++; 999 1000 size_cost = (global_cost_for_size (new_regs + *regs_needed, 1001 regs_used, n_inv_uses) 1002 - global_cost_for_size (new_regs, regs_used, n_inv_uses)); 1003 1004 return comp_cost - size_cost; 1005} 1006 1007/* Finds invariant with best gain for moving. Returns the gain, stores 1008 the invariant in *BEST and number of registers needed for it to 1009 *REGS_NEEDED. REGS_USED is the number of registers used in 1010 the loop, N_INV_USES is the number of uses of invariants. NEW_REGS 1011 is the number of new variables already added due to invariant motion. */ 1012 1013static int 1014best_gain_for_invariant (struct invariant **best, unsigned *regs_needed, 1015 unsigned new_regs, unsigned regs_used, 1016 unsigned n_inv_uses) 1017{ 1018 struct invariant *inv; 1019 int gain = 0, again; 1020 unsigned aregs_needed, invno; 1021 1022 for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++) 1023 { 1024 if (inv->move) 1025 continue; 1026 1027 /* Only consider the "representatives" of equivalent invariants. */ 1028 if (inv->eqto != inv->invno) 1029 continue; 1030 1031 again = gain_for_invariant (inv, &aregs_needed, 1032 new_regs, regs_used, n_inv_uses); 1033 if (again > gain) 1034 { 1035 gain = again; 1036 *best = inv; 1037 *regs_needed = aregs_needed; 1038 } 1039 } 1040 1041 return gain; 1042} 1043 1044/* Marks invariant INVNO and all its dependencies for moving. */ 1045 1046static void 1047set_move_mark (unsigned invno) 1048{ 1049 struct invariant *inv = VEC_index (invariant_p, invariants, invno); 1050 bitmap_iterator bi; 1051 1052 /* Find the representative of the class of the equivalent invariants. */ 1053 inv = VEC_index (invariant_p, invariants, inv->eqto); 1054 1055 if (inv->move) 1056 return; 1057 inv->move = true; 1058 1059 if (dump_file) 1060 fprintf (dump_file, "Decided to move invariant %d\n", invno); 1061 1062 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi) 1063 { 1064 set_move_mark (invno); 1065 } 1066} 1067 1068/* Determines which invariants to move. */ 1069 1070static void 1071find_invariants_to_move (void) 1072{ 1073 unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs; 1074 struct invariant *inv = NULL; 1075 unsigned int n_regs = DF_REG_SIZE (df); 1076 1077 if (!VEC_length (invariant_p, invariants)) 1078 return; 1079 1080 /* Now something slightly more involved. First estimate the number of used 1081 registers. */ 1082 n_inv_uses = 0; 1083 1084 /* We do not really do a good job in this estimation; put some initial bound 1085 here to stand for induction variables etc. that we do not detect. */ 1086 regs_used = 2; 1087 1088 for (i = 0; i < n_regs; i++) 1089 { 1090 if (!DF_REGNO_FIRST_DEF (df, i) && DF_REGNO_LAST_USE (df, i)) 1091 { 1092 /* This is a value that is used but not changed inside loop. */ 1093 regs_used++; 1094 } 1095 } 1096 1097 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) 1098 { 1099 if (inv->def) 1100 n_inv_uses += inv->def->n_uses; 1101 } 1102 1103 new_regs = 0; 1104 while (best_gain_for_invariant (&inv, ®s_needed, 1105 new_regs, regs_used, n_inv_uses) > 0) 1106 { 1107 set_move_mark (inv->invno); 1108 new_regs += regs_needed; 1109 } 1110} 1111 1112/* Returns true if all insns in SEQ are valid. */ 1113 1114static bool 1115seq_insns_valid_p (rtx seq) 1116{ 1117 rtx x; 1118 1119 for (x = seq; x; x = NEXT_INSN (x)) 1120 if (insn_invalid_p (x)) 1121 return false; 1122 1123 return true; 1124} 1125 1126/* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false 1127 otherwise. */ 1128 1129static bool 1130move_invariant_reg (struct loop *loop, unsigned invno) 1131{ 1132 struct invariant *inv = VEC_index (invariant_p, invariants, invno); 1133 struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto); 1134 unsigned i; 1135 basic_block preheader = loop_preheader_edge (loop)->src; 1136 rtx reg, set, dest, seq, op; 1137 struct use *use; 1138 bitmap_iterator bi; 1139 1140 if (inv->reg) 1141 return true; 1142 if (!repr->move) 1143 return false; 1144 1145 /* If this is a representative of the class of equivalent invariants, 1146 really move the invariant. Otherwise just replace its use with 1147 the register used for the representative. */ 1148 if (inv == repr) 1149 { 1150 if (inv->depends_on) 1151 { 1152 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi) 1153 { 1154 if (!move_invariant_reg (loop, i)) 1155 goto fail; 1156 } 1157 } 1158 1159 /* Move the set out of the loop. If the set is always executed (we could 1160 omit this condition if we know that the register is unused outside of the 1161 loop, but it does not seem worth finding out) and it has no uses that 1162 would not be dominated by it, we may just move it (TODO). Otherwise we 1163 need to create a temporary register. */ 1164 set = single_set (inv->insn); 1165 dest = SET_DEST (set); 1166 reg = gen_reg_rtx (GET_MODE (dest)); 1167 1168 /* If the SET_DEST of the invariant insn is a pseudo, we can just move 1169 the insn out of the loop. Otherwise, we have to use gen_move_insn 1170 to let emit_move_insn produce a valid instruction stream. */ 1171 if (REG_P (dest) && !HARD_REGISTER_P (dest)) 1172 { 1173 emit_insn_after (gen_move_insn (dest, reg), inv->insn); 1174 SET_DEST (set) = reg; 1175 reorder_insns (inv->insn, inv->insn, BB_END (preheader)); 1176 } 1177 else 1178 { 1179 start_sequence (); 1180 op = force_operand (SET_SRC (set), reg); 1181 if (!op) 1182 { 1183 end_sequence (); 1184 goto fail; 1185 } 1186 if (op != reg) 1187 emit_move_insn (reg, op); 1188 seq = get_insns (); 1189 end_sequence (); 1190 1191 if (!seq_insns_valid_p (seq)) 1192 goto fail; 1193 emit_insn_after (seq, BB_END (preheader)); 1194 1195 emit_insn_after (gen_move_insn (dest, reg), inv->insn); 1196 delete_insn (inv->insn); 1197 } 1198 } 1199 else 1200 { 1201 if (!move_invariant_reg (loop, repr->invno)) 1202 goto fail; 1203 reg = repr->reg; 1204 set = single_set (inv->insn); 1205 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn); 1206 delete_insn (inv->insn); 1207 } 1208 1209 inv->reg = reg; 1210 1211 /* Replace the uses we know to be dominated. It saves work for copy 1212 propagation, and also it is necessary so that dependent invariants 1213 are computed right. */ 1214 if (inv->def) 1215 { 1216 for (use = inv->def->uses; use; use = use->next) 1217 *use->pos = reg; 1218 } 1219 1220 return true; 1221 1222fail: 1223 /* If we failed, clear move flag, so that we do not try to move inv 1224 again. */ 1225 if (dump_file) 1226 fprintf (dump_file, "Failed to move invariant %d\n", invno); 1227 inv->move = false; 1228 inv->reg = NULL_RTX; 1229 return false; 1230} 1231 1232/* Move selected invariant out of the LOOP. Newly created regs are marked 1233 in TEMPORARY_REGS. */ 1234 1235static void 1236move_invariants (struct loop *loop) 1237{ 1238 struct invariant *inv; 1239 unsigned i; 1240 1241 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) 1242 move_invariant_reg (loop, i); 1243} 1244 1245/* Initializes invariant motion data. */ 1246 1247static void 1248init_inv_motion_data (void) 1249{ 1250 actual_stamp = 1; 1251 1252 invariants = VEC_alloc (invariant_p, heap, 100); 1253} 1254 1255/* Frees the data allocated by invariant motion. */ 1256 1257static void 1258free_inv_motion_data (void) 1259{ 1260 unsigned i; 1261 struct def *def; 1262 struct invariant *inv; 1263 1264 for (i = 0; i < DF_DEFS_SIZE (df); i++) 1265 { 1266 struct df_ref * ref = DF_DEFS_GET (df, i); 1267 if (!ref) 1268 continue; 1269 1270 inv = DF_REF_DATA (ref); 1271 if (!inv) 1272 continue; 1273 1274 def = inv->def; 1275 gcc_assert (def != NULL); 1276 1277 free_use_list (def->uses); 1278 free (def); 1279 DF_REF_DATA (ref) = NULL; 1280 } 1281 1282 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) 1283 { 1284 BITMAP_FREE (inv->depends_on); 1285 free (inv); 1286 } 1287 VEC_free (invariant_p, heap, invariants); 1288} 1289 1290/* Move the invariants out of the LOOP. */ 1291 1292static void 1293move_single_loop_invariants (struct loop *loop) 1294{ 1295 init_inv_motion_data (); 1296 1297 find_invariants (loop); 1298 find_invariants_to_move (); 1299 move_invariants (loop); 1300 1301 free_inv_motion_data (); 1302} 1303 1304/* Releases the auxiliary data for LOOP. */ 1305 1306static void 1307free_loop_data (struct loop *loop) 1308{ 1309 struct loop_data *data = LOOP_DATA (loop); 1310 1311 free (data); 1312 loop->aux = NULL; 1313} 1314 1315/* Move the invariants out of the LOOPS. */ 1316 1317void 1318move_loop_invariants (struct loops *loops) 1319{ 1320 struct loop *loop; 1321 unsigned i; 1322 1323 df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES); 1324 df_chain_add_problem (df, DF_UD_CHAIN); 1325 1326 /* Process the loops, innermost first. */ 1327 loop = loops->tree_root; 1328 while (loop->inner) 1329 loop = loop->inner; 1330 1331 while (loop != loops->tree_root) 1332 { 1333 move_single_loop_invariants (loop); 1334 1335 if (loop->next) 1336 { 1337 loop = loop->next; 1338 while (loop->inner) 1339 loop = loop->inner; 1340 } 1341 else 1342 loop = loop->outer; 1343 } 1344 1345 for (i = 1; i < loops->num; i++) 1346 if (loops->parray[i]) 1347 free_loop_data (loops->parray[i]); 1348 1349 df_finish (df); 1350 df = NULL; 1351 1352#ifdef ENABLE_CHECKING 1353 verify_flow_info (); 1354#endif 1355} 1356