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