1/* Allocate registers within a basic block, for GNU compiler. 2 Copyright (C) 1987, 1988, 1991, 1993, 1994, 1995, 1996, 1997, 1998, 3 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22/* Allocation of hard register numbers to pseudo registers is done in 23 two passes. In this pass we consider only regs that are born and 24 die once within one basic block. We do this one basic block at a 25 time. Then the next pass allocates the registers that remain. 26 Two passes are used because this pass uses methods that work only 27 on linear code, but that do a better job than the general methods 28 used in global_alloc, and more quickly too. 29 30 The assignments made are recorded in the vector reg_renumber 31 whose space is allocated here. The rtl code itself is not altered. 32 33 We assign each instruction in the basic block a number 34 which is its order from the beginning of the block. 35 Then we can represent the lifetime of a pseudo register with 36 a pair of numbers, and check for conflicts easily. 37 We can record the availability of hard registers with a 38 HARD_REG_SET for each instruction. The HARD_REG_SET 39 contains 0 or 1 for each hard reg. 40 41 To avoid register shuffling, we tie registers together when one 42 dies by being copied into another, or dies in an instruction that 43 does arithmetic to produce another. The tied registers are 44 allocated as one. Registers with different reg class preferences 45 can never be tied unless the class preferred by one is a subclass 46 of the one preferred by the other. 47 48 Tying is represented with "quantity numbers". 49 A non-tied register is given a new quantity number. 50 Tied registers have the same quantity number. 51 52 We have provision to exempt registers, even when they are contained 53 within the block, that can be tied to others that are not contained in it. 54 This is so that global_alloc could process them both and tie them then. 55 But this is currently disabled since tying in global_alloc is not 56 yet implemented. */ 57 58/* Pseudos allocated here can be reallocated by global.c if the hard register 59 is used as a spill register. Currently we don't allocate such pseudos 60 here if their preferred class is likely to be used by spills. */ 61 62#include "config.h" 63#include "system.h" 64#include "coretypes.h" 65#include "tm.h" 66#include "hard-reg-set.h" 67#include "rtl.h" 68#include "tm_p.h" 69#include "flags.h" 70#include "regs.h" 71#include "function.h" 72#include "insn-config.h" 73#include "insn-attr.h" 74#include "recog.h" 75#include "output.h" 76#include "toplev.h" 77#include "except.h" 78#include "integrate.h" 79#include "reload.h" 80#include "ggc.h" 81#include "timevar.h" 82#include "tree-pass.h" 83 84/* Next quantity number available for allocation. */ 85 86static int next_qty; 87 88/* Information we maintain about each quantity. */ 89struct qty 90{ 91 /* The number of refs to quantity Q. */ 92 93 int n_refs; 94 95 /* The frequency of uses of quantity Q. */ 96 97 int freq; 98 99 /* Insn number (counting from head of basic block) 100 where quantity Q was born. -1 if birth has not been recorded. */ 101 102 int birth; 103 104 /* Insn number (counting from head of basic block) 105 where given quantity died. Due to the way tying is done, 106 and the fact that we consider in this pass only regs that die but once, 107 a quantity can die only once. Each quantity's life span 108 is a set of consecutive insns. -1 if death has not been recorded. */ 109 110 int death; 111 112 /* Number of words needed to hold the data in given quantity. 113 This depends on its machine mode. It is used for these purposes: 114 1. It is used in computing the relative importance of qtys, 115 which determines the order in which we look for regs for them. 116 2. It is used in rules that prevent tying several registers of 117 different sizes in a way that is geometrically impossible 118 (see combine_regs). */ 119 120 int size; 121 122 /* Number of times a reg tied to given qty lives across a CALL_INSN. */ 123 124 int n_calls_crossed; 125 126 /* Number of times a reg tied to given qty lives across a CALL_INSN 127 that might throw. */ 128 129 int n_throwing_calls_crossed; 130 131 /* The register number of one pseudo register whose reg_qty value is Q. 132 This register should be the head of the chain 133 maintained in reg_next_in_qty. */ 134 135 int first_reg; 136 137 /* Reg class contained in (smaller than) the preferred classes of all 138 the pseudo regs that are tied in given quantity. 139 This is the preferred class for allocating that quantity. */ 140 141 enum reg_class min_class; 142 143 /* Register class within which we allocate given qty if we can't get 144 its preferred class. */ 145 146 enum reg_class alternate_class; 147 148 /* This holds the mode of the registers that are tied to given qty, 149 or VOIDmode if registers with differing modes are tied together. */ 150 151 enum machine_mode mode; 152 153 /* the hard reg number chosen for given quantity, 154 or -1 if none was found. */ 155 156 short phys_reg; 157}; 158 159static struct qty *qty; 160 161/* These fields are kept separately to speedup their clearing. */ 162 163/* We maintain two hard register sets that indicate suggested hard registers 164 for each quantity. The first, phys_copy_sugg, contains hard registers 165 that are tied to the quantity by a simple copy. The second contains all 166 hard registers that are tied to the quantity via an arithmetic operation. 167 168 The former register set is given priority for allocation. This tends to 169 eliminate copy insns. */ 170 171/* Element Q is a set of hard registers that are suggested for quantity Q by 172 copy insns. */ 173 174static HARD_REG_SET *qty_phys_copy_sugg; 175 176/* Element Q is a set of hard registers that are suggested for quantity Q by 177 arithmetic insns. */ 178 179static HARD_REG_SET *qty_phys_sugg; 180 181/* Element Q is the number of suggested registers in qty_phys_copy_sugg. */ 182 183static short *qty_phys_num_copy_sugg; 184 185/* Element Q is the number of suggested registers in qty_phys_sugg. */ 186 187static short *qty_phys_num_sugg; 188 189/* If (REG N) has been assigned a quantity number, is a register number 190 of another register assigned the same quantity number, or -1 for the 191 end of the chain. qty->first_reg point to the head of this chain. */ 192 193static int *reg_next_in_qty; 194 195/* reg_qty[N] (where N is a pseudo reg number) is the qty number of that reg 196 if it is >= 0, 197 of -1 if this register cannot be allocated by local-alloc, 198 or -2 if not known yet. 199 200 Note that if we see a use or death of pseudo register N with 201 reg_qty[N] == -2, register N must be local to the current block. If 202 it were used in more than one block, we would have reg_qty[N] == -1. 203 This relies on the fact that if reg_basic_block[N] is >= 0, register N 204 will not appear in any other block. We save a considerable number of 205 tests by exploiting this. 206 207 If N is < FIRST_PSEUDO_REGISTER, reg_qty[N] is undefined and should not 208 be referenced. */ 209 210static int *reg_qty; 211 212/* The offset (in words) of register N within its quantity. 213 This can be nonzero if register N is SImode, and has been tied 214 to a subreg of a DImode register. */ 215 216static char *reg_offset; 217 218/* Vector of substitutions of register numbers, 219 used to map pseudo regs into hardware regs. 220 This is set up as a result of register allocation. 221 Element N is the hard reg assigned to pseudo reg N, 222 or is -1 if no hard reg was assigned. 223 If N is a hard reg number, element N is N. */ 224 225short *reg_renumber; 226 227/* Set of hard registers live at the current point in the scan 228 of the instructions in a basic block. */ 229 230static HARD_REG_SET regs_live; 231 232/* Each set of hard registers indicates registers live at a particular 233 point in the basic block. For N even, regs_live_at[N] says which 234 hard registers are needed *after* insn N/2 (i.e., they may not 235 conflict with the outputs of insn N/2 or the inputs of insn N/2 + 1. 236 237 If an object is to conflict with the inputs of insn J but not the 238 outputs of insn J + 1, we say it is born at index J*2 - 1. Similarly, 239 if it is to conflict with the outputs of insn J but not the inputs of 240 insn J + 1, it is said to die at index J*2 + 1. */ 241 242static HARD_REG_SET *regs_live_at; 243 244/* Communicate local vars `insn_number' and `insn' 245 from `block_alloc' to `reg_is_set', `wipe_dead_reg', and `alloc_qty'. */ 246static int this_insn_number; 247static rtx this_insn; 248 249struct equivalence 250{ 251 /* Set when an attempt should be made to replace a register 252 with the associated src_p entry. */ 253 254 char replace; 255 256 /* Set when a REG_EQUIV note is found or created. Use to 257 keep track of what memory accesses might be created later, 258 e.g. by reload. */ 259 260 rtx replacement; 261 262 rtx *src_p; 263 264 /* Loop depth is used to recognize equivalences which appear 265 to be present within the same loop (or in an inner loop). */ 266 267 int loop_depth; 268 269 /* The list of each instruction which initializes this register. */ 270 271 rtx init_insns; 272 273 /* Nonzero if this had a preexisting REG_EQUIV note. */ 274 275 int is_arg_equivalence; 276}; 277 278/* reg_equiv[N] (where N is a pseudo reg number) is the equivalence 279 structure for that register. */ 280 281static struct equivalence *reg_equiv; 282 283/* Nonzero if we recorded an equivalence for a LABEL_REF. */ 284static int recorded_label_ref; 285 286static void alloc_qty (int, enum machine_mode, int, int); 287static void validate_equiv_mem_from_store (rtx, rtx, void *); 288static int validate_equiv_mem (rtx, rtx, rtx); 289static int equiv_init_varies_p (rtx); 290static int equiv_init_movable_p (rtx, int); 291static int contains_replace_regs (rtx); 292static int memref_referenced_p (rtx, rtx); 293static int memref_used_between_p (rtx, rtx, rtx); 294static void update_equiv_regs (void); 295static void no_equiv (rtx, rtx, void *); 296static void block_alloc (int); 297static int qty_sugg_compare (int, int); 298static int qty_sugg_compare_1 (const void *, const void *); 299static int qty_compare (int, int); 300static int qty_compare_1 (const void *, const void *); 301static int combine_regs (rtx, rtx, int, int, rtx, int); 302static int reg_meets_class_p (int, enum reg_class); 303static void update_qty_class (int, int); 304static void reg_is_set (rtx, rtx, void *); 305static void reg_is_born (rtx, int); 306static void wipe_dead_reg (rtx, int); 307static int find_free_reg (enum reg_class, enum machine_mode, int, int, int, 308 int, int); 309static void mark_life (int, enum machine_mode, int); 310static void post_mark_life (int, enum machine_mode, int, int, int); 311static int no_conflict_p (rtx, rtx, rtx); 312static int requires_inout (const char *); 313 314/* Allocate a new quantity (new within current basic block) 315 for register number REGNO which is born at index BIRTH 316 within the block. MODE and SIZE are info on reg REGNO. */ 317 318static void 319alloc_qty (int regno, enum machine_mode mode, int size, int birth) 320{ 321 int qtyno = next_qty++; 322 323 reg_qty[regno] = qtyno; 324 reg_offset[regno] = 0; 325 reg_next_in_qty[regno] = -1; 326 327 qty[qtyno].first_reg = regno; 328 qty[qtyno].size = size; 329 qty[qtyno].mode = mode; 330 qty[qtyno].birth = birth; 331 qty[qtyno].n_calls_crossed = REG_N_CALLS_CROSSED (regno); 332 qty[qtyno].n_throwing_calls_crossed = REG_N_THROWING_CALLS_CROSSED (regno); 333 qty[qtyno].min_class = reg_preferred_class (regno); 334 qty[qtyno].alternate_class = reg_alternate_class (regno); 335 qty[qtyno].n_refs = REG_N_REFS (regno); 336 qty[qtyno].freq = REG_FREQ (regno); 337} 338 339/* Main entry point of this file. */ 340 341int 342local_alloc (void) 343{ 344 int i; 345 int max_qty; 346 basic_block b; 347 348 /* We need to keep track of whether or not we recorded a LABEL_REF so 349 that we know if the jump optimizer needs to be rerun. */ 350 recorded_label_ref = 0; 351 352 /* Leaf functions and non-leaf functions have different needs. 353 If defined, let the machine say what kind of ordering we 354 should use. */ 355#ifdef ORDER_REGS_FOR_LOCAL_ALLOC 356 ORDER_REGS_FOR_LOCAL_ALLOC; 357#endif 358 359 /* Promote REG_EQUAL notes to REG_EQUIV notes and adjust status of affected 360 registers. */ 361 update_equiv_regs (); 362 363 /* This sets the maximum number of quantities we can have. Quantity 364 numbers start at zero and we can have one for each pseudo. */ 365 max_qty = (max_regno - FIRST_PSEUDO_REGISTER); 366 367 /* Allocate vectors of temporary data. 368 See the declarations of these variables, above, 369 for what they mean. */ 370 371 qty = xmalloc (max_qty * sizeof (struct qty)); 372 qty_phys_copy_sugg = xmalloc (max_qty * sizeof (HARD_REG_SET)); 373 qty_phys_num_copy_sugg = xmalloc (max_qty * sizeof (short)); 374 qty_phys_sugg = xmalloc (max_qty * sizeof (HARD_REG_SET)); 375 qty_phys_num_sugg = xmalloc (max_qty * sizeof (short)); 376 377 reg_qty = xmalloc (max_regno * sizeof (int)); 378 reg_offset = xmalloc (max_regno * sizeof (char)); 379 reg_next_in_qty = xmalloc (max_regno * sizeof (int)); 380 381 /* Determine which pseudo-registers can be allocated by local-alloc. 382 In general, these are the registers used only in a single block and 383 which only die once. 384 385 We need not be concerned with which block actually uses the register 386 since we will never see it outside that block. */ 387 388 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 389 { 390 if (REG_BASIC_BLOCK (i) >= 0 && REG_N_DEATHS (i) == 1) 391 reg_qty[i] = -2; 392 else 393 reg_qty[i] = -1; 394 } 395 396 /* Force loop below to initialize entire quantity array. */ 397 next_qty = max_qty; 398 399 /* Allocate each block's local registers, block by block. */ 400 401 FOR_EACH_BB (b) 402 { 403 /* NEXT_QTY indicates which elements of the `qty_...' 404 vectors might need to be initialized because they were used 405 for the previous block; it is set to the entire array before 406 block 0. Initialize those, with explicit loop if there are few, 407 else with bzero and bcopy. Do not initialize vectors that are 408 explicit set by `alloc_qty'. */ 409 410 if (next_qty < 6) 411 { 412 for (i = 0; i < next_qty; i++) 413 { 414 CLEAR_HARD_REG_SET (qty_phys_copy_sugg[i]); 415 qty_phys_num_copy_sugg[i] = 0; 416 CLEAR_HARD_REG_SET (qty_phys_sugg[i]); 417 qty_phys_num_sugg[i] = 0; 418 } 419 } 420 else 421 { 422#define CLEAR(vector) \ 423 memset ((vector), 0, (sizeof (*(vector))) * next_qty); 424 425 CLEAR (qty_phys_copy_sugg); 426 CLEAR (qty_phys_num_copy_sugg); 427 CLEAR (qty_phys_sugg); 428 CLEAR (qty_phys_num_sugg); 429 } 430 431 next_qty = 0; 432 433 block_alloc (b->index); 434 } 435 436 free (qty); 437 free (qty_phys_copy_sugg); 438 free (qty_phys_num_copy_sugg); 439 free (qty_phys_sugg); 440 free (qty_phys_num_sugg); 441 442 free (reg_qty); 443 free (reg_offset); 444 free (reg_next_in_qty); 445 446 return recorded_label_ref; 447} 448 449/* Used for communication between the following two functions: contains 450 a MEM that we wish to ensure remains unchanged. */ 451static rtx equiv_mem; 452 453/* Set nonzero if EQUIV_MEM is modified. */ 454static int equiv_mem_modified; 455 456/* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified. 457 Called via note_stores. */ 458 459static void 460validate_equiv_mem_from_store (rtx dest, rtx set ATTRIBUTE_UNUSED, 461 void *data ATTRIBUTE_UNUSED) 462{ 463 if ((REG_P (dest) 464 && reg_overlap_mentioned_p (dest, equiv_mem)) 465 || (MEM_P (dest) 466 && true_dependence (dest, VOIDmode, equiv_mem, rtx_varies_p))) 467 equiv_mem_modified = 1; 468} 469 470/* Verify that no store between START and the death of REG invalidates 471 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF, 472 by storing into an overlapping memory location, or with a non-const 473 CALL_INSN. 474 475 Return 1 if MEMREF remains valid. */ 476 477static int 478validate_equiv_mem (rtx start, rtx reg, rtx memref) 479{ 480 rtx insn; 481 rtx note; 482 483 equiv_mem = memref; 484 equiv_mem_modified = 0; 485 486 /* If the memory reference has side effects or is volatile, it isn't a 487 valid equivalence. */ 488 if (side_effects_p (memref)) 489 return 0; 490 491 for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn)) 492 { 493 if (! INSN_P (insn)) 494 continue; 495 496 if (find_reg_note (insn, REG_DEAD, reg)) 497 return 1; 498 499 if (CALL_P (insn) && ! MEM_READONLY_P (memref) 500 && ! CONST_OR_PURE_CALL_P (insn)) 501 return 0; 502 503 note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL); 504 505 /* If a register mentioned in MEMREF is modified via an 506 auto-increment, we lose the equivalence. Do the same if one 507 dies; although we could extend the life, it doesn't seem worth 508 the trouble. */ 509 510 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 511 if ((REG_NOTE_KIND (note) == REG_INC 512 || REG_NOTE_KIND (note) == REG_DEAD) 513 && REG_P (XEXP (note, 0)) 514 && reg_overlap_mentioned_p (XEXP (note, 0), memref)) 515 return 0; 516 } 517 518 return 0; 519} 520 521/* Returns zero if X is known to be invariant. */ 522 523static int 524equiv_init_varies_p (rtx x) 525{ 526 RTX_CODE code = GET_CODE (x); 527 int i; 528 const char *fmt; 529 530 switch (code) 531 { 532 case MEM: 533 return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0)); 534 535 case CONST: 536 case CONST_INT: 537 case CONST_DOUBLE: 538 case CONST_VECTOR: 539 case SYMBOL_REF: 540 case LABEL_REF: 541 return 0; 542 543 case REG: 544 return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0); 545 546 case ASM_OPERANDS: 547 if (MEM_VOLATILE_P (x)) 548 return 1; 549 550 /* Fall through. */ 551 552 default: 553 break; 554 } 555 556 fmt = GET_RTX_FORMAT (code); 557 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 558 if (fmt[i] == 'e') 559 { 560 if (equiv_init_varies_p (XEXP (x, i))) 561 return 1; 562 } 563 else if (fmt[i] == 'E') 564 { 565 int j; 566 for (j = 0; j < XVECLEN (x, i); j++) 567 if (equiv_init_varies_p (XVECEXP (x, i, j))) 568 return 1; 569 } 570 571 return 0; 572} 573 574/* Returns nonzero if X (used to initialize register REGNO) is movable. 575 X is only movable if the registers it uses have equivalent initializations 576 which appear to be within the same loop (or in an inner loop) and movable 577 or if they are not candidates for local_alloc and don't vary. */ 578 579static int 580equiv_init_movable_p (rtx x, int regno) 581{ 582 int i, j; 583 const char *fmt; 584 enum rtx_code code = GET_CODE (x); 585 586 switch (code) 587 { 588 case SET: 589 return equiv_init_movable_p (SET_SRC (x), regno); 590 591 case CC0: 592 case CLOBBER: 593 return 0; 594 595 case PRE_INC: 596 case PRE_DEC: 597 case POST_INC: 598 case POST_DEC: 599 case PRE_MODIFY: 600 case POST_MODIFY: 601 return 0; 602 603 case REG: 604 return (reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth 605 && reg_equiv[REGNO (x)].replace) 606 || (REG_BASIC_BLOCK (REGNO (x)) < 0 && ! rtx_varies_p (x, 0)); 607 608 case UNSPEC_VOLATILE: 609 return 0; 610 611 case ASM_OPERANDS: 612 if (MEM_VOLATILE_P (x)) 613 return 0; 614 615 /* Fall through. */ 616 617 default: 618 break; 619 } 620 621 fmt = GET_RTX_FORMAT (code); 622 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 623 switch (fmt[i]) 624 { 625 case 'e': 626 if (! equiv_init_movable_p (XEXP (x, i), regno)) 627 return 0; 628 break; 629 case 'E': 630 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 631 if (! equiv_init_movable_p (XVECEXP (x, i, j), regno)) 632 return 0; 633 break; 634 } 635 636 return 1; 637} 638 639/* TRUE if X uses any registers for which reg_equiv[REGNO].replace is true. */ 640 641static int 642contains_replace_regs (rtx x) 643{ 644 int i, j; 645 const char *fmt; 646 enum rtx_code code = GET_CODE (x); 647 648 switch (code) 649 { 650 case CONST_INT: 651 case CONST: 652 case LABEL_REF: 653 case SYMBOL_REF: 654 case CONST_DOUBLE: 655 case CONST_VECTOR: 656 case PC: 657 case CC0: 658 case HIGH: 659 return 0; 660 661 case REG: 662 return reg_equiv[REGNO (x)].replace; 663 664 default: 665 break; 666 } 667 668 fmt = GET_RTX_FORMAT (code); 669 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 670 switch (fmt[i]) 671 { 672 case 'e': 673 if (contains_replace_regs (XEXP (x, i))) 674 return 1; 675 break; 676 case 'E': 677 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 678 if (contains_replace_regs (XVECEXP (x, i, j))) 679 return 1; 680 break; 681 } 682 683 return 0; 684} 685 686/* TRUE if X references a memory location that would be affected by a store 687 to MEMREF. */ 688 689static int 690memref_referenced_p (rtx memref, rtx x) 691{ 692 int i, j; 693 const char *fmt; 694 enum rtx_code code = GET_CODE (x); 695 696 switch (code) 697 { 698 case CONST_INT: 699 case CONST: 700 case LABEL_REF: 701 case SYMBOL_REF: 702 case CONST_DOUBLE: 703 case CONST_VECTOR: 704 case PC: 705 case CC0: 706 case HIGH: 707 case LO_SUM: 708 return 0; 709 710 case REG: 711 return (reg_equiv[REGNO (x)].replacement 712 && memref_referenced_p (memref, 713 reg_equiv[REGNO (x)].replacement)); 714 715 case MEM: 716 if (true_dependence (memref, VOIDmode, x, rtx_varies_p)) 717 return 1; 718 break; 719 720 case SET: 721 /* If we are setting a MEM, it doesn't count (its address does), but any 722 other SET_DEST that has a MEM in it is referencing the MEM. */ 723 if (MEM_P (SET_DEST (x))) 724 { 725 if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0))) 726 return 1; 727 } 728 else if (memref_referenced_p (memref, SET_DEST (x))) 729 return 1; 730 731 return memref_referenced_p (memref, SET_SRC (x)); 732 733 default: 734 break; 735 } 736 737 fmt = GET_RTX_FORMAT (code); 738 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 739 switch (fmt[i]) 740 { 741 case 'e': 742 if (memref_referenced_p (memref, XEXP (x, i))) 743 return 1; 744 break; 745 case 'E': 746 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 747 if (memref_referenced_p (memref, XVECEXP (x, i, j))) 748 return 1; 749 break; 750 } 751 752 return 0; 753} 754 755/* TRUE if some insn in the range (START, END] references a memory location 756 that would be affected by a store to MEMREF. */ 757 758static int 759memref_used_between_p (rtx memref, rtx start, rtx end) 760{ 761 rtx insn; 762 763 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end); 764 insn = NEXT_INSN (insn)) 765 { 766 if (!INSN_P (insn)) 767 continue; 768 769 if (memref_referenced_p (memref, PATTERN (insn))) 770 return 1; 771 772 /* Nonconst functions may access memory. */ 773 if (CALL_P (insn) 774 && (! CONST_OR_PURE_CALL_P (insn) 775 || pure_call_p (insn))) 776 return 1; 777 } 778 779 return 0; 780} 781 782/* Find registers that are equivalent to a single value throughout the 783 compilation (either because they can be referenced in memory or are set once 784 from a single constant). Lower their priority for a register. 785 786 If such a register is only referenced once, try substituting its value 787 into the using insn. If it succeeds, we can eliminate the register 788 completely. 789 790 Initialize the REG_EQUIV_INIT array of initializing insns. */ 791 792static void 793update_equiv_regs (void) 794{ 795 rtx insn; 796 basic_block bb; 797 int loop_depth; 798 regset_head cleared_regs; 799 int clear_regnos = 0; 800 801 reg_equiv = xcalloc (max_regno, sizeof *reg_equiv); 802 INIT_REG_SET (&cleared_regs); 803 reg_equiv_init = ggc_alloc_cleared (max_regno * sizeof (rtx)); 804 reg_equiv_init_size = max_regno; 805 806 init_alias_analysis (); 807 808 /* Scan the insns and find which registers have equivalences. Do this 809 in a separate scan of the insns because (due to -fcse-follow-jumps) 810 a register can be set below its use. */ 811 FOR_EACH_BB (bb) 812 { 813 loop_depth = bb->loop_depth; 814 815 for (insn = BB_HEAD (bb); 816 insn != NEXT_INSN (BB_END (bb)); 817 insn = NEXT_INSN (insn)) 818 { 819 rtx note; 820 rtx set; 821 rtx dest, src; 822 int regno; 823 824 if (! INSN_P (insn)) 825 continue; 826 827 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 828 if (REG_NOTE_KIND (note) == REG_INC) 829 no_equiv (XEXP (note, 0), note, NULL); 830 831 set = single_set (insn); 832 833 /* If this insn contains more (or less) than a single SET, 834 only mark all destinations as having no known equivalence. */ 835 if (set == 0) 836 { 837 note_stores (PATTERN (insn), no_equiv, NULL); 838 continue; 839 } 840 else if (GET_CODE (PATTERN (insn)) == PARALLEL) 841 { 842 int i; 843 844 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) 845 { 846 rtx part = XVECEXP (PATTERN (insn), 0, i); 847 if (part != set) 848 note_stores (part, no_equiv, NULL); 849 } 850 } 851 852 dest = SET_DEST (set); 853 src = SET_SRC (set); 854 855 /* See if this is setting up the equivalence between an argument 856 register and its stack slot. */ 857 note = find_reg_note (insn, REG_EQUIV, NULL_RTX); 858 if (note) 859 { 860 gcc_assert (REG_P (dest)); 861 regno = REGNO (dest); 862 863 /* Note that we don't want to clear reg_equiv_init even if there 864 are multiple sets of this register. */ 865 reg_equiv[regno].is_arg_equivalence = 1; 866 867 /* Record for reload that this is an equivalencing insn. */ 868 if (rtx_equal_p (src, XEXP (note, 0))) 869 reg_equiv_init[regno] 870 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]); 871 872 /* Continue normally in case this is a candidate for 873 replacements. */ 874 } 875 876 if (!optimize) 877 continue; 878 879 /* We only handle the case of a pseudo register being set 880 once, or always to the same value. */ 881 /* ??? The mn10200 port breaks if we add equivalences for 882 values that need an ADDRESS_REGS register and set them equivalent 883 to a MEM of a pseudo. The actual problem is in the over-conservative 884 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in 885 calculate_needs, but we traditionally work around this problem 886 here by rejecting equivalences when the destination is in a register 887 that's likely spilled. This is fragile, of course, since the 888 preferred class of a pseudo depends on all instructions that set 889 or use it. */ 890 891 if (!REG_P (dest) 892 || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER 893 || reg_equiv[regno].init_insns == const0_rtx 894 || (CLASS_LIKELY_SPILLED_P (reg_preferred_class (regno)) 895 && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence)) 896 { 897 /* This might be setting a SUBREG of a pseudo, a pseudo that is 898 also set somewhere else to a constant. */ 899 note_stores (set, no_equiv, NULL); 900 continue; 901 } 902 903 note = find_reg_note (insn, REG_EQUAL, NULL_RTX); 904 905 /* cse sometimes generates function invariants, but doesn't put a 906 REG_EQUAL note on the insn. Since this note would be redundant, 907 there's no point creating it earlier than here. */ 908 if (! note && ! rtx_varies_p (src, 0)) 909 note = set_unique_reg_note (insn, REG_EQUAL, src); 910 911 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST 912 since it represents a function call */ 913 if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST) 914 note = NULL_RTX; 915 916 if (REG_N_SETS (regno) != 1 917 && (! note 918 || rtx_varies_p (XEXP (note, 0), 0) 919 || (reg_equiv[regno].replacement 920 && ! rtx_equal_p (XEXP (note, 0), 921 reg_equiv[regno].replacement)))) 922 { 923 no_equiv (dest, set, NULL); 924 continue; 925 } 926 /* Record this insn as initializing this register. */ 927 reg_equiv[regno].init_insns 928 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns); 929 930 /* If this register is known to be equal to a constant, record that 931 it is always equivalent to the constant. */ 932 if (note && ! rtx_varies_p (XEXP (note, 0), 0)) 933 PUT_MODE (note, (enum machine_mode) REG_EQUIV); 934 935 /* If this insn introduces a "constant" register, decrease the priority 936 of that register. Record this insn if the register is only used once 937 more and the equivalence value is the same as our source. 938 939 The latter condition is checked for two reasons: First, it is an 940 indication that it may be more efficient to actually emit the insn 941 as written (if no registers are available, reload will substitute 942 the equivalence). Secondly, it avoids problems with any registers 943 dying in this insn whose death notes would be missed. 944 945 If we don't have a REG_EQUIV note, see if this insn is loading 946 a register used only in one basic block from a MEM. If so, and the 947 MEM remains unchanged for the life of the register, add a REG_EQUIV 948 note. */ 949 950 note = find_reg_note (insn, REG_EQUIV, NULL_RTX); 951 952 if (note == 0 && REG_BASIC_BLOCK (regno) >= 0 953 && MEM_P (SET_SRC (set)) 954 && validate_equiv_mem (insn, dest, SET_SRC (set))) 955 REG_NOTES (insn) = note = gen_rtx_EXPR_LIST (REG_EQUIV, SET_SRC (set), 956 REG_NOTES (insn)); 957 958 if (note) 959 { 960 int regno = REGNO (dest); 961 rtx x = XEXP (note, 0); 962 963 /* If we haven't done so, record for reload that this is an 964 equivalencing insn. */ 965 if (!reg_equiv[regno].is_arg_equivalence) 966 reg_equiv_init[regno] 967 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]); 968 969 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF. 970 We might end up substituting the LABEL_REF for uses of the 971 pseudo here or later. That kind of transformation may turn an 972 indirect jump into a direct jump, in which case we must rerun the 973 jump optimizer to ensure that the JUMP_LABEL fields are valid. */ 974 if (GET_CODE (x) == LABEL_REF 975 || (GET_CODE (x) == CONST 976 && GET_CODE (XEXP (x, 0)) == PLUS 977 && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF))) 978 recorded_label_ref = 1; 979 980 reg_equiv[regno].replacement = x; 981 reg_equiv[regno].src_p = &SET_SRC (set); 982 reg_equiv[regno].loop_depth = loop_depth; 983 984 /* Don't mess with things live during setjmp. */ 985 if (REG_LIVE_LENGTH (regno) >= 0 && optimize) 986 { 987 /* Note that the statement below does not affect the priority 988 in local-alloc! */ 989 REG_LIVE_LENGTH (regno) *= 2; 990 991 /* If the register is referenced exactly twice, meaning it is 992 set once and used once, indicate that the reference may be 993 replaced by the equivalence we computed above. Do this 994 even if the register is only used in one block so that 995 dependencies can be handled where the last register is 996 used in a different block (i.e. HIGH / LO_SUM sequences) 997 and to reduce the number of registers alive across 998 calls. */ 999 1000 if (REG_N_REFS (regno) == 2 1001 && (rtx_equal_p (x, src) 1002 || ! equiv_init_varies_p (src)) 1003 && NONJUMP_INSN_P (insn) 1004 && equiv_init_movable_p (PATTERN (insn), regno)) 1005 reg_equiv[regno].replace = 1; 1006 } 1007 } 1008 } 1009 } 1010 1011 if (!optimize) 1012 goto out; 1013 1014 /* A second pass, to gather additional equivalences with memory. This needs 1015 to be done after we know which registers we are going to replace. */ 1016 1017 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 1018 { 1019 rtx set, src, dest; 1020 unsigned regno; 1021 1022 if (! INSN_P (insn)) 1023 continue; 1024 1025 set = single_set (insn); 1026 if (! set) 1027 continue; 1028 1029 dest = SET_DEST (set); 1030 src = SET_SRC (set); 1031 1032 /* If this sets a MEM to the contents of a REG that is only used 1033 in a single basic block, see if the register is always equivalent 1034 to that memory location and if moving the store from INSN to the 1035 insn that set REG is safe. If so, put a REG_EQUIV note on the 1036 initializing insn. 1037 1038 Don't add a REG_EQUIV note if the insn already has one. The existing 1039 REG_EQUIV is likely more useful than the one we are adding. 1040 1041 If one of the regs in the address has reg_equiv[REGNO].replace set, 1042 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace 1043 optimization may move the set of this register immediately before 1044 insn, which puts it after reg_equiv[REGNO].init_insns, and hence 1045 the mention in the REG_EQUIV note would be to an uninitialized 1046 pseudo. */ 1047 1048 if (MEM_P (dest) && REG_P (src) 1049 && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER 1050 && REG_BASIC_BLOCK (regno) >= 0 1051 && REG_N_SETS (regno) == 1 1052 && reg_equiv[regno].init_insns != 0 1053 && reg_equiv[regno].init_insns != const0_rtx 1054 && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0), 1055 REG_EQUIV, NULL_RTX) 1056 && ! contains_replace_regs (XEXP (dest, 0))) 1057 { 1058 rtx init_insn = XEXP (reg_equiv[regno].init_insns, 0); 1059 if (validate_equiv_mem (init_insn, src, dest) 1060 && ! memref_used_between_p (dest, init_insn, insn)) 1061 { 1062 REG_NOTES (init_insn) 1063 = gen_rtx_EXPR_LIST (REG_EQUIV, dest, 1064 REG_NOTES (init_insn)); 1065 /* This insn makes the equivalence, not the one initializing 1066 the register. */ 1067 reg_equiv_init[regno] 1068 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX); 1069 } 1070 } 1071 } 1072 1073 /* Now scan all regs killed in an insn to see if any of them are 1074 registers only used that once. If so, see if we can replace the 1075 reference with the equivalent form. If we can, delete the 1076 initializing reference and this register will go away. If we 1077 can't replace the reference, and the initializing reference is 1078 within the same loop (or in an inner loop), then move the register 1079 initialization just before the use, so that they are in the same 1080 basic block. */ 1081 FOR_EACH_BB_REVERSE (bb) 1082 { 1083 loop_depth = bb->loop_depth; 1084 for (insn = BB_END (bb); 1085 insn != PREV_INSN (BB_HEAD (bb)); 1086 insn = PREV_INSN (insn)) 1087 { 1088 rtx link; 1089 1090 if (! INSN_P (insn)) 1091 continue; 1092 1093 /* Don't substitute into a non-local goto, this confuses CFG. */ 1094 if (JUMP_P (insn) 1095 && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX)) 1096 continue; 1097 1098 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 1099 { 1100 if (REG_NOTE_KIND (link) == REG_DEAD 1101 /* Make sure this insn still refers to the register. */ 1102 && reg_mentioned_p (XEXP (link, 0), PATTERN (insn))) 1103 { 1104 int regno = REGNO (XEXP (link, 0)); 1105 rtx equiv_insn; 1106 1107 if (! reg_equiv[regno].replace 1108 || reg_equiv[regno].loop_depth < loop_depth) 1109 continue; 1110 1111 /* reg_equiv[REGNO].replace gets set only when 1112 REG_N_REFS[REGNO] is 2, i.e. the register is set 1113 once and used once. (If it were only set, but not used, 1114 flow would have deleted the setting insns.) Hence 1115 there can only be one insn in reg_equiv[REGNO].init_insns. */ 1116 gcc_assert (reg_equiv[regno].init_insns 1117 && !XEXP (reg_equiv[regno].init_insns, 1)); 1118 equiv_insn = XEXP (reg_equiv[regno].init_insns, 0); 1119 1120 /* We may not move instructions that can throw, since 1121 that changes basic block boundaries and we are not 1122 prepared to adjust the CFG to match. */ 1123 if (can_throw_internal (equiv_insn)) 1124 continue; 1125 1126 if (asm_noperands (PATTERN (equiv_insn)) < 0 1127 && validate_replace_rtx (regno_reg_rtx[regno], 1128 *(reg_equiv[regno].src_p), insn)) 1129 { 1130 rtx equiv_link; 1131 rtx last_link; 1132 rtx note; 1133 1134 /* Find the last note. */ 1135 for (last_link = link; XEXP (last_link, 1); 1136 last_link = XEXP (last_link, 1)) 1137 ; 1138 1139 /* Append the REG_DEAD notes from equiv_insn. */ 1140 equiv_link = REG_NOTES (equiv_insn); 1141 while (equiv_link) 1142 { 1143 note = equiv_link; 1144 equiv_link = XEXP (equiv_link, 1); 1145 if (REG_NOTE_KIND (note) == REG_DEAD) 1146 { 1147 remove_note (equiv_insn, note); 1148 XEXP (last_link, 1) = note; 1149 XEXP (note, 1) = NULL_RTX; 1150 last_link = note; 1151 } 1152 } 1153 1154 remove_death (regno, insn); 1155 REG_N_REFS (regno) = 0; 1156 REG_FREQ (regno) = 0; 1157 delete_insn (equiv_insn); 1158 1159 reg_equiv[regno].init_insns 1160 = XEXP (reg_equiv[regno].init_insns, 1); 1161 1162 /* Remember to clear REGNO from all basic block's live 1163 info. */ 1164 SET_REGNO_REG_SET (&cleared_regs, regno); 1165 clear_regnos++; 1166 reg_equiv_init[regno] = NULL_RTX; 1167 } 1168 /* Move the initialization of the register to just before 1169 INSN. Update the flow information. */ 1170 else if (PREV_INSN (insn) != equiv_insn) 1171 { 1172 rtx new_insn; 1173 1174 new_insn = emit_insn_before (PATTERN (equiv_insn), insn); 1175 REG_NOTES (new_insn) = REG_NOTES (equiv_insn); 1176 REG_NOTES (equiv_insn) = 0; 1177 1178 /* Make sure this insn is recognized before 1179 reload begins, otherwise 1180 eliminate_regs_in_insn will die. */ 1181 INSN_CODE (new_insn) = INSN_CODE (equiv_insn); 1182 1183 delete_insn (equiv_insn); 1184 1185 XEXP (reg_equiv[regno].init_insns, 0) = new_insn; 1186 1187 REG_BASIC_BLOCK (regno) = bb->index; 1188 REG_N_CALLS_CROSSED (regno) = 0; 1189 REG_N_THROWING_CALLS_CROSSED (regno) = 0; 1190 REG_LIVE_LENGTH (regno) = 2; 1191 1192 if (insn == BB_HEAD (bb)) 1193 BB_HEAD (bb) = PREV_INSN (insn); 1194 1195 /* Remember to clear REGNO from all basic block's live 1196 info. */ 1197 SET_REGNO_REG_SET (&cleared_regs, regno); 1198 clear_regnos++; 1199 reg_equiv_init[regno] 1200 = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX); 1201 } 1202 } 1203 } 1204 } 1205 } 1206 1207 /* Clear all dead REGNOs from all basic block's live info. */ 1208 if (clear_regnos) 1209 { 1210 unsigned j; 1211 1212 if (clear_regnos > 8) 1213 { 1214 FOR_EACH_BB (bb) 1215 { 1216 AND_COMPL_REG_SET (bb->il.rtl->global_live_at_start, 1217 &cleared_regs); 1218 AND_COMPL_REG_SET (bb->il.rtl->global_live_at_end, 1219 &cleared_regs); 1220 } 1221 } 1222 else 1223 { 1224 reg_set_iterator rsi; 1225 EXECUTE_IF_SET_IN_REG_SET (&cleared_regs, 0, j, rsi) 1226 { 1227 FOR_EACH_BB (bb) 1228 { 1229 CLEAR_REGNO_REG_SET (bb->il.rtl->global_live_at_start, j); 1230 CLEAR_REGNO_REG_SET (bb->il.rtl->global_live_at_end, j); 1231 } 1232 } 1233 } 1234 } 1235 1236 out: 1237 /* Clean up. */ 1238 end_alias_analysis (); 1239 CLEAR_REG_SET (&cleared_regs); 1240 free (reg_equiv); 1241} 1242 1243/* Mark REG as having no known equivalence. 1244 Some instructions might have been processed before and furnished 1245 with REG_EQUIV notes for this register; these notes will have to be 1246 removed. 1247 STORE is the piece of RTL that does the non-constant / conflicting 1248 assignment - a SET, CLOBBER or REG_INC note. It is currently not used, 1249 but needs to be there because this function is called from note_stores. */ 1250static void 1251no_equiv (rtx reg, rtx store ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) 1252{ 1253 int regno; 1254 rtx list; 1255 1256 if (!REG_P (reg)) 1257 return; 1258 regno = REGNO (reg); 1259 list = reg_equiv[regno].init_insns; 1260 if (list == const0_rtx) 1261 return; 1262 reg_equiv[regno].init_insns = const0_rtx; 1263 reg_equiv[regno].replacement = NULL_RTX; 1264 /* This doesn't matter for equivalences made for argument registers, we 1265 should keep their initialization insns. */ 1266 if (reg_equiv[regno].is_arg_equivalence) 1267 return; 1268 reg_equiv_init[regno] = NULL_RTX; 1269 for (; list; list = XEXP (list, 1)) 1270 { 1271 rtx insn = XEXP (list, 0); 1272 remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX)); 1273 } 1274} 1275 1276/* Allocate hard regs to the pseudo regs used only within block number B. 1277 Only the pseudos that die but once can be handled. */ 1278 1279static void 1280block_alloc (int b) 1281{ 1282 int i, q; 1283 rtx insn; 1284 rtx note, hard_reg; 1285 int insn_number = 0; 1286 int insn_count = 0; 1287 int max_uid = get_max_uid (); 1288 int *qty_order; 1289 int no_conflict_combined_regno = -1; 1290 1291 /* Count the instructions in the basic block. */ 1292 1293 insn = BB_END (BASIC_BLOCK (b)); 1294 while (1) 1295 { 1296 if (!NOTE_P (insn)) 1297 { 1298 ++insn_count; 1299 gcc_assert (insn_count <= max_uid); 1300 } 1301 if (insn == BB_HEAD (BASIC_BLOCK (b))) 1302 break; 1303 insn = PREV_INSN (insn); 1304 } 1305 1306 /* +2 to leave room for a post_mark_life at the last insn and for 1307 the birth of a CLOBBER in the first insn. */ 1308 regs_live_at = xcalloc ((2 * insn_count + 2), sizeof (HARD_REG_SET)); 1309 1310 /* Initialize table of hardware registers currently live. */ 1311 1312 REG_SET_TO_HARD_REG_SET (regs_live, 1313 BASIC_BLOCK (b)->il.rtl->global_live_at_start); 1314 1315 /* This loop scans the instructions of the basic block 1316 and assigns quantities to registers. 1317 It computes which registers to tie. */ 1318 1319 insn = BB_HEAD (BASIC_BLOCK (b)); 1320 while (1) 1321 { 1322 if (!NOTE_P (insn)) 1323 insn_number++; 1324 1325 if (INSN_P (insn)) 1326 { 1327 rtx link, set; 1328 int win = 0; 1329 rtx r0, r1 = NULL_RTX; 1330 int combined_regno = -1; 1331 int i; 1332 1333 this_insn_number = insn_number; 1334 this_insn = insn; 1335 1336 extract_insn (insn); 1337 which_alternative = -1; 1338 1339 /* Is this insn suitable for tying two registers? 1340 If so, try doing that. 1341 Suitable insns are those with at least two operands and where 1342 operand 0 is an output that is a register that is not 1343 earlyclobber. 1344 1345 We can tie operand 0 with some operand that dies in this insn. 1346 First look for operands that are required to be in the same 1347 register as operand 0. If we find such, only try tying that 1348 operand or one that can be put into that operand if the 1349 operation is commutative. If we don't find an operand 1350 that is required to be in the same register as operand 0, 1351 we can tie with any operand. 1352 1353 Subregs in place of regs are also ok. 1354 1355 If tying is done, WIN is set nonzero. */ 1356 1357 if (optimize 1358 && recog_data.n_operands > 1 1359 && recog_data.constraints[0][0] == '=' 1360 && recog_data.constraints[0][1] != '&') 1361 { 1362 /* If non-negative, is an operand that must match operand 0. */ 1363 int must_match_0 = -1; 1364 /* Counts number of alternatives that require a match with 1365 operand 0. */ 1366 int n_matching_alts = 0; 1367 1368 for (i = 1; i < recog_data.n_operands; i++) 1369 { 1370 const char *p = recog_data.constraints[i]; 1371 int this_match = requires_inout (p); 1372 1373 n_matching_alts += this_match; 1374 if (this_match == recog_data.n_alternatives) 1375 must_match_0 = i; 1376 } 1377 1378 r0 = recog_data.operand[0]; 1379 for (i = 1; i < recog_data.n_operands; i++) 1380 { 1381 /* Skip this operand if we found an operand that 1382 must match operand 0 and this operand isn't it 1383 and can't be made to be it by commutativity. */ 1384 1385 if (must_match_0 >= 0 && i != must_match_0 1386 && ! (i == must_match_0 + 1 1387 && recog_data.constraints[i-1][0] == '%') 1388 && ! (i == must_match_0 - 1 1389 && recog_data.constraints[i][0] == '%')) 1390 continue; 1391 1392 /* Likewise if each alternative has some operand that 1393 must match operand zero. In that case, skip any 1394 operand that doesn't list operand 0 since we know that 1395 the operand always conflicts with operand 0. We 1396 ignore commutativity in this case to keep things simple. */ 1397 if (n_matching_alts == recog_data.n_alternatives 1398 && 0 == requires_inout (recog_data.constraints[i])) 1399 continue; 1400 1401 r1 = recog_data.operand[i]; 1402 1403 /* If the operand is an address, find a register in it. 1404 There may be more than one register, but we only try one 1405 of them. */ 1406 if (recog_data.constraints[i][0] == 'p' 1407 || EXTRA_ADDRESS_CONSTRAINT (recog_data.constraints[i][0], 1408 recog_data.constraints[i])) 1409 while (GET_CODE (r1) == PLUS || GET_CODE (r1) == MULT) 1410 r1 = XEXP (r1, 0); 1411 1412 /* Avoid making a call-saved register unnecessarily 1413 clobbered. */ 1414 hard_reg = get_hard_reg_initial_reg (cfun, r1); 1415 if (hard_reg != NULL_RTX) 1416 { 1417 if (REG_P (hard_reg) 1418 && REGNO (hard_reg) < FIRST_PSEUDO_REGISTER 1419 && !call_used_regs[REGNO (hard_reg)]) 1420 continue; 1421 } 1422 1423 if (REG_P (r0) || GET_CODE (r0) == SUBREG) 1424 { 1425 /* We have two priorities for hard register preferences. 1426 If we have a move insn or an insn whose first input 1427 can only be in the same register as the output, give 1428 priority to an equivalence found from that insn. */ 1429 int may_save_copy 1430 = (r1 == recog_data.operand[i] && must_match_0 >= 0); 1431 1432 if (REG_P (r1) || GET_CODE (r1) == SUBREG) 1433 win = combine_regs (r1, r0, may_save_copy, 1434 insn_number, insn, 0); 1435 } 1436 if (win) 1437 break; 1438 } 1439 } 1440 1441 /* Recognize an insn sequence with an ultimate result 1442 which can safely overlap one of the inputs. 1443 The sequence begins with a CLOBBER of its result, 1444 and ends with an insn that copies the result to itself 1445 and has a REG_EQUAL note for an equivalent formula. 1446 That note indicates what the inputs are. 1447 The result and the input can overlap if each insn in 1448 the sequence either doesn't mention the input 1449 or has a REG_NO_CONFLICT note to inhibit the conflict. 1450 1451 We do the combining test at the CLOBBER so that the 1452 destination register won't have had a quantity number 1453 assigned, since that would prevent combining. */ 1454 1455 if (optimize 1456 && GET_CODE (PATTERN (insn)) == CLOBBER 1457 && (r0 = XEXP (PATTERN (insn), 0), 1458 REG_P (r0)) 1459 && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0 1460 && XEXP (link, 0) != 0 1461 && NONJUMP_INSN_P (XEXP (link, 0)) 1462 && (set = single_set (XEXP (link, 0))) != 0 1463 && SET_DEST (set) == r0 && SET_SRC (set) == r0 1464 && (note = find_reg_note (XEXP (link, 0), REG_EQUAL, 1465 NULL_RTX)) != 0) 1466 { 1467 if (r1 = XEXP (note, 0), REG_P (r1) 1468 /* Check that we have such a sequence. */ 1469 && no_conflict_p (insn, r0, r1)) 1470 win = combine_regs (r1, r0, 1, insn_number, insn, 1); 1471 else if (GET_RTX_FORMAT (GET_CODE (XEXP (note, 0)))[0] == 'e' 1472 && (r1 = XEXP (XEXP (note, 0), 0), 1473 REG_P (r1) || GET_CODE (r1) == SUBREG) 1474 && no_conflict_p (insn, r0, r1)) 1475 win = combine_regs (r1, r0, 0, insn_number, insn, 1); 1476 1477 /* Here we care if the operation to be computed is 1478 commutative. */ 1479 else if (COMMUTATIVE_P (XEXP (note, 0)) 1480 && (r1 = XEXP (XEXP (note, 0), 1), 1481 (REG_P (r1) || GET_CODE (r1) == SUBREG)) 1482 && no_conflict_p (insn, r0, r1)) 1483 win = combine_regs (r1, r0, 0, insn_number, insn, 1); 1484 1485 /* If we did combine something, show the register number 1486 in question so that we know to ignore its death. */ 1487 if (win) 1488 no_conflict_combined_regno = REGNO (r1); 1489 } 1490 1491 /* If registers were just tied, set COMBINED_REGNO 1492 to the number of the register used in this insn 1493 that was tied to the register set in this insn. 1494 This register's qty should not be "killed". */ 1495 1496 if (win) 1497 { 1498 while (GET_CODE (r1) == SUBREG) 1499 r1 = SUBREG_REG (r1); 1500 combined_regno = REGNO (r1); 1501 } 1502 1503 /* Mark the death of everything that dies in this instruction, 1504 except for anything that was just combined. */ 1505 1506 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 1507 if (REG_NOTE_KIND (link) == REG_DEAD 1508 && REG_P (XEXP (link, 0)) 1509 && combined_regno != (int) REGNO (XEXP (link, 0)) 1510 && (no_conflict_combined_regno != (int) REGNO (XEXP (link, 0)) 1511 || ! find_reg_note (insn, REG_NO_CONFLICT, 1512 XEXP (link, 0)))) 1513 wipe_dead_reg (XEXP (link, 0), 0); 1514 1515 /* Allocate qty numbers for all registers local to this block 1516 that are born (set) in this instruction. 1517 A pseudo that already has a qty is not changed. */ 1518 1519 note_stores (PATTERN (insn), reg_is_set, NULL); 1520 1521 /* If anything is set in this insn and then unused, mark it as dying 1522 after this insn, so it will conflict with our outputs. This 1523 can't match with something that combined, and it doesn't matter 1524 if it did. Do this after the calls to reg_is_set since these 1525 die after, not during, the current insn. */ 1526 1527 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 1528 if (REG_NOTE_KIND (link) == REG_UNUSED 1529 && REG_P (XEXP (link, 0))) 1530 wipe_dead_reg (XEXP (link, 0), 1); 1531 1532 /* If this is an insn that has a REG_RETVAL note pointing at a 1533 CLOBBER insn, we have reached the end of a REG_NO_CONFLICT 1534 block, so clear any register number that combined within it. */ 1535 if ((note = find_reg_note (insn, REG_RETVAL, NULL_RTX)) != 0 1536 && NONJUMP_INSN_P (XEXP (note, 0)) 1537 && GET_CODE (PATTERN (XEXP (note, 0))) == CLOBBER) 1538 no_conflict_combined_regno = -1; 1539 } 1540 1541 /* Set the registers live after INSN_NUMBER. Note that we never 1542 record the registers live before the block's first insn, since no 1543 pseudos we care about are live before that insn. */ 1544 1545 IOR_HARD_REG_SET (regs_live_at[2 * insn_number], regs_live); 1546 IOR_HARD_REG_SET (regs_live_at[2 * insn_number + 1], regs_live); 1547 1548 if (insn == BB_END (BASIC_BLOCK (b))) 1549 break; 1550 1551 insn = NEXT_INSN (insn); 1552 } 1553 1554 /* Now every register that is local to this basic block 1555 should have been given a quantity, or else -1 meaning ignore it. 1556 Every quantity should have a known birth and death. 1557 1558 Order the qtys so we assign them registers in order of the 1559 number of suggested registers they need so we allocate those with 1560 the most restrictive needs first. */ 1561 1562 qty_order = xmalloc (next_qty * sizeof (int)); 1563 for (i = 0; i < next_qty; i++) 1564 qty_order[i] = i; 1565 1566#define EXCHANGE(I1, I2) \ 1567 { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; } 1568 1569 switch (next_qty) 1570 { 1571 case 3: 1572 /* Make qty_order[2] be the one to allocate last. */ 1573 if (qty_sugg_compare (0, 1) > 0) 1574 EXCHANGE (0, 1); 1575 if (qty_sugg_compare (1, 2) > 0) 1576 EXCHANGE (2, 1); 1577 1578 /* ... Fall through ... */ 1579 case 2: 1580 /* Put the best one to allocate in qty_order[0]. */ 1581 if (qty_sugg_compare (0, 1) > 0) 1582 EXCHANGE (0, 1); 1583 1584 /* ... Fall through ... */ 1585 1586 case 1: 1587 case 0: 1588 /* Nothing to do here. */ 1589 break; 1590 1591 default: 1592 qsort (qty_order, next_qty, sizeof (int), qty_sugg_compare_1); 1593 } 1594 1595 /* Try to put each quantity in a suggested physical register, if it has one. 1596 This may cause registers to be allocated that otherwise wouldn't be, but 1597 this seems acceptable in local allocation (unlike global allocation). */ 1598 for (i = 0; i < next_qty; i++) 1599 { 1600 q = qty_order[i]; 1601 if (qty_phys_num_sugg[q] != 0 || qty_phys_num_copy_sugg[q] != 0) 1602 qty[q].phys_reg = find_free_reg (qty[q].min_class, qty[q].mode, q, 1603 0, 1, qty[q].birth, qty[q].death); 1604 else 1605 qty[q].phys_reg = -1; 1606 } 1607 1608 /* Order the qtys so we assign them registers in order of 1609 decreasing length of life. Normally call qsort, but if we 1610 have only a very small number of quantities, sort them ourselves. */ 1611 1612 for (i = 0; i < next_qty; i++) 1613 qty_order[i] = i; 1614 1615#define EXCHANGE(I1, I2) \ 1616 { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; } 1617 1618 switch (next_qty) 1619 { 1620 case 3: 1621 /* Make qty_order[2] be the one to allocate last. */ 1622 if (qty_compare (0, 1) > 0) 1623 EXCHANGE (0, 1); 1624 if (qty_compare (1, 2) > 0) 1625 EXCHANGE (2, 1); 1626 1627 /* ... Fall through ... */ 1628 case 2: 1629 /* Put the best one to allocate in qty_order[0]. */ 1630 if (qty_compare (0, 1) > 0) 1631 EXCHANGE (0, 1); 1632 1633 /* ... Fall through ... */ 1634 1635 case 1: 1636 case 0: 1637 /* Nothing to do here. */ 1638 break; 1639 1640 default: 1641 qsort (qty_order, next_qty, sizeof (int), qty_compare_1); 1642 } 1643 1644 /* Now for each qty that is not a hardware register, 1645 look for a hardware register to put it in. 1646 First try the register class that is cheapest for this qty, 1647 if there is more than one class. */ 1648 1649 for (i = 0; i < next_qty; i++) 1650 { 1651 q = qty_order[i]; 1652 if (qty[q].phys_reg < 0) 1653 { 1654#ifdef INSN_SCHEDULING 1655 /* These values represent the adjusted lifetime of a qty so 1656 that it conflicts with qtys which appear near the start/end 1657 of this qty's lifetime. 1658 1659 The purpose behind extending the lifetime of this qty is to 1660 discourage the register allocator from creating false 1661 dependencies. 1662 1663 The adjustment value is chosen to indicate that this qty 1664 conflicts with all the qtys in the instructions immediately 1665 before and after the lifetime of this qty. 1666 1667 Experiments have shown that higher values tend to hurt 1668 overall code performance. 1669 1670 If allocation using the extended lifetime fails we will try 1671 again with the qty's unadjusted lifetime. */ 1672 int fake_birth = MAX (0, qty[q].birth - 2 + qty[q].birth % 2); 1673 int fake_death = MIN (insn_number * 2 + 1, 1674 qty[q].death + 2 - qty[q].death % 2); 1675#endif 1676 1677 if (N_REG_CLASSES > 1) 1678 { 1679#ifdef INSN_SCHEDULING 1680 /* We try to avoid using hard registers allocated to qtys which 1681 are born immediately after this qty or die immediately before 1682 this qty. 1683 1684 This optimization is only appropriate when we will run 1685 a scheduling pass after reload and we are not optimizing 1686 for code size. */ 1687 if (flag_schedule_insns_after_reload 1688 && !optimize_size 1689 && !SMALL_REGISTER_CLASSES) 1690 { 1691 qty[q].phys_reg = find_free_reg (qty[q].min_class, 1692 qty[q].mode, q, 0, 0, 1693 fake_birth, fake_death); 1694 if (qty[q].phys_reg >= 0) 1695 continue; 1696 } 1697#endif 1698 qty[q].phys_reg = find_free_reg (qty[q].min_class, 1699 qty[q].mode, q, 0, 0, 1700 qty[q].birth, qty[q].death); 1701 if (qty[q].phys_reg >= 0) 1702 continue; 1703 } 1704 1705#ifdef INSN_SCHEDULING 1706 /* Similarly, avoid false dependencies. */ 1707 if (flag_schedule_insns_after_reload 1708 && !optimize_size 1709 && !SMALL_REGISTER_CLASSES 1710 && qty[q].alternate_class != NO_REGS) 1711 qty[q].phys_reg = find_free_reg (qty[q].alternate_class, 1712 qty[q].mode, q, 0, 0, 1713 fake_birth, fake_death); 1714#endif 1715 if (qty[q].alternate_class != NO_REGS) 1716 qty[q].phys_reg = find_free_reg (qty[q].alternate_class, 1717 qty[q].mode, q, 0, 0, 1718 qty[q].birth, qty[q].death); 1719 } 1720 } 1721 1722 /* Now propagate the register assignments 1723 to the pseudo regs belonging to the qtys. */ 1724 1725 for (q = 0; q < next_qty; q++) 1726 if (qty[q].phys_reg >= 0) 1727 { 1728 for (i = qty[q].first_reg; i >= 0; i = reg_next_in_qty[i]) 1729 reg_renumber[i] = qty[q].phys_reg + reg_offset[i]; 1730 } 1731 1732 /* Clean up. */ 1733 free (regs_live_at); 1734 free (qty_order); 1735} 1736 1737/* Compare two quantities' priority for getting real registers. 1738 We give shorter-lived quantities higher priority. 1739 Quantities with more references are also preferred, as are quantities that 1740 require multiple registers. This is the identical prioritization as 1741 done by global-alloc. 1742 1743 We used to give preference to registers with *longer* lives, but using 1744 the same algorithm in both local- and global-alloc can speed up execution 1745 of some programs by as much as a factor of three! */ 1746 1747/* Note that the quotient will never be bigger than 1748 the value of floor_log2 times the maximum number of 1749 times a register can occur in one insn (surely less than 100) 1750 weighted by frequency (max REG_FREQ_MAX). 1751 Multiplying this by 10000/REG_FREQ_MAX can't overflow. 1752 QTY_CMP_PRI is also used by qty_sugg_compare. */ 1753 1754#define QTY_CMP_PRI(q) \ 1755 ((int) (((double) (floor_log2 (qty[q].n_refs) * qty[q].freq * qty[q].size) \ 1756 / (qty[q].death - qty[q].birth)) * (10000 / REG_FREQ_MAX))) 1757 1758static int 1759qty_compare (int q1, int q2) 1760{ 1761 return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1); 1762} 1763 1764static int 1765qty_compare_1 (const void *q1p, const void *q2p) 1766{ 1767 int q1 = *(const int *) q1p, q2 = *(const int *) q2p; 1768 int tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1); 1769 1770 if (tem != 0) 1771 return tem; 1772 1773 /* If qtys are equally good, sort by qty number, 1774 so that the results of qsort leave nothing to chance. */ 1775 return q1 - q2; 1776} 1777 1778/* Compare two quantities' priority for getting real registers. This version 1779 is called for quantities that have suggested hard registers. First priority 1780 goes to quantities that have copy preferences, then to those that have 1781 normal preferences. Within those groups, quantities with the lower 1782 number of preferences have the highest priority. Of those, we use the same 1783 algorithm as above. */ 1784 1785#define QTY_CMP_SUGG(q) \ 1786 (qty_phys_num_copy_sugg[q] \ 1787 ? qty_phys_num_copy_sugg[q] \ 1788 : qty_phys_num_sugg[q] * FIRST_PSEUDO_REGISTER) 1789 1790static int 1791qty_sugg_compare (int q1, int q2) 1792{ 1793 int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2); 1794 1795 if (tem != 0) 1796 return tem; 1797 1798 return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1); 1799} 1800 1801static int 1802qty_sugg_compare_1 (const void *q1p, const void *q2p) 1803{ 1804 int q1 = *(const int *) q1p, q2 = *(const int *) q2p; 1805 int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2); 1806 1807 if (tem != 0) 1808 return tem; 1809 1810 tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1); 1811 if (tem != 0) 1812 return tem; 1813 1814 /* If qtys are equally good, sort by qty number, 1815 so that the results of qsort leave nothing to chance. */ 1816 return q1 - q2; 1817} 1818 1819#undef QTY_CMP_SUGG 1820#undef QTY_CMP_PRI 1821 1822/* Attempt to combine the two registers (rtx's) USEDREG and SETREG. 1823 Returns 1 if have done so, or 0 if cannot. 1824 1825 Combining registers means marking them as having the same quantity 1826 and adjusting the offsets within the quantity if either of 1827 them is a SUBREG. 1828 1829 We don't actually combine a hard reg with a pseudo; instead 1830 we just record the hard reg as the suggestion for the pseudo's quantity. 1831 If we really combined them, we could lose if the pseudo lives 1832 across an insn that clobbers the hard reg (eg, movmem). 1833 1834 ALREADY_DEAD is nonzero if USEDREG is known to be dead even though 1835 there is no REG_DEAD note on INSN. This occurs during the processing 1836 of REG_NO_CONFLICT blocks. 1837 1838 MAY_SAVE_COPY is nonzero if this insn is simply copying USEDREG to 1839 SETREG or if the input and output must share a register. 1840 In that case, we record a hard reg suggestion in QTY_PHYS_COPY_SUGG. 1841 1842 There are elaborate checks for the validity of combining. */ 1843 1844static int 1845combine_regs (rtx usedreg, rtx setreg, int may_save_copy, int insn_number, 1846 rtx insn, int already_dead) 1847{ 1848 int ureg, sreg; 1849 int offset = 0; 1850 int usize, ssize; 1851 int sqty; 1852 1853 /* Determine the numbers and sizes of registers being used. If a subreg 1854 is present that does not change the entire register, don't consider 1855 this a copy insn. */ 1856 1857 while (GET_CODE (usedreg) == SUBREG) 1858 { 1859 rtx subreg = SUBREG_REG (usedreg); 1860 1861 if (REG_P (subreg)) 1862 { 1863 if (GET_MODE_SIZE (GET_MODE (subreg)) > UNITS_PER_WORD) 1864 may_save_copy = 0; 1865 1866 if (REGNO (subreg) < FIRST_PSEUDO_REGISTER) 1867 offset += subreg_regno_offset (REGNO (subreg), 1868 GET_MODE (subreg), 1869 SUBREG_BYTE (usedreg), 1870 GET_MODE (usedreg)); 1871 else 1872 offset += (SUBREG_BYTE (usedreg) 1873 / REGMODE_NATURAL_SIZE (GET_MODE (usedreg))); 1874 } 1875 1876 usedreg = subreg; 1877 } 1878 1879 if (!REG_P (usedreg)) 1880 return 0; 1881 1882 ureg = REGNO (usedreg); 1883 if (ureg < FIRST_PSEUDO_REGISTER) 1884 usize = hard_regno_nregs[ureg][GET_MODE (usedreg)]; 1885 else 1886 usize = ((GET_MODE_SIZE (GET_MODE (usedreg)) 1887 + (REGMODE_NATURAL_SIZE (GET_MODE (usedreg)) - 1)) 1888 / REGMODE_NATURAL_SIZE (GET_MODE (usedreg))); 1889 1890 while (GET_CODE (setreg) == SUBREG) 1891 { 1892 rtx subreg = SUBREG_REG (setreg); 1893 1894 if (REG_P (subreg)) 1895 { 1896 if (GET_MODE_SIZE (GET_MODE (subreg)) > UNITS_PER_WORD) 1897 may_save_copy = 0; 1898 1899 if (REGNO (subreg) < FIRST_PSEUDO_REGISTER) 1900 offset -= subreg_regno_offset (REGNO (subreg), 1901 GET_MODE (subreg), 1902 SUBREG_BYTE (setreg), 1903 GET_MODE (setreg)); 1904 else 1905 offset -= (SUBREG_BYTE (setreg) 1906 / REGMODE_NATURAL_SIZE (GET_MODE (setreg))); 1907 } 1908 1909 setreg = subreg; 1910 } 1911 1912 if (!REG_P (setreg)) 1913 return 0; 1914 1915 sreg = REGNO (setreg); 1916 if (sreg < FIRST_PSEUDO_REGISTER) 1917 ssize = hard_regno_nregs[sreg][GET_MODE (setreg)]; 1918 else 1919 ssize = ((GET_MODE_SIZE (GET_MODE (setreg)) 1920 + (REGMODE_NATURAL_SIZE (GET_MODE (setreg)) - 1)) 1921 / REGMODE_NATURAL_SIZE (GET_MODE (setreg))); 1922 1923 /* If UREG is a pseudo-register that hasn't already been assigned a 1924 quantity number, it means that it is not local to this block or dies 1925 more than once. In either event, we can't do anything with it. */ 1926 if ((ureg >= FIRST_PSEUDO_REGISTER && reg_qty[ureg] < 0) 1927 /* Do not combine registers unless one fits within the other. */ 1928 || (offset > 0 && usize + offset > ssize) 1929 || (offset < 0 && usize + offset < ssize) 1930 /* Do not combine with a smaller already-assigned object 1931 if that smaller object is already combined with something bigger. */ 1932 || (ssize > usize && ureg >= FIRST_PSEUDO_REGISTER 1933 && usize < qty[reg_qty[ureg]].size) 1934 /* Can't combine if SREG is not a register we can allocate. */ 1935 || (sreg >= FIRST_PSEUDO_REGISTER && reg_qty[sreg] == -1) 1936 /* Don't combine with a pseudo mentioned in a REG_NO_CONFLICT note. 1937 These have already been taken care of. This probably wouldn't 1938 combine anyway, but don't take any chances. */ 1939 || (ureg >= FIRST_PSEUDO_REGISTER 1940 && find_reg_note (insn, REG_NO_CONFLICT, usedreg)) 1941 /* Don't tie something to itself. In most cases it would make no 1942 difference, but it would screw up if the reg being tied to itself 1943 also dies in this insn. */ 1944 || ureg == sreg 1945 /* Don't try to connect two different hardware registers. */ 1946 || (ureg < FIRST_PSEUDO_REGISTER && sreg < FIRST_PSEUDO_REGISTER) 1947 /* Don't connect two different machine modes if they have different 1948 implications as to which registers may be used. */ 1949 || !MODES_TIEABLE_P (GET_MODE (usedreg), GET_MODE (setreg))) 1950 return 0; 1951 1952 /* Now, if UREG is a hard reg and SREG is a pseudo, record the hard reg in 1953 qty_phys_sugg for the pseudo instead of tying them. 1954 1955 Return "failure" so that the lifespan of UREG is terminated here; 1956 that way the two lifespans will be disjoint and nothing will prevent 1957 the pseudo reg from being given this hard reg. */ 1958 1959 if (ureg < FIRST_PSEUDO_REGISTER) 1960 { 1961 /* Allocate a quantity number so we have a place to put our 1962 suggestions. */ 1963 if (reg_qty[sreg] == -2) 1964 reg_is_born (setreg, 2 * insn_number); 1965 1966 if (reg_qty[sreg] >= 0) 1967 { 1968 if (may_save_copy 1969 && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg)) 1970 { 1971 SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg); 1972 qty_phys_num_copy_sugg[reg_qty[sreg]]++; 1973 } 1974 else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg)) 1975 { 1976 SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg); 1977 qty_phys_num_sugg[reg_qty[sreg]]++; 1978 } 1979 } 1980 return 0; 1981 } 1982 1983 /* Similarly for SREG a hard register and UREG a pseudo register. */ 1984 1985 if (sreg < FIRST_PSEUDO_REGISTER) 1986 { 1987 if (may_save_copy 1988 && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg)) 1989 { 1990 SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg); 1991 qty_phys_num_copy_sugg[reg_qty[ureg]]++; 1992 } 1993 else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg)) 1994 { 1995 SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg); 1996 qty_phys_num_sugg[reg_qty[ureg]]++; 1997 } 1998 return 0; 1999 } 2000 2001 /* At this point we know that SREG and UREG are both pseudos. 2002 Do nothing if SREG already has a quantity or is a register that we 2003 don't allocate. */ 2004 if (reg_qty[sreg] >= -1 2005 /* If we are not going to let any regs live across calls, 2006 don't tie a call-crossing reg to a non-call-crossing reg. */ 2007 || (current_function_has_nonlocal_label 2008 && ((REG_N_CALLS_CROSSED (ureg) > 0) 2009 != (REG_N_CALLS_CROSSED (sreg) > 0)))) 2010 return 0; 2011 2012 /* We don't already know about SREG, so tie it to UREG 2013 if this is the last use of UREG, provided the classes they want 2014 are compatible. */ 2015 2016 if ((already_dead || find_regno_note (insn, REG_DEAD, ureg)) 2017 && reg_meets_class_p (sreg, qty[reg_qty[ureg]].min_class)) 2018 { 2019 /* Add SREG to UREG's quantity. */ 2020 sqty = reg_qty[ureg]; 2021 reg_qty[sreg] = sqty; 2022 reg_offset[sreg] = reg_offset[ureg] + offset; 2023 reg_next_in_qty[sreg] = qty[sqty].first_reg; 2024 qty[sqty].first_reg = sreg; 2025 2026 /* If SREG's reg class is smaller, set qty[SQTY].min_class. */ 2027 update_qty_class (sqty, sreg); 2028 2029 /* Update info about quantity SQTY. */ 2030 qty[sqty].n_calls_crossed += REG_N_CALLS_CROSSED (sreg); 2031 qty[sqty].n_throwing_calls_crossed 2032 += REG_N_THROWING_CALLS_CROSSED (sreg); 2033 qty[sqty].n_refs += REG_N_REFS (sreg); 2034 qty[sqty].freq += REG_FREQ (sreg); 2035 if (usize < ssize) 2036 { 2037 int i; 2038 2039 for (i = qty[sqty].first_reg; i >= 0; i = reg_next_in_qty[i]) 2040 reg_offset[i] -= offset; 2041 2042 qty[sqty].size = ssize; 2043 qty[sqty].mode = GET_MODE (setreg); 2044 } 2045 } 2046 else 2047 return 0; 2048 2049 return 1; 2050} 2051 2052/* Return 1 if the preferred class of REG allows it to be tied 2053 to a quantity or register whose class is CLASS. 2054 True if REG's reg class either contains or is contained in CLASS. */ 2055 2056static int 2057reg_meets_class_p (int reg, enum reg_class class) 2058{ 2059 enum reg_class rclass = reg_preferred_class (reg); 2060 return (reg_class_subset_p (rclass, class) 2061 || reg_class_subset_p (class, rclass)); 2062} 2063 2064/* Update the class of QTYNO assuming that REG is being tied to it. */ 2065 2066static void 2067update_qty_class (int qtyno, int reg) 2068{ 2069 enum reg_class rclass = reg_preferred_class (reg); 2070 if (reg_class_subset_p (rclass, qty[qtyno].min_class)) 2071 qty[qtyno].min_class = rclass; 2072 2073 rclass = reg_alternate_class (reg); 2074 if (reg_class_subset_p (rclass, qty[qtyno].alternate_class)) 2075 qty[qtyno].alternate_class = rclass; 2076} 2077 2078/* Handle something which alters the value of an rtx REG. 2079 2080 REG is whatever is set or clobbered. SETTER is the rtx that 2081 is modifying the register. 2082 2083 If it is not really a register, we do nothing. 2084 The file-global variables `this_insn' and `this_insn_number' 2085 carry info from `block_alloc'. */ 2086 2087static void 2088reg_is_set (rtx reg, rtx setter, void *data ATTRIBUTE_UNUSED) 2089{ 2090 /* Note that note_stores will only pass us a SUBREG if it is a SUBREG of 2091 a hard register. These may actually not exist any more. */ 2092 2093 if (GET_CODE (reg) != SUBREG 2094 && !REG_P (reg)) 2095 return; 2096 2097 /* Mark this register as being born. If it is used in a CLOBBER, mark 2098 it as being born halfway between the previous insn and this insn so that 2099 it conflicts with our inputs but not the outputs of the previous insn. */ 2100 2101 reg_is_born (reg, 2 * this_insn_number - (GET_CODE (setter) == CLOBBER)); 2102} 2103 2104/* Handle beginning of the life of register REG. 2105 BIRTH is the index at which this is happening. */ 2106 2107static void 2108reg_is_born (rtx reg, int birth) 2109{ 2110 int regno; 2111 2112 if (GET_CODE (reg) == SUBREG) 2113 { 2114 regno = REGNO (SUBREG_REG (reg)); 2115 if (regno < FIRST_PSEUDO_REGISTER) 2116 regno = subreg_regno (reg); 2117 } 2118 else 2119 regno = REGNO (reg); 2120 2121 if (regno < FIRST_PSEUDO_REGISTER) 2122 { 2123 mark_life (regno, GET_MODE (reg), 1); 2124 2125 /* If the register was to have been born earlier that the present 2126 insn, mark it as live where it is actually born. */ 2127 if (birth < 2 * this_insn_number) 2128 post_mark_life (regno, GET_MODE (reg), 1, birth, 2 * this_insn_number); 2129 } 2130 else 2131 { 2132 if (reg_qty[regno] == -2) 2133 alloc_qty (regno, GET_MODE (reg), PSEUDO_REGNO_SIZE (regno), birth); 2134 2135 /* If this register has a quantity number, show that it isn't dead. */ 2136 if (reg_qty[regno] >= 0) 2137 qty[reg_qty[regno]].death = -1; 2138 } 2139} 2140 2141/* Record the death of REG in the current insn. If OUTPUT_P is nonzero, 2142 REG is an output that is dying (i.e., it is never used), otherwise it 2143 is an input (the normal case). 2144 If OUTPUT_P is 1, then we extend the life past the end of this insn. */ 2145 2146static void 2147wipe_dead_reg (rtx reg, int output_p) 2148{ 2149 int regno = REGNO (reg); 2150 2151 /* If this insn has multiple results, 2152 and the dead reg is used in one of the results, 2153 extend its life to after this insn, 2154 so it won't get allocated together with any other result of this insn. 2155 2156 It is unsafe to use !single_set here since it will ignore an unused 2157 output. Just because an output is unused does not mean the compiler 2158 can assume the side effect will not occur. Consider if REG appears 2159 in the address of an output and we reload the output. If we allocate 2160 REG to the same hard register as an unused output we could set the hard 2161 register before the output reload insn. */ 2162 if (GET_CODE (PATTERN (this_insn)) == PARALLEL 2163 && multiple_sets (this_insn)) 2164 { 2165 int i; 2166 for (i = XVECLEN (PATTERN (this_insn), 0) - 1; i >= 0; i--) 2167 { 2168 rtx set = XVECEXP (PATTERN (this_insn), 0, i); 2169 if (GET_CODE (set) == SET 2170 && !REG_P (SET_DEST (set)) 2171 && !rtx_equal_p (reg, SET_DEST (set)) 2172 && reg_overlap_mentioned_p (reg, SET_DEST (set))) 2173 output_p = 1; 2174 } 2175 } 2176 2177 /* If this register is used in an auto-increment address, then extend its 2178 life to after this insn, so that it won't get allocated together with 2179 the result of this insn. */ 2180 if (! output_p && find_regno_note (this_insn, REG_INC, regno)) 2181 output_p = 1; 2182 2183 if (regno < FIRST_PSEUDO_REGISTER) 2184 { 2185 mark_life (regno, GET_MODE (reg), 0); 2186 2187 /* If a hard register is dying as an output, mark it as in use at 2188 the beginning of this insn (the above statement would cause this 2189 not to happen). */ 2190 if (output_p) 2191 post_mark_life (regno, GET_MODE (reg), 1, 2192 2 * this_insn_number, 2 * this_insn_number + 1); 2193 } 2194 2195 else if (reg_qty[regno] >= 0) 2196 qty[reg_qty[regno]].death = 2 * this_insn_number + output_p; 2197} 2198 2199/* Find a block of SIZE words of hard regs in reg_class CLASS 2200 that can hold something of machine-mode MODE 2201 (but actually we test only the first of the block for holding MODE) 2202 and still free between insn BORN_INDEX and insn DEAD_INDEX, 2203 and return the number of the first of them. 2204 Return -1 if such a block cannot be found. 2205 If QTYNO crosses calls, insist on a register preserved by calls, 2206 unless ACCEPT_CALL_CLOBBERED is nonzero. 2207 2208 If JUST_TRY_SUGGESTED is nonzero, only try to see if the suggested 2209 register is available. If not, return -1. */ 2210 2211static int 2212find_free_reg (enum reg_class class, enum machine_mode mode, int qtyno, 2213 int accept_call_clobbered, int just_try_suggested, 2214 int born_index, int dead_index) 2215{ 2216 int i, ins; 2217 HARD_REG_SET first_used, used; 2218#ifdef ELIMINABLE_REGS 2219 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS; 2220#endif 2221 2222 /* Validate our parameters. */ 2223 gcc_assert (born_index >= 0 && born_index <= dead_index); 2224 2225 /* Don't let a pseudo live in a reg across a function call 2226 if we might get a nonlocal goto. */ 2227 if (current_function_has_nonlocal_label 2228 && qty[qtyno].n_calls_crossed > 0) 2229 return -1; 2230 2231 if (accept_call_clobbered) 2232 COPY_HARD_REG_SET (used, call_fixed_reg_set); 2233 else if (qty[qtyno].n_calls_crossed == 0) 2234 COPY_HARD_REG_SET (used, fixed_reg_set); 2235 else 2236 COPY_HARD_REG_SET (used, call_used_reg_set); 2237 2238 if (accept_call_clobbered) 2239 IOR_HARD_REG_SET (used, losing_caller_save_reg_set); 2240 2241 for (ins = born_index; ins < dead_index; ins++) 2242 IOR_HARD_REG_SET (used, regs_live_at[ins]); 2243 2244 IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]); 2245 2246 /* Don't use the frame pointer reg in local-alloc even if 2247 we may omit the frame pointer, because if we do that and then we 2248 need a frame pointer, reload won't know how to move the pseudo 2249 to another hard reg. It can move only regs made by global-alloc. 2250 2251 This is true of any register that can be eliminated. */ 2252#ifdef ELIMINABLE_REGS 2253 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++) 2254 SET_HARD_REG_BIT (used, eliminables[i].from); 2255#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 2256 /* If FRAME_POINTER_REGNUM is not a real register, then protect the one 2257 that it might be eliminated into. */ 2258 SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM); 2259#endif 2260#else 2261 SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM); 2262#endif 2263 2264#ifdef CANNOT_CHANGE_MODE_CLASS 2265 cannot_change_mode_set_regs (&used, mode, qty[qtyno].first_reg); 2266#endif 2267 2268 /* Normally, the registers that can be used for the first register in 2269 a multi-register quantity are the same as those that can be used for 2270 subsequent registers. However, if just trying suggested registers, 2271 restrict our consideration to them. If there are copy-suggested 2272 register, try them. Otherwise, try the arithmetic-suggested 2273 registers. */ 2274 COPY_HARD_REG_SET (first_used, used); 2275 2276 if (just_try_suggested) 2277 { 2278 if (qty_phys_num_copy_sugg[qtyno] != 0) 2279 IOR_COMPL_HARD_REG_SET (first_used, qty_phys_copy_sugg[qtyno]); 2280 else 2281 IOR_COMPL_HARD_REG_SET (first_used, qty_phys_sugg[qtyno]); 2282 } 2283 2284 /* If all registers are excluded, we can't do anything. */ 2285 GO_IF_HARD_REG_SUBSET (reg_class_contents[(int) ALL_REGS], first_used, fail); 2286 2287 /* If at least one would be suitable, test each hard reg. */ 2288 2289 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 2290 { 2291#ifdef REG_ALLOC_ORDER 2292 int regno = reg_alloc_order[i]; 2293#else 2294 int regno = i; 2295#endif 2296 if (! TEST_HARD_REG_BIT (first_used, regno) 2297 && HARD_REGNO_MODE_OK (regno, mode) 2298 && (qty[qtyno].n_calls_crossed == 0 2299 || accept_call_clobbered 2300 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))) 2301 { 2302 int j; 2303 int size1 = hard_regno_nregs[regno][mode]; 2304 for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++); 2305 if (j == size1) 2306 { 2307 /* Mark that this register is in use between its birth and death 2308 insns. */ 2309 post_mark_life (regno, mode, 1, born_index, dead_index); 2310 return regno; 2311 } 2312#ifndef REG_ALLOC_ORDER 2313 /* Skip starting points we know will lose. */ 2314 i += j; 2315#endif 2316 } 2317 } 2318 2319 fail: 2320 /* If we are just trying suggested register, we have just tried copy- 2321 suggested registers, and there are arithmetic-suggested registers, 2322 try them. */ 2323 2324 /* If it would be profitable to allocate a call-clobbered register 2325 and save and restore it around calls, do that. */ 2326 if (just_try_suggested && qty_phys_num_copy_sugg[qtyno] != 0 2327 && qty_phys_num_sugg[qtyno] != 0) 2328 { 2329 /* Don't try the copy-suggested regs again. */ 2330 qty_phys_num_copy_sugg[qtyno] = 0; 2331 return find_free_reg (class, mode, qtyno, accept_call_clobbered, 1, 2332 born_index, dead_index); 2333 } 2334 2335 /* We need not check to see if the current function has nonlocal 2336 labels because we don't put any pseudos that are live over calls in 2337 registers in that case. Avoid putting pseudos crossing calls that 2338 might throw into call used registers. */ 2339 2340 if (! accept_call_clobbered 2341 && flag_caller_saves 2342 && ! just_try_suggested 2343 && qty[qtyno].n_calls_crossed != 0 2344 && qty[qtyno].n_throwing_calls_crossed == 0 2345 && CALLER_SAVE_PROFITABLE (qty[qtyno].n_refs, 2346 qty[qtyno].n_calls_crossed)) 2347 { 2348 i = find_free_reg (class, mode, qtyno, 1, 0, born_index, dead_index); 2349 if (i >= 0) 2350 caller_save_needed = 1; 2351 return i; 2352 } 2353 return -1; 2354} 2355 2356/* Mark that REGNO with machine-mode MODE is live starting from the current 2357 insn (if LIFE is nonzero) or dead starting at the current insn (if LIFE 2358 is zero). */ 2359 2360static void 2361mark_life (int regno, enum machine_mode mode, int life) 2362{ 2363 int j = hard_regno_nregs[regno][mode]; 2364 if (life) 2365 while (--j >= 0) 2366 SET_HARD_REG_BIT (regs_live, regno + j); 2367 else 2368 while (--j >= 0) 2369 CLEAR_HARD_REG_BIT (regs_live, regno + j); 2370} 2371 2372/* Mark register number REGNO (with machine-mode MODE) as live (if LIFE 2373 is nonzero) or dead (if LIFE is zero) from insn number BIRTH (inclusive) 2374 to insn number DEATH (exclusive). */ 2375 2376static void 2377post_mark_life (int regno, enum machine_mode mode, int life, int birth, 2378 int death) 2379{ 2380 int j = hard_regno_nregs[regno][mode]; 2381 HARD_REG_SET this_reg; 2382 2383 CLEAR_HARD_REG_SET (this_reg); 2384 while (--j >= 0) 2385 SET_HARD_REG_BIT (this_reg, regno + j); 2386 2387 if (life) 2388 while (birth < death) 2389 { 2390 IOR_HARD_REG_SET (regs_live_at[birth], this_reg); 2391 birth++; 2392 } 2393 else 2394 while (birth < death) 2395 { 2396 AND_COMPL_HARD_REG_SET (regs_live_at[birth], this_reg); 2397 birth++; 2398 } 2399} 2400 2401/* INSN is the CLOBBER insn that starts a REG_NO_NOCONFLICT block, R0 2402 is the register being clobbered, and R1 is a register being used in 2403 the equivalent expression. 2404 2405 If R1 dies in the block and has a REG_NO_CONFLICT note on every insn 2406 in which it is used, return 1. 2407 2408 Otherwise, return 0. */ 2409 2410static int 2411no_conflict_p (rtx insn, rtx r0 ATTRIBUTE_UNUSED, rtx r1) 2412{ 2413 int ok = 0; 2414 rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX); 2415 rtx p, last; 2416 2417 /* If R1 is a hard register, return 0 since we handle this case 2418 when we scan the insns that actually use it. */ 2419 2420 if (note == 0 2421 || (REG_P (r1) && REGNO (r1) < FIRST_PSEUDO_REGISTER) 2422 || (GET_CODE (r1) == SUBREG && REG_P (SUBREG_REG (r1)) 2423 && REGNO (SUBREG_REG (r1)) < FIRST_PSEUDO_REGISTER)) 2424 return 0; 2425 2426 last = XEXP (note, 0); 2427 2428 for (p = NEXT_INSN (insn); p && p != last; p = NEXT_INSN (p)) 2429 if (INSN_P (p)) 2430 { 2431 if (find_reg_note (p, REG_DEAD, r1)) 2432 ok = 1; 2433 2434 /* There must be a REG_NO_CONFLICT note on every insn, otherwise 2435 some earlier optimization pass has inserted instructions into 2436 the sequence, and it is not safe to perform this optimization. 2437 Note that emit_no_conflict_block always ensures that this is 2438 true when these sequences are created. */ 2439 if (! find_reg_note (p, REG_NO_CONFLICT, r1)) 2440 return 0; 2441 } 2442 2443 return ok; 2444} 2445 2446/* Return the number of alternatives for which the constraint string P 2447 indicates that the operand must be equal to operand 0 and that no register 2448 is acceptable. */ 2449 2450static int 2451requires_inout (const char *p) 2452{ 2453 char c; 2454 int found_zero = 0; 2455 int reg_allowed = 0; 2456 int num_matching_alts = 0; 2457 int len; 2458 2459 for ( ; (c = *p); p += len) 2460 { 2461 len = CONSTRAINT_LEN (c, p); 2462 switch (c) 2463 { 2464 case '=': case '+': case '?': 2465 case '#': case '&': case '!': 2466 case '*': case '%': 2467 case 'm': case '<': case '>': case 'V': case 'o': 2468 case 'E': case 'F': case 'G': case 'H': 2469 case 's': case 'i': case 'n': 2470 case 'I': case 'J': case 'K': case 'L': 2471 case 'M': case 'N': case 'O': case 'P': 2472 case 'X': 2473 /* These don't say anything we care about. */ 2474 break; 2475 2476 case ',': 2477 if (found_zero && ! reg_allowed) 2478 num_matching_alts++; 2479 2480 found_zero = reg_allowed = 0; 2481 break; 2482 2483 case '0': 2484 found_zero = 1; 2485 break; 2486 2487 case '1': case '2': case '3': case '4': case '5': 2488 case '6': case '7': case '8': case '9': 2489 /* Skip the balance of the matching constraint. */ 2490 do 2491 p++; 2492 while (ISDIGIT (*p)); 2493 len = 0; 2494 break; 2495 2496 default: 2497 if (REG_CLASS_FROM_CONSTRAINT (c, p) == NO_REGS 2498 && !EXTRA_ADDRESS_CONSTRAINT (c, p)) 2499 break; 2500 /* Fall through. */ 2501 case 'p': 2502 case 'g': case 'r': 2503 reg_allowed = 1; 2504 break; 2505 } 2506 } 2507 2508 if (found_zero && ! reg_allowed) 2509 num_matching_alts++; 2510 2511 return num_matching_alts; 2512} 2513 2514void 2515dump_local_alloc (FILE *file) 2516{ 2517 int i; 2518 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 2519 if (reg_renumber[i] != -1) 2520 fprintf (file, ";; Register %d in %d.\n", i, reg_renumber[i]); 2521} 2522 2523/* Run old register allocator. Return TRUE if we must exit 2524 rest_of_compilation upon return. */ 2525static void 2526rest_of_handle_local_alloc (void) 2527{ 2528 int rebuild_notes; 2529 2530 /* Determine if the current function is a leaf before running reload 2531 since this can impact optimizations done by the prologue and 2532 epilogue thus changing register elimination offsets. */ 2533 current_function_is_leaf = leaf_function_p (); 2534 2535 /* Allocate the reg_renumber array. */ 2536 allocate_reg_info (max_regno, FALSE, TRUE); 2537 2538 /* And the reg_equiv_memory_loc array. */ 2539 VARRAY_GROW (reg_equiv_memory_loc_varray, max_regno); 2540 reg_equiv_memory_loc = &VARRAY_RTX (reg_equiv_memory_loc_varray, 0); 2541 2542 allocate_initial_values (reg_equiv_memory_loc); 2543 2544 regclass (get_insns (), max_reg_num (), dump_file); 2545 rebuild_notes = local_alloc (); 2546 2547 /* Local allocation may have turned an indirect jump into a direct 2548 jump. If so, we must rebuild the JUMP_LABEL fields of jumping 2549 instructions. */ 2550 if (rebuild_notes) 2551 { 2552 timevar_push (TV_JUMP); 2553 2554 rebuild_jump_labels (get_insns ()); 2555 purge_all_dead_edges (); 2556 delete_unreachable_blocks (); 2557 2558 timevar_pop (TV_JUMP); 2559 } 2560 2561 if (dump_enabled_p (pass_local_alloc.static_pass_number)) 2562 { 2563 timevar_push (TV_DUMP); 2564 dump_flow_info (dump_file); 2565 dump_local_alloc (dump_file); 2566 timevar_pop (TV_DUMP); 2567 } 2568} 2569 2570struct tree_opt_pass pass_local_alloc = 2571{ 2572 "lreg", /* name */ 2573 NULL, /* gate */ 2574 rest_of_handle_local_alloc, /* execute */ 2575 NULL, /* sub */ 2576 NULL, /* next */ 2577 0, /* static_pass_number */ 2578 TV_LOCAL_ALLOC, /* tv_id */ 2579 0, /* properties_required */ 2580 0, /* properties_provided */ 2581 0, /* properties_destroyed */ 2582 0, /* todo_flags_start */ 2583 TODO_dump_func | 2584 TODO_ggc_collect, /* todo_flags_finish */ 2585 'l' /* letter */ 2586}; 2587 2588