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