1/* RTL-level loop invariant motion. 2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 3 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it 8under the terms of the GNU General Public License as published by the 9Free Software Foundation; either version 3, or (at your option) any 10later version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT 13ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21/* This implements the loop invariant motion pass. It is very simple 22 (no calls, no loads/stores, etc.). This should be sufficient to cleanup 23 things like address arithmetics -- other more complicated invariants should 24 be eliminated on GIMPLE 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 "hard-reg-set.h" 43#include "rtl.h" 44#include "tm_p.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#include "params.h" 57#include "regs.h" 58#include "ira.h" 59 60/* The data stored for the loop. */ 61 62struct loop_data 63{ 64 struct loop *outermost_exit; /* The outermost exit of the loop. */ 65 bool has_call; /* True if the loop contains a call. */ 66 /* Maximal register pressure inside loop for given register class 67 (defined only for the cover classes). */ 68 int max_reg_pressure[N_REG_CLASSES]; 69 /* Loop regs referenced and live pseudo-registers. */ 70 bitmap_head regs_ref; 71 bitmap_head regs_live; 72}; 73 74#define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux) 75 76/* The description of an use. */ 77 78struct use 79{ 80 rtx *pos; /* Position of the use. */ 81 rtx insn; /* The insn in that the use occurs. */ 82 unsigned addr_use_p; /* Whether the use occurs in an address. */ 83 struct use *next; /* Next use in the list. */ 84}; 85 86/* The description of a def. */ 87 88struct def 89{ 90 struct use *uses; /* The list of uses that are uniquely reached 91 by it. */ 92 unsigned n_uses; /* Number of such uses. */ 93 unsigned n_addr_uses; /* Number of uses in addresses. */ 94 unsigned invno; /* The corresponding invariant. */ 95}; 96 97/* The data stored for each invariant. */ 98 99struct invariant 100{ 101 /* The number of the invariant. */ 102 unsigned invno; 103 104 /* The number of the invariant with the same value. */ 105 unsigned eqto; 106 107 /* If we moved the invariant out of the loop, the register that contains its 108 value. */ 109 rtx reg; 110 111 /* If we moved the invariant out of the loop, the original regno 112 that contained its value. */ 113 int orig_regno; 114 115 /* The definition of the invariant. */ 116 struct def *def; 117 118 /* The insn in that it is defined. */ 119 rtx insn; 120 121 /* Whether it is always executed. */ 122 bool always_executed; 123 124 /* Whether to move the invariant. */ 125 bool move; 126 127 /* Whether the invariant is cheap when used as an address. */ 128 bool cheap_address; 129 130 /* Cost of the invariant. */ 131 unsigned cost; 132 133 /* The invariants it depends on. */ 134 bitmap depends_on; 135 136 /* Used for detecting already visited invariants during determining 137 costs of movements. */ 138 unsigned stamp; 139}; 140 141/* Currently processed loop. */ 142static struct loop *curr_loop; 143 144/* Table of invariants indexed by the df_ref uid field. */ 145 146static unsigned int invariant_table_size = 0; 147static struct invariant ** invariant_table; 148 149/* Entry for hash table of invariant expressions. */ 150 151struct invariant_expr_entry 152{ 153 /* The invariant. */ 154 struct invariant *inv; 155 156 /* Its value. */ 157 rtx expr; 158 159 /* Its mode. */ 160 enum machine_mode mode; 161 162 /* Its hash. */ 163 hashval_t hash; 164}; 165 166/* The actual stamp for marking already visited invariants during determining 167 costs of movements. */ 168 169static unsigned actual_stamp; 170 171typedef struct invariant *invariant_p; 172 173DEF_VEC_P(invariant_p); 174DEF_VEC_ALLOC_P(invariant_p, heap); 175 176/* The invariants. */ 177 178static VEC(invariant_p,heap) *invariants; 179 180/* Check the size of the invariant table and realloc if necessary. */ 181 182static void 183check_invariant_table_size (void) 184{ 185 if (invariant_table_size < DF_DEFS_TABLE_SIZE()) 186 { 187 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4); 188 invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size); 189 memset (&invariant_table[invariant_table_size], 0, 190 (new_size - invariant_table_size) * sizeof (struct rtx_iv *)); 191 invariant_table_size = new_size; 192 } 193} 194 195/* Test for possibility of invariantness of X. */ 196 197static bool 198check_maybe_invariant (rtx x) 199{ 200 enum rtx_code code = GET_CODE (x); 201 int i, j; 202 const char *fmt; 203 204 switch (code) 205 { 206 case CONST_INT: 207 case CONST_DOUBLE: 208 case CONST_FIXED: 209 case SYMBOL_REF: 210 case CONST: 211 case LABEL_REF: 212 return true; 213 214 case PC: 215 case CC0: 216 case UNSPEC_VOLATILE: 217 case CALL: 218 return false; 219 220 case REG: 221 return true; 222 223 case MEM: 224 /* Load/store motion is done elsewhere. ??? Perhaps also add it here? 225 It should not be hard, and might be faster than "elsewhere". */ 226 227 /* Just handle the most trivial case where we load from an unchanging 228 location (most importantly, pic tables). */ 229 if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x)) 230 break; 231 232 return false; 233 234 case ASM_OPERANDS: 235 /* Don't mess with insns declared volatile. */ 236 if (MEM_VOLATILE_P (x)) 237 return false; 238 break; 239 240 default: 241 break; 242 } 243 244 fmt = GET_RTX_FORMAT (code); 245 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 246 { 247 if (fmt[i] == 'e') 248 { 249 if (!check_maybe_invariant (XEXP (x, i))) 250 return false; 251 } 252 else if (fmt[i] == 'E') 253 { 254 for (j = 0; j < XVECLEN (x, i); j++) 255 if (!check_maybe_invariant (XVECEXP (x, i, j))) 256 return false; 257 } 258 } 259 260 return true; 261} 262 263/* Returns the invariant definition for USE, or NULL if USE is not 264 invariant. */ 265 266static struct invariant * 267invariant_for_use (df_ref use) 268{ 269 struct df_link *defs; 270 df_ref def; 271 basic_block bb = DF_REF_BB (use), def_bb; 272 273 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE) 274 return NULL; 275 276 defs = DF_REF_CHAIN (use); 277 if (!defs || defs->next) 278 return NULL; 279 def = defs->ref; 280 check_invariant_table_size (); 281 if (!invariant_table[DF_REF_ID(def)]) 282 return NULL; 283 284 def_bb = DF_REF_BB (def); 285 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb)) 286 return NULL; 287 return invariant_table[DF_REF_ID(def)]; 288} 289 290/* Computes hash value for invariant expression X in INSN. */ 291 292static hashval_t 293hash_invariant_expr_1 (rtx insn, rtx x) 294{ 295 enum rtx_code code = GET_CODE (x); 296 int i, j; 297 const char *fmt; 298 hashval_t val = code; 299 int do_not_record_p; 300 df_ref use; 301 struct invariant *inv; 302 303 switch (code) 304 { 305 case CONST_INT: 306 case CONST_DOUBLE: 307 case CONST_FIXED: 308 case SYMBOL_REF: 309 case CONST: 310 case LABEL_REF: 311 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false); 312 313 case REG: 314 use = df_find_use (insn, x); 315 if (!use) 316 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false); 317 inv = invariant_for_use (use); 318 if (!inv) 319 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false); 320 321 gcc_assert (inv->eqto != ~0u); 322 return inv->eqto; 323 324 default: 325 break; 326 } 327 328 fmt = GET_RTX_FORMAT (code); 329 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 330 { 331 if (fmt[i] == 'e') 332 val ^= hash_invariant_expr_1 (insn, XEXP (x, i)); 333 else if (fmt[i] == 'E') 334 { 335 for (j = 0; j < XVECLEN (x, i); j++) 336 val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j)); 337 } 338 else if (fmt[i] == 'i' || fmt[i] == 'n') 339 val ^= XINT (x, i); 340 } 341 342 return val; 343} 344 345/* Returns true if the invariant expressions E1 and E2 used in insns INSN1 346 and INSN2 have always the same value. */ 347 348static bool 349invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2) 350{ 351 enum rtx_code code = GET_CODE (e1); 352 int i, j; 353 const char *fmt; 354 df_ref use1, use2; 355 struct invariant *inv1 = NULL, *inv2 = NULL; 356 rtx sub1, sub2; 357 358 /* If mode of only one of the operands is VOIDmode, it is not equivalent to 359 the other one. If both are VOIDmode, we rely on the caller of this 360 function to verify that their modes are the same. */ 361 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2)) 362 return false; 363 364 switch (code) 365 { 366 case CONST_INT: 367 case CONST_DOUBLE: 368 case CONST_FIXED: 369 case SYMBOL_REF: 370 case CONST: 371 case LABEL_REF: 372 return rtx_equal_p (e1, e2); 373 374 case REG: 375 use1 = df_find_use (insn1, e1); 376 use2 = df_find_use (insn2, e2); 377 if (use1) 378 inv1 = invariant_for_use (use1); 379 if (use2) 380 inv2 = invariant_for_use (use2); 381 382 if (!inv1 && !inv2) 383 return rtx_equal_p (e1, e2); 384 385 if (!inv1 || !inv2) 386 return false; 387 388 gcc_assert (inv1->eqto != ~0u); 389 gcc_assert (inv2->eqto != ~0u); 390 return inv1->eqto == inv2->eqto; 391 392 default: 393 break; 394 } 395 396 fmt = GET_RTX_FORMAT (code); 397 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 398 { 399 if (fmt[i] == 'e') 400 { 401 sub1 = XEXP (e1, i); 402 sub2 = XEXP (e2, i); 403 404 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2)) 405 return false; 406 } 407 408 else if (fmt[i] == 'E') 409 { 410 if (XVECLEN (e1, i) != XVECLEN (e2, i)) 411 return false; 412 413 for (j = 0; j < XVECLEN (e1, i); j++) 414 { 415 sub1 = XVECEXP (e1, i, j); 416 sub2 = XVECEXP (e2, i, j); 417 418 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2)) 419 return false; 420 } 421 } 422 else if (fmt[i] == 'i' || fmt[i] == 'n') 423 { 424 if (XINT (e1, i) != XINT (e2, i)) 425 return false; 426 } 427 /* Unhandled type of subexpression, we fail conservatively. */ 428 else 429 return false; 430 } 431 432 return true; 433} 434 435/* Returns hash value for invariant expression entry E. */ 436 437static hashval_t 438hash_invariant_expr (const void *e) 439{ 440 const struct invariant_expr_entry *const entry = 441 (const struct invariant_expr_entry *) e; 442 443 return entry->hash; 444} 445 446/* Compares invariant expression entries E1 and E2. */ 447 448static int 449eq_invariant_expr (const void *e1, const void *e2) 450{ 451 const struct invariant_expr_entry *const entry1 = 452 (const struct invariant_expr_entry *) e1; 453 const struct invariant_expr_entry *const entry2 = 454 (const struct invariant_expr_entry *) e2; 455 456 if (entry1->mode != entry2->mode) 457 return 0; 458 459 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr, 460 entry2->inv->insn, entry2->expr); 461} 462 463/* Checks whether invariant with value EXPR in machine mode MODE is 464 recorded in EQ. If this is the case, return the invariant. Otherwise 465 insert INV to the table for this expression and return INV. */ 466 467static struct invariant * 468find_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode, 469 struct invariant *inv) 470{ 471 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr); 472 struct invariant_expr_entry *entry; 473 struct invariant_expr_entry pentry; 474 PTR *slot; 475 476 pentry.expr = expr; 477 pentry.inv = inv; 478 pentry.mode = mode; 479 slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT); 480 entry = (struct invariant_expr_entry *) *slot; 481 482 if (entry) 483 return entry->inv; 484 485 entry = XNEW (struct invariant_expr_entry); 486 entry->inv = inv; 487 entry->expr = expr; 488 entry->mode = mode; 489 entry->hash = hash; 490 *slot = entry; 491 492 return inv; 493} 494 495/* Finds invariants identical to INV and records the equivalence. EQ is the 496 hash table of the invariants. */ 497 498static void 499find_identical_invariants (htab_t eq, struct invariant *inv) 500{ 501 unsigned depno; 502 bitmap_iterator bi; 503 struct invariant *dep; 504 rtx expr, set; 505 enum machine_mode mode; 506 507 if (inv->eqto != ~0u) 508 return; 509 510 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi) 511 { 512 dep = VEC_index (invariant_p, invariants, depno); 513 find_identical_invariants (eq, dep); 514 } 515 516 set = single_set (inv->insn); 517 expr = SET_SRC (set); 518 mode = GET_MODE (expr); 519 if (mode == VOIDmode) 520 mode = GET_MODE (SET_DEST (set)); 521 inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno; 522 523 if (dump_file && inv->eqto != inv->invno) 524 fprintf (dump_file, 525 "Invariant %d is equivalent to invariant %d.\n", 526 inv->invno, inv->eqto); 527} 528 529/* Find invariants with the same value and record the equivalences. */ 530 531static void 532merge_identical_invariants (void) 533{ 534 unsigned i; 535 struct invariant *inv; 536 htab_t eq = htab_create (VEC_length (invariant_p, invariants), 537 hash_invariant_expr, eq_invariant_expr, free); 538 539 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) 540 find_identical_invariants (eq, inv); 541 542 htab_delete (eq); 543} 544 545/* Determines the basic blocks inside LOOP that are always executed and 546 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of 547 basic blocks that may either exit the loop, or contain the call that 548 does not have to return. BODY is body of the loop obtained by 549 get_loop_body_in_dom_order. */ 550 551static void 552compute_always_reached (struct loop *loop, basic_block *body, 553 bitmap may_exit, bitmap always_reached) 554{ 555 unsigned i; 556 557 for (i = 0; i < loop->num_nodes; i++) 558 { 559 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i])) 560 bitmap_set_bit (always_reached, i); 561 562 if (bitmap_bit_p (may_exit, i)) 563 return; 564 } 565} 566 567/* Finds exits out of the LOOP with body BODY. Marks blocks in that we may 568 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT 569 additionally mark blocks that may exit due to a call. */ 570 571static void 572find_exits (struct loop *loop, basic_block *body, 573 bitmap may_exit, bitmap has_exit) 574{ 575 unsigned i; 576 edge_iterator ei; 577 edge e; 578 struct loop *outermost_exit = loop, *aexit; 579 bool has_call = false; 580 rtx insn; 581 582 for (i = 0; i < loop->num_nodes; i++) 583 { 584 if (body[i]->loop_father == loop) 585 { 586 FOR_BB_INSNS (body[i], insn) 587 { 588 if (CALL_P (insn) 589 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn) 590 || !RTL_CONST_OR_PURE_CALL_P (insn))) 591 { 592 has_call = true; 593 bitmap_set_bit (may_exit, i); 594 break; 595 } 596 } 597 598 FOR_EACH_EDGE (e, ei, body[i]->succs) 599 { 600 if (flow_bb_inside_loop_p (loop, e->dest)) 601 continue; 602 603 bitmap_set_bit (may_exit, i); 604 bitmap_set_bit (has_exit, i); 605 outermost_exit = find_common_loop (outermost_exit, 606 e->dest->loop_father); 607 } 608 continue; 609 } 610 611 /* Use the data stored for the subloop to decide whether we may exit 612 through it. It is sufficient to do this for header of the loop, 613 as other basic blocks inside it must be dominated by it. */ 614 if (body[i]->loop_father->header != body[i]) 615 continue; 616 617 if (LOOP_DATA (body[i]->loop_father)->has_call) 618 { 619 has_call = true; 620 bitmap_set_bit (may_exit, i); 621 } 622 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit; 623 if (aexit != loop) 624 { 625 bitmap_set_bit (may_exit, i); 626 bitmap_set_bit (has_exit, i); 627 628 if (flow_loop_nested_p (aexit, outermost_exit)) 629 outermost_exit = aexit; 630 } 631 } 632 633 if (loop->aux == NULL) 634 { 635 loop->aux = xcalloc (1, sizeof (struct loop_data)); 636 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, ®_obstack); 637 bitmap_initialize (&LOOP_DATA (loop)->regs_live, ®_obstack); 638 } 639 LOOP_DATA (loop)->outermost_exit = outermost_exit; 640 LOOP_DATA (loop)->has_call = has_call; 641} 642 643/* Check whether we may assign a value to X from a register. */ 644 645static bool 646may_assign_reg_p (rtx x) 647{ 648 return (GET_MODE (x) != VOIDmode 649 && GET_MODE (x) != BLKmode 650 && can_copy_p (GET_MODE (x)) 651 && (!REG_P (x) 652 || !HARD_REGISTER_P (x) 653 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS)); 654} 655 656/* Finds definitions that may correspond to invariants in LOOP with body 657 BODY. */ 658 659static void 660find_defs (struct loop *loop, basic_block *body) 661{ 662 unsigned i; 663 bitmap blocks = BITMAP_ALLOC (NULL); 664 665 for (i = 0; i < loop->num_nodes; i++) 666 bitmap_set_bit (blocks, body[i]->index); 667 668 df_remove_problem (df_chain); 669 df_process_deferred_rescans (); 670 df_chain_add_problem (DF_UD_CHAIN); 671 df_set_blocks (blocks); 672 df_analyze (); 673 674 if (dump_file) 675 { 676 df_dump_region (dump_file); 677 fprintf (dump_file, "*****starting processing of loop ******\n"); 678 print_rtl_with_bb (dump_file, get_insns ()); 679 fprintf (dump_file, "*****ending processing of loop ******\n"); 680 } 681 check_invariant_table_size (); 682 683 BITMAP_FREE (blocks); 684} 685 686/* Creates a new invariant for definition DEF in INSN, depending on invariants 687 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed, 688 unless the program ends due to a function call. The newly created invariant 689 is returned. */ 690 691static struct invariant * 692create_new_invariant (struct def *def, rtx insn, bitmap depends_on, 693 bool always_executed) 694{ 695 struct invariant *inv = XNEW (struct invariant); 696 rtx set = single_set (insn); 697 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn)); 698 699 inv->def = def; 700 inv->always_executed = always_executed; 701 inv->depends_on = depends_on; 702 703 /* If the set is simple, usually by moving it we move the whole store out of 704 the loop. Otherwise we save only cost of the computation. */ 705 if (def) 706 { 707 inv->cost = rtx_cost (set, SET, speed); 708 /* ??? Try to determine cheapness of address computation. Unfortunately 709 the address cost is only a relative measure, we can't really compare 710 it with any absolute number, but only with other address costs. 711 But here we don't have any other addresses, so compare with a magic 712 number anyway. It has to be large enough to not regress PR33928 713 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small 714 enough to not regress 410.bwaves either (by still moving reg+reg 715 invariants). 716 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */ 717 inv->cheap_address = address_cost (SET_SRC (set), word_mode, 718 ADDR_SPACE_GENERIC, speed) < 3; 719 } 720 else 721 { 722 inv->cost = rtx_cost (SET_SRC (set), SET, speed); 723 inv->cheap_address = false; 724 } 725 726 inv->move = false; 727 inv->reg = NULL_RTX; 728 inv->orig_regno = -1; 729 inv->stamp = 0; 730 inv->insn = insn; 731 732 inv->invno = VEC_length (invariant_p, invariants); 733 inv->eqto = ~0u; 734 if (def) 735 def->invno = inv->invno; 736 VEC_safe_push (invariant_p, heap, invariants, inv); 737 738 if (dump_file) 739 { 740 fprintf (dump_file, 741 "Set in insn %d is invariant (%d), cost %d, depends on ", 742 INSN_UID (insn), inv->invno, inv->cost); 743 dump_bitmap (dump_file, inv->depends_on); 744 } 745 746 return inv; 747} 748 749/* Record USE at DEF. */ 750 751static void 752record_use (struct def *def, df_ref use) 753{ 754 struct use *u = XNEW (struct use); 755 756 u->pos = DF_REF_REAL_LOC (use); 757 u->insn = DF_REF_INSN (use); 758 u->addr_use_p = (DF_REF_TYPE (use) == DF_REF_REG_MEM_LOAD 759 || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE); 760 u->next = def->uses; 761 def->uses = u; 762 def->n_uses++; 763 if (u->addr_use_p) 764 def->n_addr_uses++; 765} 766 767/* Finds the invariants USE depends on and store them to the DEPENDS_ON 768 bitmap. Returns true if all dependencies of USE are known to be 769 loop invariants, false otherwise. */ 770 771static bool 772check_dependency (basic_block bb, df_ref use, bitmap depends_on) 773{ 774 df_ref def; 775 basic_block def_bb; 776 struct df_link *defs; 777 struct def *def_data; 778 struct invariant *inv; 779 780 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE) 781 return false; 782 783 defs = DF_REF_CHAIN (use); 784 if (!defs) 785 return true; 786 787 if (defs->next) 788 return false; 789 790 def = defs->ref; 791 check_invariant_table_size (); 792 inv = invariant_table[DF_REF_ID(def)]; 793 if (!inv) 794 return false; 795 796 def_data = inv->def; 797 gcc_assert (def_data != NULL); 798 799 def_bb = DF_REF_BB (def); 800 /* Note that in case bb == def_bb, we know that the definition 801 dominates insn, because def has invariant_table[DF_REF_ID(def)] 802 defined and we process the insns in the basic block bb 803 sequentially. */ 804 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb)) 805 return false; 806 807 bitmap_set_bit (depends_on, def_data->invno); 808 return true; 809} 810 811 812/* Finds the invariants INSN depends on and store them to the DEPENDS_ON 813 bitmap. Returns true if all dependencies of INSN are known to be 814 loop invariants, false otherwise. */ 815 816static bool 817check_dependencies (rtx insn, bitmap depends_on) 818{ 819 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 820 df_ref *use_rec; 821 basic_block bb = BLOCK_FOR_INSN (insn); 822 823 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++) 824 if (!check_dependency (bb, *use_rec, depends_on)) 825 return false; 826 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++) 827 if (!check_dependency (bb, *use_rec, depends_on)) 828 return false; 829 830 return true; 831} 832 833/* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always 834 executed. ALWAYS_EXECUTED is true if the insn is always executed, 835 unless the program ends due to a function call. */ 836 837static void 838find_invariant_insn (rtx insn, bool always_reached, bool always_executed) 839{ 840 df_ref ref; 841 struct def *def; 842 bitmap depends_on; 843 rtx set, dest; 844 bool simple = true; 845 struct invariant *inv; 846 847#ifdef HAVE_cc0 848 /* We can't move a CC0 setter without the user. */ 849 if (sets_cc0_p (insn)) 850 return; 851#endif 852 853 set = single_set (insn); 854 if (!set) 855 return; 856 dest = SET_DEST (set); 857 858 if (!REG_P (dest) 859 || HARD_REGISTER_P (dest)) 860 simple = false; 861 862 if (!may_assign_reg_p (SET_DEST (set)) 863 || !check_maybe_invariant (SET_SRC (set))) 864 return; 865 866 /* If the insn can throw exception, we cannot move it at all without changing 867 cfg. */ 868 if (can_throw_internal (insn)) 869 return; 870 871 /* We cannot make trapping insn executed, unless it was executed before. */ 872 if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached) 873 return; 874 875 depends_on = BITMAP_ALLOC (NULL); 876 if (!check_dependencies (insn, depends_on)) 877 { 878 BITMAP_FREE (depends_on); 879 return; 880 } 881 882 if (simple) 883 def = XCNEW (struct def); 884 else 885 def = NULL; 886 887 inv = create_new_invariant (def, insn, depends_on, always_executed); 888 889 if (simple) 890 { 891 ref = df_find_def (insn, dest); 892 check_invariant_table_size (); 893 invariant_table[DF_REF_ID(ref)] = inv; 894 } 895} 896 897/* Record registers used in INSN that have a unique invariant definition. */ 898 899static void 900record_uses (rtx insn) 901{ 902 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 903 df_ref *use_rec; 904 struct invariant *inv; 905 906 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++) 907 { 908 df_ref use = *use_rec; 909 inv = invariant_for_use (use); 910 if (inv) 911 record_use (inv->def, use); 912 } 913 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++) 914 { 915 df_ref use = *use_rec; 916 inv = invariant_for_use (use); 917 if (inv) 918 record_use (inv->def, use); 919 } 920} 921 922/* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always 923 executed. ALWAYS_EXECUTED is true if the insn is always executed, 924 unless the program ends due to a function call. */ 925 926static void 927find_invariants_insn (rtx insn, bool always_reached, bool always_executed) 928{ 929 find_invariant_insn (insn, always_reached, always_executed); 930 record_uses (insn); 931} 932 933/* Finds invariants in basic block BB. ALWAYS_REACHED is true if the 934 basic block is always executed. ALWAYS_EXECUTED is true if the basic 935 block is always executed, unless the program ends due to a function 936 call. */ 937 938static void 939find_invariants_bb (basic_block bb, bool always_reached, bool always_executed) 940{ 941 rtx insn; 942 943 FOR_BB_INSNS (bb, insn) 944 { 945 if (!NONDEBUG_INSN_P (insn)) 946 continue; 947 948 find_invariants_insn (insn, always_reached, always_executed); 949 950 if (always_reached 951 && CALL_P (insn) 952 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn) 953 || ! RTL_CONST_OR_PURE_CALL_P (insn))) 954 always_reached = false; 955 } 956} 957 958/* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of 959 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the 960 bitmap of basic blocks in BODY that are always executed unless the program 961 ends due to a function call. */ 962 963static void 964find_invariants_body (struct loop *loop, basic_block *body, 965 bitmap always_reached, bitmap always_executed) 966{ 967 unsigned i; 968 969 for (i = 0; i < loop->num_nodes; i++) 970 find_invariants_bb (body[i], 971 bitmap_bit_p (always_reached, i), 972 bitmap_bit_p (always_executed, i)); 973} 974 975/* Finds invariants in LOOP. */ 976 977static void 978find_invariants (struct loop *loop) 979{ 980 bitmap may_exit = BITMAP_ALLOC (NULL); 981 bitmap always_reached = BITMAP_ALLOC (NULL); 982 bitmap has_exit = BITMAP_ALLOC (NULL); 983 bitmap always_executed = BITMAP_ALLOC (NULL); 984 basic_block *body = get_loop_body_in_dom_order (loop); 985 986 find_exits (loop, body, may_exit, has_exit); 987 compute_always_reached (loop, body, may_exit, always_reached); 988 compute_always_reached (loop, body, has_exit, always_executed); 989 990 find_defs (loop, body); 991 find_invariants_body (loop, body, always_reached, always_executed); 992 merge_identical_invariants (); 993 994 BITMAP_FREE (always_reached); 995 BITMAP_FREE (always_executed); 996 BITMAP_FREE (may_exit); 997 BITMAP_FREE (has_exit); 998 free (body); 999} 1000 1001/* Frees a list of uses USE. */ 1002 1003static void 1004free_use_list (struct use *use) 1005{ 1006 struct use *next; 1007 1008 for (; use; use = next) 1009 { 1010 next = use->next; 1011 free (use); 1012 } 1013} 1014 1015/* Return cover class and number of hard registers (through *NREGS) 1016 for destination of INSN. */ 1017static enum reg_class 1018get_cover_class_and_nregs (rtx insn, int *nregs) 1019{ 1020 rtx reg; 1021 enum reg_class cover_class; 1022 rtx set = single_set (insn); 1023 1024 /* Considered invariant insns have only one set. */ 1025 gcc_assert (set != NULL_RTX); 1026 reg = SET_DEST (set); 1027 if (GET_CODE (reg) == SUBREG) 1028 reg = SUBREG_REG (reg); 1029 if (MEM_P (reg)) 1030 { 1031 *nregs = 0; 1032 cover_class = NO_REGS; 1033 } 1034 else 1035 { 1036 if (! REG_P (reg)) 1037 reg = NULL_RTX; 1038 if (reg == NULL_RTX) 1039 cover_class = GENERAL_REGS; 1040 else 1041 cover_class = reg_cover_class (REGNO (reg)); 1042 *nregs = ira_reg_class_nregs[cover_class][GET_MODE (SET_SRC (set))]; 1043 } 1044 return cover_class; 1045} 1046 1047/* Calculates cost and number of registers needed for moving invariant INV 1048 out of the loop and stores them to *COST and *REGS_NEEDED. */ 1049 1050static void 1051get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed) 1052{ 1053 int i, acomp_cost; 1054 unsigned aregs_needed[N_REG_CLASSES]; 1055 unsigned depno; 1056 struct invariant *dep; 1057 bitmap_iterator bi; 1058 1059 /* Find the representative of the class of the equivalent invariants. */ 1060 inv = VEC_index (invariant_p, invariants, inv->eqto); 1061 1062 *comp_cost = 0; 1063 if (! flag_ira_loop_pressure) 1064 regs_needed[0] = 0; 1065 else 1066 { 1067 for (i = 0; i < ira_reg_class_cover_size; i++) 1068 regs_needed[ira_reg_class_cover[i]] = 0; 1069 } 1070 1071 if (inv->move 1072 || inv->stamp == actual_stamp) 1073 return; 1074 inv->stamp = actual_stamp; 1075 1076 if (! flag_ira_loop_pressure) 1077 regs_needed[0]++; 1078 else 1079 { 1080 int nregs; 1081 enum reg_class cover_class; 1082 1083 cover_class = get_cover_class_and_nregs (inv->insn, &nregs); 1084 regs_needed[cover_class] += nregs; 1085 } 1086 1087 if (!inv->cheap_address 1088 || inv->def->n_addr_uses < inv->def->n_uses) 1089 (*comp_cost) += inv->cost; 1090 1091#ifdef STACK_REGS 1092 { 1093 /* Hoisting constant pool constants into stack regs may cost more than 1094 just single register. On x87, the balance is affected both by the 1095 small number of FP registers, and by its register stack organization, 1096 that forces us to add compensation code in and around the loop to 1097 shuffle the operands to the top of stack before use, and pop them 1098 from the stack after the loop finishes. 1099 1100 To model this effect, we increase the number of registers needed for 1101 stack registers by two: one register push, and one register pop. 1102 This usually has the effect that FP constant loads from the constant 1103 pool are not moved out of the loop. 1104 1105 Note that this also means that dependent invariants can not be moved. 1106 However, the primary purpose of this pass is to move loop invariant 1107 address arithmetic out of loops, and address arithmetic that depends 1108 on floating point constants is unlikely to ever occur. */ 1109 rtx set = single_set (inv->insn); 1110 if (set 1111 && IS_STACK_MODE (GET_MODE (SET_SRC (set))) 1112 && constant_pool_constant_p (SET_SRC (set))) 1113 { 1114 if (flag_ira_loop_pressure) 1115 regs_needed[STACK_REG_COVER_CLASS] += 2; 1116 else 1117 regs_needed[0] += 2; 1118 } 1119 } 1120#endif 1121 1122 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi) 1123 { 1124 bool check_p; 1125 1126 dep = VEC_index (invariant_p, invariants, depno); 1127 1128 get_inv_cost (dep, &acomp_cost, aregs_needed); 1129 1130 if (! flag_ira_loop_pressure) 1131 check_p = aregs_needed[0] != 0; 1132 else 1133 { 1134 for (i = 0; i < ira_reg_class_cover_size; i++) 1135 if (aregs_needed[ira_reg_class_cover[i]] != 0) 1136 break; 1137 check_p = i < ira_reg_class_cover_size; 1138 } 1139 if (check_p 1140 /* We need to check always_executed, since if the original value of 1141 the invariant may be preserved, we may need to keep it in a 1142 separate register. TODO check whether the register has an 1143 use outside of the loop. */ 1144 && dep->always_executed 1145 && !dep->def->uses->next) 1146 { 1147 /* If this is a single use, after moving the dependency we will not 1148 need a new register. */ 1149 if (! flag_ira_loop_pressure) 1150 aregs_needed[0]--; 1151 else 1152 { 1153 int nregs; 1154 enum reg_class cover_class; 1155 1156 cover_class = get_cover_class_and_nregs (inv->insn, &nregs); 1157 aregs_needed[cover_class] -= nregs; 1158 } 1159 } 1160 1161 if (! flag_ira_loop_pressure) 1162 regs_needed[0] += aregs_needed[0]; 1163 else 1164 { 1165 for (i = 0; i < ira_reg_class_cover_size; i++) 1166 regs_needed[ira_reg_class_cover[i]] 1167 += aregs_needed[ira_reg_class_cover[i]]; 1168 } 1169 (*comp_cost) += acomp_cost; 1170 } 1171} 1172 1173/* Calculates gain for eliminating invariant INV. REGS_USED is the number 1174 of registers used in the loop, NEW_REGS is the number of new variables 1175 already added due to the invariant motion. The number of registers needed 1176 for it is stored in *REGS_NEEDED. */ 1177 1178static int 1179gain_for_invariant (struct invariant *inv, unsigned *regs_needed, 1180 unsigned *new_regs, unsigned regs_used, bool speed) 1181{ 1182 int comp_cost, size_cost; 1183 1184 actual_stamp++; 1185 1186 get_inv_cost (inv, &comp_cost, regs_needed); 1187 1188 if (! flag_ira_loop_pressure) 1189 { 1190 size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0], 1191 regs_used, speed) 1192 - estimate_reg_pressure_cost (new_regs[0], 1193 regs_used, speed)); 1194 } 1195 else 1196 { 1197 int i; 1198 enum reg_class cover_class; 1199 1200 for (i = 0; i < ira_reg_class_cover_size; i++) 1201 { 1202 cover_class = ira_reg_class_cover[i]; 1203 if ((int) new_regs[cover_class] 1204 + (int) regs_needed[cover_class] 1205 + LOOP_DATA (curr_loop)->max_reg_pressure[cover_class] 1206 + IRA_LOOP_RESERVED_REGS 1207 > ira_available_class_regs[cover_class]) 1208 break; 1209 } 1210 if (i < ira_reg_class_cover_size) 1211 /* There will be register pressure excess and we want not to 1212 make this loop invariant motion. All loop invariants with 1213 non-positive gains will be rejected in function 1214 find_invariants_to_move. Therefore we return the negative 1215 number here. 1216 1217 One could think that this rejects also expensive loop 1218 invariant motions and this will hurt code performance. 1219 However numerous experiments with different heuristics 1220 taking invariant cost into account did not confirm this 1221 assumption. There are possible explanations for this 1222 result: 1223 o probably all expensive invariants were already moved out 1224 of the loop by PRE and gimple invariant motion pass. 1225 o expensive invariant execution will be hidden by insn 1226 scheduling or OOO processor hardware because usually such 1227 invariants have a lot of freedom to be executed 1228 out-of-order. 1229 Another reason for ignoring invariant cost vs spilling cost 1230 heuristics is also in difficulties to evaluate accurately 1231 spill cost at this stage. */ 1232 return -1; 1233 else 1234 size_cost = 0; 1235 } 1236 1237 return comp_cost - size_cost; 1238} 1239 1240/* Finds invariant with best gain for moving. Returns the gain, stores 1241 the invariant in *BEST and number of registers needed for it to 1242 *REGS_NEEDED. REGS_USED is the number of registers used in the loop. 1243 NEW_REGS is the number of new variables already added due to invariant 1244 motion. */ 1245 1246static int 1247best_gain_for_invariant (struct invariant **best, unsigned *regs_needed, 1248 unsigned *new_regs, unsigned regs_used, bool speed) 1249{ 1250 struct invariant *inv; 1251 int i, gain = 0, again; 1252 unsigned aregs_needed[N_REG_CLASSES], invno; 1253 1254 for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++) 1255 { 1256 if (inv->move) 1257 continue; 1258 1259 /* Only consider the "representatives" of equivalent invariants. */ 1260 if (inv->eqto != inv->invno) 1261 continue; 1262 1263 again = gain_for_invariant (inv, aregs_needed, new_regs, regs_used, 1264 speed); 1265 if (again > gain) 1266 { 1267 gain = again; 1268 *best = inv; 1269 if (! flag_ira_loop_pressure) 1270 regs_needed[0] = aregs_needed[0]; 1271 else 1272 { 1273 for (i = 0; i < ira_reg_class_cover_size; i++) 1274 regs_needed[ira_reg_class_cover[i]] 1275 = aregs_needed[ira_reg_class_cover[i]]; 1276 } 1277 } 1278 } 1279 1280 return gain; 1281} 1282 1283/* Marks invariant INVNO and all its dependencies for moving. */ 1284 1285static void 1286set_move_mark (unsigned invno, int gain) 1287{ 1288 struct invariant *inv = VEC_index (invariant_p, invariants, invno); 1289 bitmap_iterator bi; 1290 1291 /* Find the representative of the class of the equivalent invariants. */ 1292 inv = VEC_index (invariant_p, invariants, inv->eqto); 1293 1294 if (inv->move) 1295 return; 1296 inv->move = true; 1297 1298 if (dump_file) 1299 { 1300 if (gain >= 0) 1301 fprintf (dump_file, "Decided to move invariant %d -- gain %d\n", 1302 invno, gain); 1303 else 1304 fprintf (dump_file, "Decided to move dependent invariant %d\n", 1305 invno); 1306 }; 1307 1308 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi) 1309 { 1310 set_move_mark (invno, -1); 1311 } 1312} 1313 1314/* Determines which invariants to move. */ 1315 1316static void 1317find_invariants_to_move (bool speed) 1318{ 1319 int gain; 1320 unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES]; 1321 struct invariant *inv = NULL; 1322 1323 if (!VEC_length (invariant_p, invariants)) 1324 return; 1325 1326 if (flag_ira_loop_pressure) 1327 /* REGS_USED is actually never used when the flag is on. */ 1328 regs_used = 0; 1329 else 1330 /* We do not really do a good job in estimating number of 1331 registers used; we put some initial bound here to stand for 1332 induction variables etc. that we do not detect. */ 1333 { 1334 unsigned int n_regs = DF_REG_SIZE (df); 1335 1336 regs_used = 2; 1337 1338 for (i = 0; i < n_regs; i++) 1339 { 1340 if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i)) 1341 { 1342 /* This is a value that is used but not changed inside loop. */ 1343 regs_used++; 1344 } 1345 } 1346 } 1347 1348 if (! flag_ira_loop_pressure) 1349 new_regs[0] = regs_needed[0] = 0; 1350 else 1351 { 1352 for (i = 0; (int) i < ira_reg_class_cover_size; i++) 1353 new_regs[ira_reg_class_cover[i]] = 0; 1354 } 1355 while ((gain = best_gain_for_invariant (&inv, regs_needed, 1356 new_regs, regs_used, speed)) > 0) 1357 { 1358 set_move_mark (inv->invno, gain); 1359 if (! flag_ira_loop_pressure) 1360 new_regs[0] += regs_needed[0]; 1361 else 1362 { 1363 for (i = 0; (int) i < ira_reg_class_cover_size; i++) 1364 new_regs[ira_reg_class_cover[i]] 1365 += regs_needed[ira_reg_class_cover[i]]; 1366 } 1367 } 1368} 1369 1370/* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false 1371 otherwise. */ 1372 1373static bool 1374move_invariant_reg (struct loop *loop, unsigned invno) 1375{ 1376 struct invariant *inv = VEC_index (invariant_p, invariants, invno); 1377 struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto); 1378 unsigned i; 1379 basic_block preheader = loop_preheader_edge (loop)->src; 1380 rtx reg, set, dest, note; 1381 struct use *use; 1382 bitmap_iterator bi; 1383 int regno; 1384 1385 if (inv->reg) 1386 return true; 1387 if (!repr->move) 1388 return false; 1389 regno = -1; 1390 /* If this is a representative of the class of equivalent invariants, 1391 really move the invariant. Otherwise just replace its use with 1392 the register used for the representative. */ 1393 if (inv == repr) 1394 { 1395 if (inv->depends_on) 1396 { 1397 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi) 1398 { 1399 if (!move_invariant_reg (loop, i)) 1400 goto fail; 1401 } 1402 } 1403 1404 /* Move the set out of the loop. If the set is always executed (we could 1405 omit this condition if we know that the register is unused outside of the 1406 loop, but it does not seem worth finding out) and it has no uses that 1407 would not be dominated by it, we may just move it (TODO). Otherwise we 1408 need to create a temporary register. */ 1409 set = single_set (inv->insn); 1410 reg = dest = SET_DEST (set); 1411 if (GET_CODE (reg) == SUBREG) 1412 reg = SUBREG_REG (reg); 1413 if (REG_P (reg)) 1414 regno = REGNO (reg); 1415 1416 reg = gen_reg_rtx_and_attrs (dest); 1417 1418 /* Try replacing the destination by a new pseudoregister. */ 1419 if (!validate_change (inv->insn, &SET_DEST (set), reg, false)) 1420 goto fail; 1421 df_insn_rescan (inv->insn); 1422 1423 emit_insn_after (gen_move_insn (dest, reg), inv->insn); 1424 reorder_insns (inv->insn, inv->insn, BB_END (preheader)); 1425 1426 /* If there is a REG_EQUAL note on the insn we just moved, and the 1427 insn is in a basic block that is not always executed or the note 1428 contains something for which we don't know the invariant status, 1429 the note may no longer be valid after we move the insn. Note that 1430 uses in REG_EQUAL notes are taken into account in the computation 1431 of invariants, so it is safe to retain the note even if it contains 1432 register references for which we know the invariant status. */ 1433 if ((note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX)) 1434 && (!inv->always_executed 1435 || !check_maybe_invariant (XEXP (note, 0)))) 1436 remove_note (inv->insn, note); 1437 } 1438 else 1439 { 1440 if (!move_invariant_reg (loop, repr->invno)) 1441 goto fail; 1442 reg = repr->reg; 1443 regno = repr->orig_regno; 1444 set = single_set (inv->insn); 1445 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn); 1446 delete_insn (inv->insn); 1447 } 1448 1449 1450 inv->reg = reg; 1451 inv->orig_regno = regno; 1452 1453 /* Replace the uses we know to be dominated. It saves work for copy 1454 propagation, and also it is necessary so that dependent invariants 1455 are computed right. */ 1456 if (inv->def) 1457 { 1458 for (use = inv->def->uses; use; use = use->next) 1459 { 1460 *use->pos = reg; 1461 df_insn_rescan (use->insn); 1462 } 1463 } 1464 1465 return true; 1466 1467fail: 1468 /* If we failed, clear move flag, so that we do not try to move inv 1469 again. */ 1470 if (dump_file) 1471 fprintf (dump_file, "Failed to move invariant %d\n", invno); 1472 inv->move = false; 1473 inv->reg = NULL_RTX; 1474 inv->orig_regno = -1; 1475 1476 return false; 1477} 1478 1479/* Move selected invariant out of the LOOP. Newly created regs are marked 1480 in TEMPORARY_REGS. */ 1481 1482static void 1483move_invariants (struct loop *loop) 1484{ 1485 struct invariant *inv; 1486 unsigned i; 1487 1488 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) 1489 move_invariant_reg (loop, i); 1490 if (flag_ira_loop_pressure && resize_reg_info ()) 1491 { 1492 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) 1493 if (inv->reg != NULL_RTX) 1494 { 1495 if (inv->orig_regno >= 0) 1496 setup_reg_classes (REGNO (inv->reg), 1497 reg_preferred_class (inv->orig_regno), 1498 reg_alternate_class (inv->orig_regno), 1499 reg_cover_class (inv->orig_regno)); 1500 else 1501 setup_reg_classes (REGNO (inv->reg), 1502 GENERAL_REGS, NO_REGS, GENERAL_REGS); 1503 } 1504 } 1505} 1506 1507/* Initializes invariant motion data. */ 1508 1509static void 1510init_inv_motion_data (void) 1511{ 1512 actual_stamp = 1; 1513 1514 invariants = VEC_alloc (invariant_p, heap, 100); 1515} 1516 1517/* Frees the data allocated by invariant motion. */ 1518 1519static void 1520free_inv_motion_data (void) 1521{ 1522 unsigned i; 1523 struct def *def; 1524 struct invariant *inv; 1525 1526 check_invariant_table_size (); 1527 for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++) 1528 { 1529 inv = invariant_table[i]; 1530 if (inv) 1531 { 1532 def = inv->def; 1533 gcc_assert (def != NULL); 1534 1535 free_use_list (def->uses); 1536 free (def); 1537 invariant_table[i] = NULL; 1538 } 1539 } 1540 1541 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) 1542 { 1543 BITMAP_FREE (inv->depends_on); 1544 free (inv); 1545 } 1546 VEC_free (invariant_p, heap, invariants); 1547} 1548 1549/* Move the invariants out of the LOOP. */ 1550 1551static void 1552move_single_loop_invariants (struct loop *loop) 1553{ 1554 init_inv_motion_data (); 1555 1556 find_invariants (loop); 1557 find_invariants_to_move (optimize_loop_for_speed_p (loop)); 1558 move_invariants (loop); 1559 1560 free_inv_motion_data (); 1561} 1562 1563/* Releases the auxiliary data for LOOP. */ 1564 1565static void 1566free_loop_data (struct loop *loop) 1567{ 1568 struct loop_data *data = LOOP_DATA (loop); 1569 if (!data) 1570 return; 1571 1572 bitmap_clear (&LOOP_DATA (loop)->regs_ref); 1573 bitmap_clear (&LOOP_DATA (loop)->regs_live); 1574 free (data); 1575 loop->aux = NULL; 1576} 1577 1578 1579 1580/* Registers currently living. */ 1581static bitmap_head curr_regs_live; 1582 1583/* Current reg pressure for each cover class. */ 1584static int curr_reg_pressure[N_REG_CLASSES]; 1585 1586/* Record all regs that are set in any one insn. Communication from 1587 mark_reg_{store,clobber} and global_conflicts. Asm can refer to 1588 all hard-registers. */ 1589static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS 1590 ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2]; 1591/* Number of regs stored in the previous array. */ 1592static int n_regs_set; 1593 1594/* Return cover class and number of needed hard registers (through 1595 *NREGS) of register REGNO. */ 1596static enum reg_class 1597get_regno_cover_class (int regno, int *nregs) 1598{ 1599 if (regno >= FIRST_PSEUDO_REGISTER) 1600 { 1601 enum reg_class cover_class = reg_cover_class (regno); 1602 1603 *nregs = ira_reg_class_nregs[cover_class][PSEUDO_REGNO_MODE (regno)]; 1604 return cover_class; 1605 } 1606 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno) 1607 && ! TEST_HARD_REG_BIT (eliminable_regset, regno)) 1608 { 1609 *nregs = 1; 1610 return ira_class_translate[REGNO_REG_CLASS (regno)]; 1611 } 1612 else 1613 { 1614 *nregs = 0; 1615 return NO_REGS; 1616 } 1617} 1618 1619/* Increase (if INCR_P) or decrease current register pressure for 1620 register REGNO. */ 1621static void 1622change_pressure (int regno, bool incr_p) 1623{ 1624 int nregs; 1625 enum reg_class cover_class; 1626 1627 cover_class = get_regno_cover_class (regno, &nregs); 1628 if (! incr_p) 1629 curr_reg_pressure[cover_class] -= nregs; 1630 else 1631 { 1632 curr_reg_pressure[cover_class] += nregs; 1633 if (LOOP_DATA (curr_loop)->max_reg_pressure[cover_class] 1634 < curr_reg_pressure[cover_class]) 1635 LOOP_DATA (curr_loop)->max_reg_pressure[cover_class] 1636 = curr_reg_pressure[cover_class]; 1637 } 1638} 1639 1640/* Mark REGNO birth. */ 1641static void 1642mark_regno_live (int regno) 1643{ 1644 struct loop *loop; 1645 1646 for (loop = curr_loop; 1647 loop != current_loops->tree_root; 1648 loop = loop_outer (loop)) 1649 bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno); 1650 if (bitmap_bit_p (&curr_regs_live, regno)) 1651 return; 1652 bitmap_set_bit (&curr_regs_live, regno); 1653 change_pressure (regno, true); 1654} 1655 1656/* Mark REGNO death. */ 1657static void 1658mark_regno_death (int regno) 1659{ 1660 if (! bitmap_bit_p (&curr_regs_live, regno)) 1661 return; 1662 bitmap_clear_bit (&curr_regs_live, regno); 1663 change_pressure (regno, false); 1664} 1665 1666/* Mark setting register REG. */ 1667static void 1668mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED, 1669 void *data ATTRIBUTE_UNUSED) 1670{ 1671 int regno; 1672 1673 if (GET_CODE (reg) == SUBREG) 1674 reg = SUBREG_REG (reg); 1675 1676 if (! REG_P (reg)) 1677 return; 1678 1679 regs_set[n_regs_set++] = reg; 1680 1681 regno = REGNO (reg); 1682 1683 if (regno >= FIRST_PSEUDO_REGISTER) 1684 mark_regno_live (regno); 1685 else 1686 { 1687 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)]; 1688 1689 while (regno < last) 1690 { 1691 mark_regno_live (regno); 1692 regno++; 1693 } 1694 } 1695} 1696 1697/* Mark clobbering register REG. */ 1698static void 1699mark_reg_clobber (rtx reg, const_rtx setter, void *data) 1700{ 1701 if (GET_CODE (setter) == CLOBBER) 1702 mark_reg_store (reg, setter, data); 1703} 1704 1705/* Mark register REG death. */ 1706static void 1707mark_reg_death (rtx reg) 1708{ 1709 int regno = REGNO (reg); 1710 1711 if (regno >= FIRST_PSEUDO_REGISTER) 1712 mark_regno_death (regno); 1713 else 1714 { 1715 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)]; 1716 1717 while (regno < last) 1718 { 1719 mark_regno_death (regno); 1720 regno++; 1721 } 1722 } 1723} 1724 1725/* Mark occurrence of registers in X for the current loop. */ 1726static void 1727mark_ref_regs (rtx x) 1728{ 1729 RTX_CODE code; 1730 int i; 1731 const char *fmt; 1732 1733 if (!x) 1734 return; 1735 1736 code = GET_CODE (x); 1737 if (code == REG) 1738 { 1739 struct loop *loop; 1740 1741 for (loop = curr_loop; 1742 loop != current_loops->tree_root; 1743 loop = loop_outer (loop)) 1744 bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x)); 1745 return; 1746 } 1747 1748 fmt = GET_RTX_FORMAT (code); 1749 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1750 if (fmt[i] == 'e') 1751 mark_ref_regs (XEXP (x, i)); 1752 else if (fmt[i] == 'E') 1753 { 1754 int j; 1755 1756 for (j = 0; j < XVECLEN (x, i); j++) 1757 mark_ref_regs (XVECEXP (x, i, j)); 1758 } 1759} 1760 1761/* Calculate register pressure in the loops. */ 1762static void 1763calculate_loop_reg_pressure (void) 1764{ 1765 int i; 1766 unsigned int j; 1767 bitmap_iterator bi; 1768 basic_block bb; 1769 rtx insn, link; 1770 struct loop *loop, *parent; 1771 loop_iterator li; 1772 1773 FOR_EACH_LOOP (li, loop, 0) 1774 if (loop->aux == NULL) 1775 { 1776 loop->aux = xcalloc (1, sizeof (struct loop_data)); 1777 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, ®_obstack); 1778 bitmap_initialize (&LOOP_DATA (loop)->regs_live, ®_obstack); 1779 } 1780 ira_setup_eliminable_regset (); 1781 bitmap_initialize (&curr_regs_live, ®_obstack); 1782 FOR_EACH_BB (bb) 1783 { 1784 curr_loop = bb->loop_father; 1785 if (curr_loop == current_loops->tree_root) 1786 continue; 1787 1788 for (loop = curr_loop; 1789 loop != current_loops->tree_root; 1790 loop = loop_outer (loop)) 1791 bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb)); 1792 1793 bitmap_copy (&curr_regs_live, DF_LR_IN (bb)); 1794 for (i = 0; i < ira_reg_class_cover_size; i++) 1795 curr_reg_pressure[ira_reg_class_cover[i]] = 0; 1796 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi) 1797 change_pressure (j, true); 1798 1799 FOR_BB_INSNS (bb, insn) 1800 { 1801 if (! NONDEBUG_INSN_P (insn)) 1802 continue; 1803 1804 mark_ref_regs (PATTERN (insn)); 1805 n_regs_set = 0; 1806 note_stores (PATTERN (insn), mark_reg_clobber, NULL); 1807 1808 /* Mark any registers dead after INSN as dead now. */ 1809 1810 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 1811 if (REG_NOTE_KIND (link) == REG_DEAD) 1812 mark_reg_death (XEXP (link, 0)); 1813 1814 /* Mark any registers set in INSN as live, 1815 and mark them as conflicting with all other live regs. 1816 Clobbers are processed again, so they conflict with 1817 the registers that are set. */ 1818 1819 note_stores (PATTERN (insn), mark_reg_store, NULL); 1820 1821#ifdef AUTO_INC_DEC 1822 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 1823 if (REG_NOTE_KIND (link) == REG_INC) 1824 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL); 1825#endif 1826 while (n_regs_set-- > 0) 1827 { 1828 rtx note = find_regno_note (insn, REG_UNUSED, 1829 REGNO (regs_set[n_regs_set])); 1830 if (! note) 1831 continue; 1832 1833 mark_reg_death (XEXP (note, 0)); 1834 } 1835 } 1836 } 1837 bitmap_clear (&curr_regs_live); 1838 if (flag_ira_region == IRA_REGION_MIXED 1839 || flag_ira_region == IRA_REGION_ALL) 1840 FOR_EACH_LOOP (li, loop, 0) 1841 { 1842 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi) 1843 if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j)) 1844 { 1845 enum reg_class cover_class; 1846 int nregs; 1847 1848 cover_class = get_regno_cover_class (j, &nregs); 1849 LOOP_DATA (loop)->max_reg_pressure[cover_class] -= nregs; 1850 } 1851 } 1852 if (dump_file == NULL) 1853 return; 1854 FOR_EACH_LOOP (li, loop, 0) 1855 { 1856 parent = loop_outer (loop); 1857 fprintf (dump_file, "\n Loop %d (parent %d, header bb%d, depth %d)\n", 1858 loop->num, (parent == NULL ? -1 : parent->num), 1859 loop->header->index, loop_depth (loop)); 1860 fprintf (dump_file, "\n ref. regnos:"); 1861 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi) 1862 fprintf (dump_file, " %d", j); 1863 fprintf (dump_file, "\n live regnos:"); 1864 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi) 1865 fprintf (dump_file, " %d", j); 1866 fprintf (dump_file, "\n Pressure:"); 1867 for (i = 0; (int) i < ira_reg_class_cover_size; i++) 1868 { 1869 enum reg_class cover_class; 1870 1871 cover_class = ira_reg_class_cover[i]; 1872 if (LOOP_DATA (loop)->max_reg_pressure[cover_class] == 0) 1873 continue; 1874 fprintf (dump_file, " %s=%d", reg_class_names[cover_class], 1875 LOOP_DATA (loop)->max_reg_pressure[cover_class]); 1876 } 1877 fprintf (dump_file, "\n"); 1878 } 1879} 1880 1881 1882 1883/* Move the invariants out of the loops. */ 1884 1885void 1886move_loop_invariants (void) 1887{ 1888 struct loop *loop; 1889 loop_iterator li; 1890 1891 if (flag_ira_loop_pressure) 1892 { 1893 df_analyze (); 1894 ira_set_pseudo_classes (dump_file); 1895 calculate_loop_reg_pressure (); 1896 } 1897 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN); 1898 /* Process the loops, innermost first. */ 1899 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) 1900 { 1901 curr_loop = loop; 1902 /* move_single_loop_invariants for very large loops 1903 is time consuming and might need a lot of memory. */ 1904 if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP) 1905 move_single_loop_invariants (loop); 1906 } 1907 1908 FOR_EACH_LOOP (li, loop, 0) 1909 { 1910 free_loop_data (loop); 1911 } 1912 1913 if (flag_ira_loop_pressure) 1914 /* There is no sense to keep this info because it was most 1915 probably outdated by subsequent passes. */ 1916 free_reg_info (); 1917 free (invariant_table); 1918 invariant_table = NULL; 1919 invariant_table_size = 0; 1920 1921#ifdef ENABLE_CHECKING 1922 verify_flow_info (); 1923#endif 1924} 1925