118334Speter/* Allocate registers for pseudo-registers that span basic blocks. 290075Sobrien Copyright (C) 1987, 1988, 1991, 1994, 1996, 1997, 1998, 3169689Skan 1999, 2000, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 418334Speter 590075SobrienThis file is part of GCC. 618334Speter 790075SobrienGCC is free software; you can redistribute it and/or modify it under 890075Sobrienthe terms of the GNU General Public License as published by the Free 990075SobrienSoftware Foundation; either version 2, or (at your option) any later 1090075Sobrienversion. 1118334Speter 1290075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1390075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1490075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1590075Sobrienfor more details. 1618334Speter 1718334SpeterYou should have received a copy of the GNU General Public License 1890075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 2118334Speter 2218334Speter 2318334Speter#include "config.h" 2450397Sobrien#include "system.h" 25132718Skan#include "coretypes.h" 26132718Skan#include "tm.h" 2750397Sobrien#include "machmode.h" 2850397Sobrien#include "hard-reg-set.h" 2918334Speter#include "rtl.h" 3090075Sobrien#include "tm_p.h" 3118334Speter#include "flags.h" 3218334Speter#include "regs.h" 3390075Sobrien#include "function.h" 3418334Speter#include "insn-config.h" 35169689Skan#include "recog.h" 3652284Sobrien#include "reload.h" 3718334Speter#include "output.h" 3850397Sobrien#include "toplev.h" 39169689Skan#include "tree-pass.h" 40169689Skan#include "timevar.h" 41169689Skan#include "vecprim.h" 4218334Speter 4318334Speter/* This pass of the compiler performs global register allocation. 4418334Speter It assigns hard register numbers to all the pseudo registers 4518334Speter that were not handled in local_alloc. Assignments are recorded 4618334Speter in the vector reg_renumber, not by changing the rtl code. 4718334Speter (Such changes are made by final). The entry point is 4818334Speter the function global_alloc. 4918334Speter 5018334Speter After allocation is complete, the reload pass is run as a subroutine 5118334Speter of this pass, so that when a pseudo reg loses its hard reg due to 5218334Speter spilling it is possible to make a second attempt to find a hard 5318334Speter reg for it. The reload pass is independent in other respects 5418334Speter and it is run even when stupid register allocation is in use. 5518334Speter 5652284Sobrien 1. Assign allocation-numbers (allocnos) to the pseudo-registers 5752284Sobrien still needing allocations and to the pseudo-registers currently 5852284Sobrien allocated by local-alloc which may be spilled by reload. 59117395Skan Set up tables reg_allocno and allocno_reg to map 6018334Speter reg numbers to allocnos and vice versa. 6118334Speter max_allocno gets the number of allocnos in use. 6218334Speter 6318334Speter 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it. 6418334Speter Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix 6518334Speter for conflicts between allocnos and explicit hard register use 6618334Speter (which includes use of pseudo-registers allocated by local_alloc). 6718334Speter 6852284Sobrien 3. For each basic block 6918334Speter walk forward through the block, recording which 7052284Sobrien pseudo-registers and which hardware registers are live. 7152284Sobrien Build the conflict matrix between the pseudo-registers 7252284Sobrien and another of pseudo-registers versus hardware registers. 7318334Speter Also record the preferred hardware registers 7452284Sobrien for each pseudo-register. 7518334Speter 7618334Speter 4. Sort a table of the allocnos into order of 7718334Speter desirability of the variables. 7818334Speter 7918334Speter 5. Allocate the variables in that order; each if possible into 8018334Speter a preferred register, else into another register. */ 8118334Speter 8290075Sobrien/* Number of pseudo-registers which are candidates for allocation. */ 8318334Speter 8418334Speterstatic int max_allocno; 8518334Speter 8618334Speter/* Indexed by (pseudo) reg number, gives the allocno, or -1 8752284Sobrien for pseudo registers which are not to be allocated. */ 8818334Speter 8952284Sobrienstatic int *reg_allocno; 9018334Speter 9190075Sobrienstruct allocno 9290075Sobrien{ 9390075Sobrien int reg; 9490075Sobrien /* Gives the number of consecutive hard registers needed by that 9590075Sobrien pseudo reg. */ 9690075Sobrien int size; 9718334Speter 9890075Sobrien /* Number of calls crossed by each allocno. */ 9990075Sobrien int calls_crossed; 10018334Speter 101161651Skan /* Number of calls that might throw crossed by each allocno. */ 102161651Skan int throwing_calls_crossed; 103161651Skan 10490075Sobrien /* Number of refs to each allocno. */ 10590075Sobrien int n_refs; 10690075Sobrien 10790075Sobrien /* Frequency of uses of each allocno. */ 10890075Sobrien int freq; 10990075Sobrien 11090075Sobrien /* Guess at live length of each allocno. 11190075Sobrien This is actually the max of the live lengths of the regs. */ 11290075Sobrien int live_length; 11390075Sobrien 11490075Sobrien /* Set of hard regs conflicting with allocno N. */ 11590075Sobrien 11690075Sobrien HARD_REG_SET hard_reg_conflicts; 11790075Sobrien 11890075Sobrien /* Set of hard regs preferred by allocno N. 11990075Sobrien This is used to make allocnos go into regs that are copied to or from them, 12090075Sobrien when possible, to reduce register shuffling. */ 12190075Sobrien 12290075Sobrien HARD_REG_SET hard_reg_preferences; 12390075Sobrien 12490075Sobrien /* Similar, but just counts register preferences made in simple copy 12590075Sobrien operations, rather than arithmetic. These are given priority because 12690075Sobrien we can always eliminate an insn by using these, but using a register 12790075Sobrien in the above list won't always eliminate an insn. */ 12890075Sobrien 12990075Sobrien HARD_REG_SET hard_reg_copy_preferences; 13090075Sobrien 13190075Sobrien /* Similar to hard_reg_preferences, but includes bits for subsequent 13290075Sobrien registers when an allocno is multi-word. The above variable is used for 13390075Sobrien allocation while this is used to build reg_someone_prefers, below. */ 13490075Sobrien 13590075Sobrien HARD_REG_SET hard_reg_full_preferences; 13690075Sobrien 13790075Sobrien /* Set of hard registers that some later allocno has a preference for. */ 13890075Sobrien 13990075Sobrien HARD_REG_SET regs_someone_prefers; 140110611Skan 141110611Skan#ifdef STACK_REGS 142110611Skan /* Set to true if allocno can't be allocated in the stack register. */ 143110611Skan bool no_stack_reg; 144110611Skan#endif 14590075Sobrien}; 14690075Sobrien 14790075Sobrienstatic struct allocno *allocno; 14890075Sobrien 14918334Speter/* A vector of the integers from 0 to max_allocno-1, 15018334Speter sorted in the order of first-to-be-allocated first. */ 15118334Speter 15218334Speterstatic int *allocno_order; 15318334Speter 15418334Speter/* Indexed by (pseudo) reg number, gives the number of another 15518334Speter lower-numbered pseudo reg which can share a hard reg with this pseudo 15618334Speter *even if the two pseudos would otherwise appear to conflict*. */ 15718334Speter 15818334Speterstatic int *reg_may_share; 15918334Speter 16018334Speter/* Define the number of bits in each element of `conflicts' and what 16118334Speter type that element has. We use the largest integer format on the 16218334Speter host machine. */ 16318334Speter 16418334Speter#define INT_BITS HOST_BITS_PER_WIDE_INT 16518334Speter#define INT_TYPE HOST_WIDE_INT 16618334Speter 16718334Speter/* max_allocno by max_allocno array of bits, 16818334Speter recording whether two allocno's conflict (can't go in the same 16918334Speter hardware register). 17018334Speter 17190075Sobrien `conflicts' is symmetric after the call to mirror_conflicts. */ 17218334Speter 17318334Speterstatic INT_TYPE *conflicts; 17418334Speter 175169689Skan/* Number of ints required to hold max_allocno bits. 17618334Speter This is the length of a row in `conflicts'. */ 17718334Speter 17818334Speterstatic int allocno_row_words; 17918334Speter 18018334Speter/* Two macros to test or store 1 in an element of `conflicts'. */ 18118334Speter 18218334Speter#define CONFLICTP(I, J) \ 18390075Sobrien (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS] \ 18490075Sobrien & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS))) 18518334Speter 18690075Sobrien/* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno, 18790075Sobrien and execute CODE. */ 18890075Sobrien#define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \ 18990075Sobriendo { \ 19090075Sobrien int i_; \ 19190075Sobrien int allocno_; \ 19290075Sobrien INT_TYPE *p_ = (ALLOCNO_SET); \ 19390075Sobrien \ 19490075Sobrien for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \ 19590075Sobrien i_--, allocno_ += INT_BITS) \ 19690075Sobrien { \ 19790075Sobrien unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \ 19890075Sobrien \ 19990075Sobrien for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \ 20090075Sobrien { \ 20190075Sobrien if (word_ & 1) \ 20290075Sobrien {CODE;} \ 20390075Sobrien } \ 20490075Sobrien } \ 20590075Sobrien} while (0) 20690075Sobrien 20790075Sobrien/* This doesn't work for non-GNU C due to the way CODE is macro expanded. */ 20890075Sobrien#if 0 20990075Sobrien/* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to 21090075Sobrien the conflicting allocno, and execute CODE. This macro assumes that 21190075Sobrien mirror_conflicts has been run. */ 21290075Sobrien#define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\ 21390075Sobrien EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\ 21490075Sobrien OUT_ALLOCNO, (CODE)) 21590075Sobrien#endif 21690075Sobrien 21718334Speter/* Set of hard regs currently live (during scan of all insns). */ 21818334Speter 21918334Speterstatic HARD_REG_SET hard_regs_live; 22018334Speter 22118334Speter/* Set of registers that global-alloc isn't supposed to use. */ 22218334Speter 22318334Speterstatic HARD_REG_SET no_global_alloc_regs; 22418334Speter 22518334Speter/* Set of registers used so far. */ 22618334Speter 22718334Speterstatic HARD_REG_SET regs_used_so_far; 22818334Speter 22990075Sobrien/* Number of refs to each hard reg, as used by local alloc. 23018334Speter It is zero for a reg that contains global pseudos or is explicitly used. */ 23118334Speter 23218334Speterstatic int local_reg_n_refs[FIRST_PSEUDO_REGISTER]; 23318334Speter 23490075Sobrien/* Frequency of uses of given hard reg. */ 23590075Sobrienstatic int local_reg_freq[FIRST_PSEUDO_REGISTER]; 23690075Sobrien 23718334Speter/* Guess at live length of each hard reg, as used by local alloc. 23818334Speter This is actually the sum of the live lengths of the specific regs. */ 23918334Speter 24018334Speterstatic int local_reg_live_length[FIRST_PSEUDO_REGISTER]; 24118334Speter 242117395Skan/* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector 243117395Skan element I, and hard register number J. */ 24418334Speter 24590075Sobrien#define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J) 24618334Speter 24718334Speter/* Bit mask for allocnos live at current point in the scan. */ 24818334Speter 24918334Speterstatic INT_TYPE *allocnos_live; 25018334Speter 25118334Speter/* Test, set or clear bit number I in allocnos_live, 25218334Speter a bit vector indexed by allocno. */ 25318334Speter 25490075Sobrien#define SET_ALLOCNO_LIVE(I) \ 25590075Sobrien (allocnos_live[(unsigned) (I) / INT_BITS] \ 25690075Sobrien |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS))) 25718334Speter 25890075Sobrien#define CLEAR_ALLOCNO_LIVE(I) \ 25990075Sobrien (allocnos_live[(unsigned) (I) / INT_BITS] \ 26090075Sobrien &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS))) 26118334Speter 26218334Speter/* This is turned off because it doesn't work right for DImode. 26318334Speter (And it is only used for DImode, so the other cases are worthless.) 26418334Speter The problem is that it isn't true that there is NO possibility of conflict; 26518334Speter only that there is no conflict if the two pseudos get the exact same regs. 26618334Speter If they were allocated with a partial overlap, there would be a conflict. 26718334Speter We can't safely turn off the conflict unless we have another way to 26818334Speter prevent the partial overlap. 26918334Speter 27018334Speter Idea: change hard_reg_conflicts so that instead of recording which 27118334Speter hard regs the allocno may not overlap, it records where the allocno 27218334Speter may not start. Change both where it is used and where it is updated. 27318334Speter Then there is a way to record that (reg:DI 108) may start at 10 27418334Speter but not at 9 or 11. There is still the question of how to record 27518334Speter this semi-conflict between two pseudos. */ 27618334Speter#if 0 27718334Speter/* Reg pairs for which conflict after the current insn 27818334Speter is inhibited by a REG_NO_CONFLICT note. 27918334Speter If the table gets full, we ignore any other notes--that is conservative. */ 28018334Speter#define NUM_NO_CONFLICT_PAIRS 4 28118334Speter/* Number of pairs in use in this insn. */ 28218334Speterint n_no_conflict_pairs; 28318334Speterstatic struct { int allocno1, allocno2;} 28418334Speter no_conflict_pairs[NUM_NO_CONFLICT_PAIRS]; 28518334Speter#endif /* 0 */ 28618334Speter 28718334Speter/* Record all regs that are set in any one insn. 28818334Speter Communication from mark_reg_{store,clobber} and global_conflicts. */ 28918334Speter 29018334Speterstatic rtx *regs_set; 29118334Speterstatic int n_regs_set; 29218334Speter 29318334Speter/* All registers that can be eliminated. */ 29418334Speter 29518334Speterstatic HARD_REG_SET eliminable_regset; 29618334Speter 297132718Skanstatic int allocno_compare (const void *, const void *); 298132718Skanstatic void global_conflicts (void); 299132718Skanstatic void mirror_conflicts (void); 300132718Skanstatic void expand_preferences (void); 301132718Skanstatic void prune_preferences (void); 302132718Skanstatic void find_reg (int, HARD_REG_SET, int, int, int); 303132718Skanstatic void record_one_conflict (int); 304132718Skanstatic void record_conflicts (int *, int); 305132718Skanstatic void mark_reg_store (rtx, rtx, void *); 306132718Skanstatic void mark_reg_clobber (rtx, rtx, void *); 307132718Skanstatic void mark_reg_conflicts (rtx); 308132718Skanstatic void mark_reg_death (rtx); 309132718Skanstatic void mark_reg_live_nc (int, enum machine_mode); 310132718Skanstatic void set_preference (rtx, rtx); 311132718Skanstatic void dump_conflicts (FILE *); 312132718Skanstatic void reg_becomes_live (rtx, rtx, void *); 313132718Skanstatic void reg_dies (int, enum machine_mode, struct insn_chain *); 314169689Skan 315169689Skanstatic void allocate_bb_info (void); 316169689Skanstatic void free_bb_info (void); 317169689Skanstatic bool check_earlyclobber (rtx); 318169689Skanstatic void mark_reg_use_for_earlyclobber_1 (rtx *, void *); 319169689Skanstatic int mark_reg_use_for_earlyclobber (rtx *, void *); 320169689Skanstatic void calculate_local_reg_bb_info (void); 321169689Skanstatic void set_up_bb_rts_numbers (void); 322169689Skanstatic int rpost_cmp (const void *, const void *); 323169689Skanstatic void calculate_reg_pav (void); 324169689Skanstatic void modify_reg_pav (void); 325169689Skanstatic void make_accurate_live_analysis (void); 326169689Skan 32718334Speter 328169689Skan 32918334Speter/* Perform allocation of pseudo-registers not allocated by local_alloc. 33018334Speter 33118334Speter Return value is nonzero if reload failed 33218334Speter and we must not do any more for this function. */ 33318334Speter 334169689Skanstatic int 335169689Skanglobal_alloc (void) 33618334Speter{ 33750397Sobrien int retval; 33818334Speter#ifdef ELIMINABLE_REGS 33990075Sobrien static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS; 34018334Speter#endif 34118334Speter int need_fp 34218334Speter = (! flag_omit_frame_pointer 34318334Speter || (current_function_calls_alloca && EXIT_IGNORE_STACK) 34418334Speter || FRAME_POINTER_REQUIRED); 34518334Speter 34690075Sobrien size_t i; 34718334Speter rtx x; 34818334Speter 349169689Skan make_accurate_live_analysis (); 350169689Skan 35118334Speter max_allocno = 0; 35218334Speter 35318334Speter /* A machine may have certain hard registers that 35418334Speter are safe to use only within a basic block. */ 35518334Speter 35618334Speter CLEAR_HARD_REG_SET (no_global_alloc_regs); 35718334Speter 35818334Speter /* Build the regset of all eliminable registers and show we can't use those 35918334Speter that we already know won't be eliminated. */ 36018334Speter#ifdef ELIMINABLE_REGS 36190075Sobrien for (i = 0; i < ARRAY_SIZE (eliminables); i++) 36218334Speter { 363132718Skan bool cannot_elim 364132718Skan = (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to) 365132718Skan || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp)); 36618334Speter 367132718Skan if (!regs_asm_clobbered[eliminables[i].from]) 368132718Skan { 369132718Skan SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from); 370132718Skan 371132718Skan if (cannot_elim) 372132718Skan SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from); 373132718Skan } 374132718Skan else if (cannot_elim) 375132718Skan error ("%s cannot be used in asm here", 376132718Skan reg_names[eliminables[i].from]); 377132718Skan else 378132718Skan regs_ever_live[eliminables[i].from] = 1; 37918334Speter } 38018334Speter#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 381132718Skan if (!regs_asm_clobbered[HARD_FRAME_POINTER_REGNUM]) 382132718Skan { 383132718Skan SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM); 384132718Skan if (need_fp) 385132718Skan SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM); 386132718Skan } 387132718Skan else if (need_fp) 388132718Skan error ("%s cannot be used in asm here", 389132718Skan reg_names[HARD_FRAME_POINTER_REGNUM]); 390132718Skan else 391132718Skan regs_ever_live[HARD_FRAME_POINTER_REGNUM] = 1; 39218334Speter#endif 39318334Speter 39418334Speter#else 395132718Skan if (!regs_asm_clobbered[FRAME_POINTER_REGNUM]) 396132718Skan { 397132718Skan SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM); 398132718Skan if (need_fp) 399132718Skan SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM); 400132718Skan } 401132718Skan else if (need_fp) 402132718Skan error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]); 403132718Skan else 404132718Skan regs_ever_live[FRAME_POINTER_REGNUM] = 1; 40518334Speter#endif 40618334Speter 40718334Speter /* Track which registers have already been used. Start with registers 40818334Speter explicitly in the rtl, then registers allocated by local register 40918334Speter allocation. */ 41018334Speter 41118334Speter CLEAR_HARD_REG_SET (regs_used_so_far); 41218334Speter#ifdef LEAF_REGISTERS 41318334Speter /* If we are doing the leaf function optimization, and this is a leaf 41418334Speter function, it means that the registers that take work to save are those 41518334Speter that need a register window. So prefer the ones that can be used in 41618334Speter a leaf function. */ 41718334Speter { 418117395Skan const char *cheap_regs; 419117395Skan const char *const leaf_regs = LEAF_REGISTERS; 42018334Speter 42118334Speter if (only_leaf_regs_used () && leaf_function_p ()) 42218334Speter cheap_regs = leaf_regs; 42318334Speter else 42418334Speter cheap_regs = call_used_regs; 42518334Speter for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 42618334Speter if (regs_ever_live[i] || cheap_regs[i]) 42718334Speter SET_HARD_REG_BIT (regs_used_so_far, i); 42818334Speter } 42918334Speter#else 43018334Speter /* We consider registers that do not have to be saved over calls as if 43118334Speter they were already used since there is no cost in using them. */ 43218334Speter for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 43318334Speter if (regs_ever_live[i] || call_used_regs[i]) 43418334Speter SET_HARD_REG_BIT (regs_used_so_far, i); 43518334Speter#endif 43618334Speter 43752284Sobrien for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++) 43818334Speter if (reg_renumber[i] >= 0) 43918334Speter SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]); 44018334Speter 44118334Speter /* Establish mappings from register number to allocation number 44218334Speter and vice versa. In the process, count the allocnos. */ 44318334Speter 444169689Skan reg_allocno = XNEWVEC (int, max_regno); 44518334Speter 44618334Speter for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 44718334Speter reg_allocno[i] = -1; 44818334Speter 44918334Speter /* Initialize the shared-hard-reg mapping 45018334Speter from the list of pairs that may share. */ 451169689Skan reg_may_share = XCNEWVEC (int, max_regno); 45218334Speter for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1)) 45318334Speter { 45418334Speter int r1 = REGNO (XEXP (x, 0)); 45518334Speter int r2 = REGNO (XEXP (XEXP (x, 1), 0)); 45618334Speter if (r1 > r2) 45718334Speter reg_may_share[r1] = r2; 45818334Speter else 45918334Speter reg_may_share[r2] = r1; 46018334Speter } 46118334Speter 46252284Sobrien for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++) 46318334Speter /* Note that reg_live_length[i] < 0 indicates a "constant" reg 46418334Speter that we are supposed to refrain from putting in a hard reg. 46518334Speter -2 means do make an allocno but don't allocate it. */ 46652284Sobrien if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1 46718334Speter /* Don't allocate pseudos that cross calls, 46818334Speter if this function receives a nonlocal goto. */ 46918334Speter && (! current_function_has_nonlocal_label 47050397Sobrien || REG_N_CALLS_CROSSED (i) == 0)) 47118334Speter { 472169689Skan if (reg_renumber[i] < 0 473169689Skan && reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0) 47418334Speter reg_allocno[i] = reg_allocno[reg_may_share[i]]; 47518334Speter else 47618334Speter reg_allocno[i] = max_allocno++; 477169689Skan gcc_assert (REG_LIVE_LENGTH (i)); 47818334Speter } 47918334Speter else 48018334Speter reg_allocno[i] = -1; 48118334Speter 482169689Skan allocno = XCNEWVEC (struct allocno, max_allocno); 48318334Speter 48452284Sobrien for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++) 48518334Speter if (reg_allocno[i] >= 0) 48618334Speter { 48790075Sobrien int num = reg_allocno[i]; 48890075Sobrien allocno[num].reg = i; 48990075Sobrien allocno[num].size = PSEUDO_REGNO_SIZE (i); 49090075Sobrien allocno[num].calls_crossed += REG_N_CALLS_CROSSED (i); 491161651Skan allocno[num].throwing_calls_crossed 492161651Skan += REG_N_THROWING_CALLS_CROSSED (i); 49390075Sobrien allocno[num].n_refs += REG_N_REFS (i); 49490075Sobrien allocno[num].freq += REG_FREQ (i); 49590075Sobrien if (allocno[num].live_length < REG_LIVE_LENGTH (i)) 49690075Sobrien allocno[num].live_length = REG_LIVE_LENGTH (i); 49718334Speter } 49818334Speter 49918334Speter /* Calculate amount of usage of each hard reg by pseudos 50018334Speter allocated by local-alloc. This is to see if we want to 50118334Speter override it. */ 502132718Skan memset (local_reg_live_length, 0, sizeof local_reg_live_length); 503132718Skan memset (local_reg_n_refs, 0, sizeof local_reg_n_refs); 504132718Skan memset (local_reg_freq, 0, sizeof local_reg_freq); 50552284Sobrien for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++) 50652284Sobrien if (reg_renumber[i] >= 0) 50718334Speter { 50818334Speter int regno = reg_renumber[i]; 509169689Skan int endregno = regno + hard_regno_nregs[regno][PSEUDO_REGNO_MODE (i)]; 51018334Speter int j; 51118334Speter 51218334Speter for (j = regno; j < endregno; j++) 51318334Speter { 51450397Sobrien local_reg_n_refs[j] += REG_N_REFS (i); 51590075Sobrien local_reg_freq[j] += REG_FREQ (i); 51650397Sobrien local_reg_live_length[j] += REG_LIVE_LENGTH (i); 51718334Speter } 51818334Speter } 51918334Speter 52018334Speter /* We can't override local-alloc for a reg used not just by local-alloc. */ 52118334Speter for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 52218334Speter if (regs_ever_live[i]) 52390075Sobrien local_reg_n_refs[i] = 0, local_reg_freq[i] = 0; 524117395Skan 52518334Speter allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS; 52618334Speter 52750397Sobrien /* We used to use alloca here, but the size of what it would try to 52850397Sobrien allocate would occasionally cause it to exceed the stack limit and 52950397Sobrien cause unpredictable core dumps. Some examples were > 2Mb in size. */ 530169689Skan conflicts = XCNEWVEC (INT_TYPE, max_allocno * allocno_row_words); 53118334Speter 532169689Skan allocnos_live = XNEWVEC (INT_TYPE, allocno_row_words); 53318334Speter 53418334Speter /* If there is work to be done (at least one reg to allocate), 53518334Speter perform global conflict analysis and allocate the regs. */ 53618334Speter 53718334Speter if (max_allocno > 0) 53818334Speter { 53918334Speter /* Scan all the insns and compute the conflicts among allocnos 54018334Speter and between allocnos and hard regs. */ 54118334Speter 54218334Speter global_conflicts (); 54318334Speter 54490075Sobrien mirror_conflicts (); 54590075Sobrien 54618334Speter /* Eliminate conflicts between pseudos and eliminable registers. If 54718334Speter the register is not eliminated, the pseudo won't really be able to 54818334Speter live in the eliminable register, so the conflict doesn't matter. 54918334Speter If we do eliminate the register, the conflict will no longer exist. 55018334Speter So in either case, we can ignore the conflict. Likewise for 55118334Speter preferences. */ 55218334Speter 55352284Sobrien for (i = 0; i < (size_t) max_allocno; i++) 55418334Speter { 55590075Sobrien AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_conflicts, 55618334Speter eliminable_regset); 55790075Sobrien AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_copy_preferences, 55890075Sobrien eliminable_regset); 55990075Sobrien AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_preferences, 56090075Sobrien eliminable_regset); 56118334Speter } 56218334Speter 56318334Speter /* Try to expand the preferences by merging them between allocnos. */ 56418334Speter 56518334Speter expand_preferences (); 56618334Speter 56718334Speter /* Determine the order to allocate the remaining pseudo registers. */ 56818334Speter 569169689Skan allocno_order = XNEWVEC (int, max_allocno); 57052284Sobrien for (i = 0; i < (size_t) max_allocno; i++) 57118334Speter allocno_order[i] = i; 57218334Speter 57318334Speter /* Default the size to 1, since allocno_compare uses it to divide by. 57418334Speter Also convert allocno_live_length of zero to -1. A length of zero 57518334Speter can occur when all the registers for that allocno have reg_live_length 57618334Speter equal to -2. In this case, we want to make an allocno, but not 57718334Speter allocate it. So avoid the divide-by-zero and set it to a low 57818334Speter priority. */ 57918334Speter 58052284Sobrien for (i = 0; i < (size_t) max_allocno; i++) 58118334Speter { 58290075Sobrien if (allocno[i].size == 0) 58390075Sobrien allocno[i].size = 1; 58490075Sobrien if (allocno[i].live_length == 0) 58590075Sobrien allocno[i].live_length = -1; 58618334Speter } 58718334Speter 58818334Speter qsort (allocno_order, max_allocno, sizeof (int), allocno_compare); 589117395Skan 59018334Speter prune_preferences (); 59118334Speter 592169689Skan if (dump_file) 593169689Skan dump_conflicts (dump_file); 59418334Speter 59518334Speter /* Try allocating them, one by one, in that order, 59618334Speter except for parameters marked with reg_live_length[regno] == -2. */ 59718334Speter 59852284Sobrien for (i = 0; i < (size_t) max_allocno; i++) 59990075Sobrien if (reg_renumber[allocno[allocno_order[i]].reg] < 0 60090075Sobrien && REG_LIVE_LENGTH (allocno[allocno_order[i]].reg) >= 0) 60118334Speter { 60218334Speter /* If we have more than one register class, 60318334Speter first try allocating in the class that is cheapest 60418334Speter for this pseudo-reg. If that fails, try any reg. */ 60518334Speter if (N_REG_CLASSES > 1) 60618334Speter { 60750397Sobrien find_reg (allocno_order[i], 0, 0, 0, 0); 60890075Sobrien if (reg_renumber[allocno[allocno_order[i]].reg] >= 0) 60918334Speter continue; 61018334Speter } 61190075Sobrien if (reg_alternate_class (allocno[allocno_order[i]].reg) != NO_REGS) 61250397Sobrien find_reg (allocno_order[i], 0, 1, 0, 0); 61318334Speter } 61490075Sobrien 61590075Sobrien free (allocno_order); 61618334Speter } 61718334Speter 618169689Skan /* Do the reloads now while the allocno data still exists, so that we can 61918334Speter try to assign new hard regs to any pseudo regs that are spilled. */ 62018334Speter 62118334Speter#if 0 /* We need to eliminate regs even if there is no rtl code, 62218334Speter for the sake of debugging information. */ 623169689Skan if (n_basic_blocks > NUM_FIXED_BLOCKS) 62418334Speter#endif 62552284Sobrien { 62652284Sobrien build_insn_chain (get_insns ()); 62790075Sobrien retval = reload (get_insns (), 1); 62852284Sobrien } 62950397Sobrien 63090075Sobrien /* Clean up. */ 63190075Sobrien free (reg_allocno); 63290075Sobrien free (reg_may_share); 63390075Sobrien free (allocno); 63450397Sobrien free (conflicts); 63590075Sobrien free (allocnos_live); 63690075Sobrien 63750397Sobrien return retval; 63818334Speter} 63918334Speter 64018334Speter/* Sort predicate for ordering the allocnos. 64118334Speter Returns -1 (1) if *v1 should be allocated before (after) *v2. */ 64218334Speter 64318334Speterstatic int 644132718Skanallocno_compare (const void *v1p, const void *v2p) 64518334Speter{ 64690075Sobrien int v1 = *(const int *)v1p, v2 = *(const int *)v2p; 64718334Speter /* Note that the quotient will never be bigger than 64818334Speter the value of floor_log2 times the maximum number of 64990075Sobrien times a register can occur in one insn (surely less than 100) 65090075Sobrien weighted by the frequency (maximally REG_FREQ_MAX). 65190075Sobrien Multiplying this by 10000/REG_FREQ_MAX can't overflow. */ 65290075Sobrien int pri1 65390075Sobrien = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].freq) 65490075Sobrien / allocno[v1].live_length) 65590075Sobrien * (10000 / REG_FREQ_MAX) * allocno[v1].size); 65690075Sobrien int pri2 65790075Sobrien = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].freq) 65890075Sobrien / allocno[v2].live_length) 65990075Sobrien * (10000 / REG_FREQ_MAX) * allocno[v2].size); 66018334Speter if (pri2 - pri1) 66118334Speter return pri2 - pri1; 66218334Speter 66318334Speter /* If regs are equally good, sort by allocno, 66418334Speter so that the results of qsort leave nothing to chance. */ 66550397Sobrien return v1 - v2; 66618334Speter} 66718334Speter 66818334Speter/* Scan the rtl code and record all conflicts and register preferences in the 66918334Speter conflict matrices and preference tables. */ 67018334Speter 67118334Speterstatic void 672132718Skanglobal_conflicts (void) 67318334Speter{ 674169689Skan unsigned i; 675117395Skan basic_block b; 67690075Sobrien rtx insn; 67752284Sobrien int *block_start_allocnos; 67818334Speter 67918334Speter /* Make a vector that mark_reg_{store,clobber} will store in. */ 680169689Skan regs_set = XNEWVEC (rtx, max_parallel * 2); 68118334Speter 682169689Skan block_start_allocnos = XNEWVEC (int, max_allocno); 68318334Speter 684117395Skan FOR_EACH_BB (b) 68518334Speter { 686132718Skan memset (allocnos_live, 0, allocno_row_words * sizeof (INT_TYPE)); 68718334Speter 68818334Speter /* Initialize table of registers currently live 68918334Speter to the state at the beginning of this basic block. 69090075Sobrien This also marks the conflicts among hard registers 69190075Sobrien and any allocnos that are live. 69218334Speter 69318334Speter For pseudo-regs, there is only one bit for each one 69418334Speter no matter how many hard regs it occupies. 69518334Speter This is ok; we know the size from PSEUDO_REGNO_SIZE. 69618334Speter For explicit hard regs, we cannot know the size that way 69718334Speter since one hard reg can be used with various sizes. 69818334Speter Therefore, we must require that all the hard regs 69918334Speter implicitly live as part of a multi-word hard reg 700169689Skan be explicitly marked in basic_block_live_at_start. */ 70118334Speter 70218334Speter { 703169689Skan regset old = b->il.rtl->global_live_at_start; 70418334Speter int ax = 0; 705169689Skan reg_set_iterator rsi; 70618334Speter 70750397Sobrien REG_SET_TO_HARD_REG_SET (hard_regs_live, old); 708169689Skan EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i, rsi) 709169689Skan { 710169689Skan int a = reg_allocno[i]; 711169689Skan if (a >= 0) 712169689Skan { 713169689Skan SET_ALLOCNO_LIVE (a); 714169689Skan block_start_allocnos[ax++] = a; 715169689Skan } 716169689Skan else if ((a = reg_renumber[i]) >= 0) 717169689Skan mark_reg_live_nc (a, PSEUDO_REGNO_MODE (i)); 718169689Skan } 71918334Speter 72090075Sobrien /* Record that each allocno now live conflicts with each hard reg 72190075Sobrien now live. 72218334Speter 723169689Skan It is not necessary to mark any conflicts between pseudos at 72490075Sobrien this point, even for pseudos which are live at the start of 72590075Sobrien the basic block. 72690075Sobrien 72790075Sobrien Given two pseudos X and Y and any point in the CFG P. 72890075Sobrien 72990075Sobrien On any path to point P where X and Y are live one of the 73090075Sobrien following conditions must be true: 73190075Sobrien 73290075Sobrien 1. X is live at some instruction on the path that 73390075Sobrien evaluates Y. 73490075Sobrien 73590075Sobrien 2. Y is live at some instruction on the path that 73690075Sobrien evaluates X. 73790075Sobrien 738132718Skan 3. Either X or Y is not evaluated on the path to P 739169689Skan (i.e. it is used uninitialized) and thus the 74090075Sobrien conflict can be ignored. 74190075Sobrien 74290075Sobrien In cases #1 and #2 the conflict will be recorded when we 74390075Sobrien scan the instruction that makes either X or Y become live. */ 74418334Speter record_conflicts (block_start_allocnos, ax); 74550397Sobrien 746169689Skan#ifdef EH_RETURN_DATA_REGNO 747169689Skan if (bb_has_eh_pred (b)) 748169689Skan { 749169689Skan unsigned int i; 750169689Skan 751169689Skan for (i = 0; ; ++i) 752169689Skan { 753169689Skan unsigned int regno = EH_RETURN_DATA_REGNO (i); 754169689Skan if (regno == INVALID_REGNUM) 755169689Skan break; 756169689Skan record_one_conflict (regno); 757169689Skan } 758169689Skan } 759169689Skan#endif 760169689Skan 761132718Skan /* Pseudos can't go in stack regs at the start of a basic block that 762132718Skan is reached by an abnormal edge. Likewise for call clobbered regs, 763169689Skan because caller-save, fixup_abnormal_edges and possibly the table 764169689Skan driven EH machinery are not quite ready to handle such regs live 765169689Skan across such edges. */ 76652284Sobrien { 767132718Skan edge e; 768169689Skan edge_iterator ei; 76952284Sobrien 770169689Skan FOR_EACH_EDGE (e, ei, b->preds) 77152284Sobrien if (e->flags & EDGE_ABNORMAL) 77252284Sobrien break; 773132718Skan 77452284Sobrien if (e != NULL) 775117395Skan { 776132718Skan#ifdef STACK_REGS 777117395Skan EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, ax, 778132718Skan { 779132718Skan allocno[ax].no_stack_reg = 1; 780132718Skan }); 781117395Skan for (ax = FIRST_STACK_REG; ax <= LAST_STACK_REG; ax++) 782132718Skan record_one_conflict (ax); 783132718Skan#endif 784132718Skan 785132718Skan /* No need to record conflicts for call clobbered regs if we have 786132718Skan nonlocal labels around, as we don't ever try to allocate such 787132718Skan regs in this case. */ 788132718Skan if (! current_function_has_nonlocal_label) 789132718Skan for (ax = 0; ax < FIRST_PSEUDO_REGISTER; ax++) 790132718Skan if (call_used_regs [ax]) 791132718Skan record_one_conflict (ax); 792117395Skan } 79352284Sobrien } 79418334Speter } 79518334Speter 796132718Skan insn = BB_HEAD (b); 79718334Speter 79818334Speter /* Scan the code of this basic block, noting which allocnos 79918334Speter and hard regs are born or die. When one is born, 80018334Speter record a conflict with all others currently live. */ 80118334Speter 80218334Speter while (1) 80318334Speter { 80490075Sobrien RTX_CODE code = GET_CODE (insn); 80590075Sobrien rtx link; 80618334Speter 80718334Speter /* Make regs_set an empty set. */ 80818334Speter 80918334Speter n_regs_set = 0; 81018334Speter 81118334Speter if (code == INSN || code == CALL_INSN || code == JUMP_INSN) 81218334Speter { 81318334Speter 81418334Speter#if 0 81518334Speter int i = 0; 81618334Speter for (link = REG_NOTES (insn); 81718334Speter link && i < NUM_NO_CONFLICT_PAIRS; 81818334Speter link = XEXP (link, 1)) 81918334Speter if (REG_NOTE_KIND (link) == REG_NO_CONFLICT) 82018334Speter { 82118334Speter no_conflict_pairs[i].allocno1 82218334Speter = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))]; 82318334Speter no_conflict_pairs[i].allocno2 82418334Speter = reg_allocno[REGNO (XEXP (link, 0))]; 82518334Speter i++; 82618334Speter } 82718334Speter#endif /* 0 */ 82818334Speter 82918334Speter /* Mark any registers clobbered by INSN as live, 83018334Speter so they conflict with the inputs. */ 83118334Speter 83290075Sobrien note_stores (PATTERN (insn), mark_reg_clobber, NULL); 83318334Speter 83418334Speter /* Mark any registers dead after INSN as dead now. */ 83518334Speter 83618334Speter for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 83718334Speter if (REG_NOTE_KIND (link) == REG_DEAD) 83818334Speter mark_reg_death (XEXP (link, 0)); 83918334Speter 84018334Speter /* Mark any registers set in INSN as live, 84118334Speter and mark them as conflicting with all other live regs. 84218334Speter Clobbers are processed again, so they conflict with 84318334Speter the registers that are set. */ 84418334Speter 84590075Sobrien note_stores (PATTERN (insn), mark_reg_store, NULL); 84618334Speter 84718334Speter#ifdef AUTO_INC_DEC 84818334Speter for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 84918334Speter if (REG_NOTE_KIND (link) == REG_INC) 85090075Sobrien mark_reg_store (XEXP (link, 0), NULL_RTX, NULL); 85118334Speter#endif 85218334Speter 85318334Speter /* If INSN has multiple outputs, then any reg that dies here 85418334Speter and is used inside of an output 85552284Sobrien must conflict with the other outputs. 85618334Speter 85752284Sobrien It is unsafe to use !single_set here since it will ignore an 85852284Sobrien unused output. Just because an output is unused does not mean 85952284Sobrien the compiler can assume the side effect will not occur. 86052284Sobrien Consider if REG appears in the address of an output and we 86152284Sobrien reload the output. If we allocate REG to the same hard 86252284Sobrien register as an unused output we could set the hard register 86352284Sobrien before the output reload insn. */ 86452284Sobrien if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn)) 86518334Speter for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 86618334Speter if (REG_NOTE_KIND (link) == REG_DEAD) 86718334Speter { 86818334Speter int used_in_output = 0; 86918334Speter int i; 87018334Speter rtx reg = XEXP (link, 0); 87118334Speter 87218334Speter for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) 87318334Speter { 87418334Speter rtx set = XVECEXP (PATTERN (insn), 0, i); 87518334Speter if (GET_CODE (set) == SET 876169689Skan && !REG_P (SET_DEST (set)) 87718334Speter && !rtx_equal_p (reg, SET_DEST (set)) 87818334Speter && reg_overlap_mentioned_p (reg, SET_DEST (set))) 87918334Speter used_in_output = 1; 88018334Speter } 88118334Speter if (used_in_output) 88218334Speter mark_reg_conflicts (reg); 88318334Speter } 88418334Speter 88518334Speter /* Mark any registers set in INSN and then never used. */ 88618334Speter 88790075Sobrien while (n_regs_set-- > 0) 88890075Sobrien { 88990075Sobrien rtx note = find_regno_note (insn, REG_UNUSED, 89090075Sobrien REGNO (regs_set[n_regs_set])); 89190075Sobrien if (note) 89290075Sobrien mark_reg_death (XEXP (note, 0)); 89390075Sobrien } 89418334Speter } 89518334Speter 896132718Skan if (insn == BB_END (b)) 89718334Speter break; 89818334Speter insn = NEXT_INSN (insn); 89918334Speter } 90018334Speter } 90190075Sobrien 90290075Sobrien /* Clean up. */ 90390075Sobrien free (block_start_allocnos); 90490075Sobrien free (regs_set); 90518334Speter} 90618334Speter/* Expand the preference information by looking for cases where one allocno 90718334Speter dies in an insn that sets an allocno. If those two allocnos don't conflict, 90818334Speter merge any preferences between those allocnos. */ 90918334Speter 91018334Speterstatic void 911132718Skanexpand_preferences (void) 91218334Speter{ 91318334Speter rtx insn; 91418334Speter rtx link; 91518334Speter rtx set; 91618334Speter 91718334Speter /* We only try to handle the most common cases here. Most of the cases 91818334Speter where this wins are reg-reg copies. */ 91918334Speter 92018334Speter for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 92190075Sobrien if (INSN_P (insn) 92218334Speter && (set = single_set (insn)) != 0 923169689Skan && REG_P (SET_DEST (set)) 92418334Speter && reg_allocno[REGNO (SET_DEST (set))] >= 0) 92518334Speter for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 92618334Speter if (REG_NOTE_KIND (link) == REG_DEAD 927169689Skan && REG_P (XEXP (link, 0)) 92818334Speter && reg_allocno[REGNO (XEXP (link, 0))] >= 0 92918334Speter && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))], 93090075Sobrien reg_allocno[REGNO (XEXP (link, 0))])) 93118334Speter { 93218334Speter int a1 = reg_allocno[REGNO (SET_DEST (set))]; 93318334Speter int a2 = reg_allocno[REGNO (XEXP (link, 0))]; 93418334Speter 93518334Speter if (XEXP (link, 0) == SET_SRC (set)) 93618334Speter { 93790075Sobrien IOR_HARD_REG_SET (allocno[a1].hard_reg_copy_preferences, 93890075Sobrien allocno[a2].hard_reg_copy_preferences); 93990075Sobrien IOR_HARD_REG_SET (allocno[a2].hard_reg_copy_preferences, 94090075Sobrien allocno[a1].hard_reg_copy_preferences); 94118334Speter } 94218334Speter 94390075Sobrien IOR_HARD_REG_SET (allocno[a1].hard_reg_preferences, 94490075Sobrien allocno[a2].hard_reg_preferences); 94590075Sobrien IOR_HARD_REG_SET (allocno[a2].hard_reg_preferences, 94690075Sobrien allocno[a1].hard_reg_preferences); 94790075Sobrien IOR_HARD_REG_SET (allocno[a1].hard_reg_full_preferences, 94890075Sobrien allocno[a2].hard_reg_full_preferences); 94990075Sobrien IOR_HARD_REG_SET (allocno[a2].hard_reg_full_preferences, 95090075Sobrien allocno[a1].hard_reg_full_preferences); 95118334Speter } 95218334Speter} 95318334Speter 95418334Speter/* Prune the preferences for global registers to exclude registers that cannot 95518334Speter be used. 956117395Skan 95718334Speter Compute `regs_someone_prefers', which is a bitmask of the hard registers 95818334Speter that are preferred by conflicting registers of lower priority. If possible, 95918334Speter we will avoid using these registers. */ 960117395Skan 96118334Speterstatic void 962132718Skanprune_preferences (void) 96318334Speter{ 96490075Sobrien int i; 96590075Sobrien int num; 966169689Skan int *allocno_to_order = XNEWVEC (int, max_allocno); 967117395Skan 96818334Speter /* Scan least most important to most important. 96918334Speter For each allocno, remove from preferences registers that cannot be used, 97018334Speter either because of conflicts or register type. Then compute all registers 97118334Speter preferred by each lower-priority register that conflicts. */ 97218334Speter 97318334Speter for (i = max_allocno - 1; i >= 0; i--) 97418334Speter { 97518334Speter HARD_REG_SET temp; 97618334Speter 97790075Sobrien num = allocno_order[i]; 97890075Sobrien allocno_to_order[num] = i; 97990075Sobrien COPY_HARD_REG_SET (temp, allocno[num].hard_reg_conflicts); 98018334Speter 98190075Sobrien if (allocno[num].calls_crossed == 0) 98218334Speter IOR_HARD_REG_SET (temp, fixed_reg_set); 98318334Speter else 98418334Speter IOR_HARD_REG_SET (temp, call_used_reg_set); 98518334Speter 98618334Speter IOR_COMPL_HARD_REG_SET 98718334Speter (temp, 98890075Sobrien reg_class_contents[(int) reg_preferred_class (allocno[num].reg)]); 98918334Speter 99090075Sobrien AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, temp); 99190075Sobrien AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, temp); 99290075Sobrien AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_full_preferences, temp); 99390075Sobrien } 99418334Speter 99590075Sobrien for (i = max_allocno - 1; i >= 0; i--) 99690075Sobrien { 99718334Speter /* Merge in the preferences of lower-priority registers (they have 99818334Speter already been pruned). If we also prefer some of those registers, 99918334Speter don't exclude them unless we are of a smaller size (in which case 100018334Speter we want to give the lower-priority allocno the first chance for 100118334Speter these registers). */ 100290075Sobrien HARD_REG_SET temp, temp2; 100390075Sobrien int allocno2; 100490075Sobrien 100590075Sobrien num = allocno_order[i]; 100690075Sobrien 100790075Sobrien CLEAR_HARD_REG_SET (temp); 100890075Sobrien CLEAR_HARD_REG_SET (temp2); 100990075Sobrien 101090075Sobrien EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + num * allocno_row_words, 101190075Sobrien allocno2, 101290075Sobrien { 101390075Sobrien if (allocno_to_order[allocno2] > i) 101490075Sobrien { 101590075Sobrien if (allocno[allocno2].size <= allocno[num].size) 101690075Sobrien IOR_HARD_REG_SET (temp, 101790075Sobrien allocno[allocno2].hard_reg_full_preferences); 101890075Sobrien else 101990075Sobrien IOR_HARD_REG_SET (temp2, 102090075Sobrien allocno[allocno2].hard_reg_full_preferences); 102190075Sobrien } 102290075Sobrien }); 102390075Sobrien 102490075Sobrien AND_COMPL_HARD_REG_SET (temp, allocno[num].hard_reg_full_preferences); 102590075Sobrien IOR_HARD_REG_SET (temp, temp2); 102690075Sobrien COPY_HARD_REG_SET (allocno[num].regs_someone_prefers, temp); 102718334Speter } 102890075Sobrien free (allocno_to_order); 102918334Speter} 103018334Speter 103190075Sobrien/* Assign a hard register to allocno NUM; look for one that is the beginning 103218334Speter of a long enough stretch of hard regs none of which conflicts with ALLOCNO. 103318334Speter The registers marked in PREFREGS are tried first. 103418334Speter 1035117395Skan LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot 103618334Speter be used for this allocation. 103718334Speter 103818334Speter If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg. 103918334Speter Otherwise ignore that preferred class and use the alternate class. 104018334Speter 104118334Speter If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that 104218334Speter will have to be saved and restored at calls. 104318334Speter 104418334Speter RETRYING is nonzero if this is called from retry_global_alloc. 104518334Speter 104618334Speter If we find one, record it in reg_renumber. 104718334Speter If not, do nothing. */ 104818334Speter 104918334Speterstatic void 1050132718Skanfind_reg (int num, HARD_REG_SET losers, int alt_regs_p, int accept_call_clobbered, int retrying) 105118334Speter{ 105290075Sobrien int i, best_reg, pass; 1053117395Skan HARD_REG_SET used, used1, used2; 105418334Speter 105518334Speter enum reg_class class = (alt_regs_p 105690075Sobrien ? reg_alternate_class (allocno[num].reg) 105790075Sobrien : reg_preferred_class (allocno[num].reg)); 105890075Sobrien enum machine_mode mode = PSEUDO_REGNO_MODE (allocno[num].reg); 105918334Speter 106018334Speter if (accept_call_clobbered) 106118334Speter COPY_HARD_REG_SET (used1, call_fixed_reg_set); 106290075Sobrien else if (allocno[num].calls_crossed == 0) 106318334Speter COPY_HARD_REG_SET (used1, fixed_reg_set); 106418334Speter else 106518334Speter COPY_HARD_REG_SET (used1, call_used_reg_set); 106618334Speter 106718334Speter /* Some registers should not be allocated in global-alloc. */ 106818334Speter IOR_HARD_REG_SET (used1, no_global_alloc_regs); 106918334Speter if (losers) 107018334Speter IOR_HARD_REG_SET (used1, losers); 107118334Speter 107218334Speter IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]); 107318334Speter COPY_HARD_REG_SET (used2, used1); 107418334Speter 107590075Sobrien IOR_HARD_REG_SET (used1, allocno[num].hard_reg_conflicts); 107618334Speter 1077117395Skan#ifdef CANNOT_CHANGE_MODE_CLASS 1078117395Skan cannot_change_mode_set_regs (&used1, mode, allocno[num].reg); 107918334Speter#endif 108018334Speter 108118334Speter /* Try each hard reg to see if it fits. Do this in two passes. 108218334Speter In the first pass, skip registers that are preferred by some other pseudo 108318334Speter to give it a better chance of getting one of those registers. Only if 108418334Speter we can't get a register when excluding those do we take one of them. 108518334Speter However, we never allocate a register for the first time in pass 0. */ 108618334Speter 108718334Speter COPY_HARD_REG_SET (used, used1); 108818334Speter IOR_COMPL_HARD_REG_SET (used, regs_used_so_far); 108990075Sobrien IOR_HARD_REG_SET (used, allocno[num].regs_someone_prefers); 1090117395Skan 109118334Speter best_reg = -1; 109218334Speter for (i = FIRST_PSEUDO_REGISTER, pass = 0; 109318334Speter pass <= 1 && i >= FIRST_PSEUDO_REGISTER; 109418334Speter pass++) 109518334Speter { 109618334Speter if (pass == 1) 109718334Speter COPY_HARD_REG_SET (used, used1); 109818334Speter for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 109918334Speter { 110018334Speter#ifdef REG_ALLOC_ORDER 110118334Speter int regno = reg_alloc_order[i]; 110218334Speter#else 110318334Speter int regno = i; 110418334Speter#endif 110518334Speter if (! TEST_HARD_REG_BIT (used, regno) 110652284Sobrien && HARD_REGNO_MODE_OK (regno, mode) 110790075Sobrien && (allocno[num].calls_crossed == 0 110852284Sobrien || accept_call_clobbered 110952284Sobrien || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))) 111018334Speter { 111190075Sobrien int j; 1112169689Skan int lim = regno + hard_regno_nregs[regno][mode]; 111318334Speter for (j = regno + 1; 111418334Speter (j < lim 111518334Speter && ! TEST_HARD_REG_BIT (used, j)); 111618334Speter j++); 111718334Speter if (j == lim) 111818334Speter { 111918334Speter best_reg = regno; 112018334Speter break; 112118334Speter } 112218334Speter#ifndef REG_ALLOC_ORDER 112318334Speter i = j; /* Skip starting points we know will lose */ 112418334Speter#endif 112518334Speter } 112618334Speter } 112718334Speter } 112818334Speter 112918334Speter /* See if there is a preferred register with the same class as the register 113018334Speter we allocated above. Making this restriction prevents register 113118334Speter preferencing from creating worse register allocation. 113218334Speter 113318334Speter Remove from the preferred registers and conflicting registers. Note that 113418334Speter additional conflicts may have been added after `prune_preferences' was 1135117395Skan called. 113618334Speter 113718334Speter First do this for those register with copy preferences, then all 113818334Speter preferred registers. */ 113918334Speter 114090075Sobrien AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, used); 114190075Sobrien GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_copy_preferences, 114218334Speter reg_class_contents[(int) NO_REGS], no_copy_prefs); 114318334Speter 114418334Speter if (best_reg >= 0) 114518334Speter { 114618334Speter for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 114790075Sobrien if (TEST_HARD_REG_BIT (allocno[num].hard_reg_copy_preferences, i) 114818334Speter && HARD_REGNO_MODE_OK (i, mode) 114990075Sobrien && (allocno[num].calls_crossed == 0 115090075Sobrien || accept_call_clobbered 115190075Sobrien || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode)) 115218334Speter && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg) 115318334Speter || reg_class_subset_p (REGNO_REG_CLASS (i), 115418334Speter REGNO_REG_CLASS (best_reg)) 115518334Speter || reg_class_subset_p (REGNO_REG_CLASS (best_reg), 115618334Speter REGNO_REG_CLASS (i)))) 115718334Speter { 115890075Sobrien int j; 1159169689Skan int lim = i + hard_regno_nregs[i][mode]; 116018334Speter for (j = i + 1; 116118334Speter (j < lim 116218334Speter && ! TEST_HARD_REG_BIT (used, j) 116318334Speter && (REGNO_REG_CLASS (j) 1164132718Skan == REGNO_REG_CLASS (best_reg + (j - i)) 116518334Speter || reg_class_subset_p (REGNO_REG_CLASS (j), 116618334Speter REGNO_REG_CLASS (best_reg + (j - i))) 116718334Speter || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)), 116818334Speter REGNO_REG_CLASS (j)))); 116918334Speter j++); 117018334Speter if (j == lim) 117118334Speter { 117218334Speter best_reg = i; 117318334Speter goto no_prefs; 117418334Speter } 117518334Speter } 117618334Speter } 117718334Speter no_copy_prefs: 117818334Speter 117990075Sobrien AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, used); 118090075Sobrien GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_preferences, 118118334Speter reg_class_contents[(int) NO_REGS], no_prefs); 118218334Speter 118318334Speter if (best_reg >= 0) 118418334Speter { 118518334Speter for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 118690075Sobrien if (TEST_HARD_REG_BIT (allocno[num].hard_reg_preferences, i) 118718334Speter && HARD_REGNO_MODE_OK (i, mode) 118890075Sobrien && (allocno[num].calls_crossed == 0 118990075Sobrien || accept_call_clobbered 119090075Sobrien || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode)) 119118334Speter && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg) 119218334Speter || reg_class_subset_p (REGNO_REG_CLASS (i), 119318334Speter REGNO_REG_CLASS (best_reg)) 119418334Speter || reg_class_subset_p (REGNO_REG_CLASS (best_reg), 119518334Speter REGNO_REG_CLASS (i)))) 119618334Speter { 119790075Sobrien int j; 1198169689Skan int lim = i + hard_regno_nregs[i][mode]; 119918334Speter for (j = i + 1; 120018334Speter (j < lim 120118334Speter && ! TEST_HARD_REG_BIT (used, j) 120218334Speter && (REGNO_REG_CLASS (j) 1203132718Skan == REGNO_REG_CLASS (best_reg + (j - i)) 120418334Speter || reg_class_subset_p (REGNO_REG_CLASS (j), 120518334Speter REGNO_REG_CLASS (best_reg + (j - i))) 120618334Speter || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)), 120718334Speter REGNO_REG_CLASS (j)))); 120818334Speter j++); 120918334Speter if (j == lim) 121018334Speter { 121118334Speter best_reg = i; 121218334Speter break; 121318334Speter } 121418334Speter } 121518334Speter } 121618334Speter no_prefs: 121718334Speter 1218117395Skan /* If we haven't succeeded yet, try with caller-saves. 121918334Speter We need not check to see if the current function has nonlocal 122018334Speter labels because we don't put any pseudos that are live over calls in 122118334Speter registers in that case. */ 122218334Speter 122318334Speter if (flag_caller_saves && best_reg < 0) 122418334Speter { 122518334Speter /* Did not find a register. If it would be profitable to 122618334Speter allocate a call-clobbered register and save and restore it 1227161651Skan around calls, do that. Don't do this if it crosses any calls 1228161651Skan that might throw. */ 122918334Speter if (! accept_call_clobbered 123090075Sobrien && allocno[num].calls_crossed != 0 1231161651Skan && allocno[num].throwing_calls_crossed == 0 123290075Sobrien && CALLER_SAVE_PROFITABLE (allocno[num].n_refs, 123390075Sobrien allocno[num].calls_crossed)) 123418334Speter { 123550397Sobrien HARD_REG_SET new_losers; 123650397Sobrien if (! losers) 123750397Sobrien CLEAR_HARD_REG_SET (new_losers); 123850397Sobrien else 123950397Sobrien COPY_HARD_REG_SET (new_losers, losers); 1240117395Skan 124150397Sobrien IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set); 124290075Sobrien find_reg (num, new_losers, alt_regs_p, 1, retrying); 124390075Sobrien if (reg_renumber[allocno[num].reg] >= 0) 124418334Speter { 124518334Speter caller_save_needed = 1; 124618334Speter return; 124718334Speter } 124818334Speter } 124918334Speter } 125018334Speter 125118334Speter /* If we haven't succeeded yet, 125218334Speter see if some hard reg that conflicts with us 125318334Speter was utilized poorly by local-alloc. 125418334Speter If so, kick out the regs that were put there by local-alloc 125518334Speter so we can use it instead. */ 125618334Speter if (best_reg < 0 && !retrying 125718334Speter /* Let's not bother with multi-reg allocnos. */ 1258169689Skan && allocno[num].size == 1 1259169689Skan && REG_BASIC_BLOCK (allocno[num].reg) == REG_BLOCK_GLOBAL) 126018334Speter { 126118334Speter /* Count from the end, to find the least-used ones first. */ 126218334Speter for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--) 126318334Speter { 126418334Speter#ifdef REG_ALLOC_ORDER 126518334Speter int regno = reg_alloc_order[i]; 126618334Speter#else 126718334Speter int regno = i; 126818334Speter#endif 126918334Speter 127018334Speter if (local_reg_n_refs[regno] != 0 127118334Speter /* Don't use a reg no good for this pseudo. */ 127218334Speter && ! TEST_HARD_REG_BIT (used2, regno) 127318334Speter && HARD_REGNO_MODE_OK (regno, mode) 1274117395Skan /* The code below assumes that we need only a single 1275117395Skan register, but the check of allocno[num].size above 1276117395Skan was not enough. Sometimes we need more than one 1277117395Skan register for a single-word value. */ 1278169689Skan && hard_regno_nregs[regno][mode] == 1 127990075Sobrien && (allocno[num].calls_crossed == 0 128090075Sobrien || accept_call_clobbered 128190075Sobrien || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)) 1282117395Skan#ifdef CANNOT_CHANGE_MODE_CLASS 1283117395Skan && ! invalid_mode_change_p (regno, REGNO_REG_CLASS (regno), 1284117395Skan mode) 128518334Speter#endif 1286110611Skan#ifdef STACK_REGS 1287132718Skan && (!allocno[num].no_stack_reg 1288132718Skan || regno < FIRST_STACK_REG || regno > LAST_STACK_REG) 1289110611Skan#endif 129018334Speter ) 129118334Speter { 129218334Speter /* We explicitly evaluate the divide results into temporary 129318334Speter variables so as to avoid excess precision problems that occur 129490075Sobrien on an i386-unknown-sysv4.2 (unixware) host. */ 1295117395Skan 1296169689Skan double tmp1 = ((double) local_reg_freq[regno] * local_reg_n_refs[regno] 129718334Speter / local_reg_live_length[regno]); 1298169689Skan double tmp2 = ((double) allocno[num].freq * allocno[num].n_refs 129990075Sobrien / allocno[num].live_length); 130018334Speter 130118334Speter if (tmp1 < tmp2) 130218334Speter { 130318334Speter /* Hard reg REGNO was used less in total by local regs 130418334Speter than it would be used by this one allocno! */ 130518334Speter int k; 1306169689Skan if (dump_file) 1307169689Skan { 1308169689Skan fprintf (dump_file, "Regno %d better for global %d, ", 1309169689Skan regno, allocno[num].reg); 1310169689Skan fprintf (dump_file, "fr:%d, ll:%d, nr:%d ", 1311169689Skan allocno[num].freq, allocno[num].live_length, 1312169689Skan allocno[num].n_refs); 1313169689Skan fprintf (dump_file, "(was: fr:%d, ll:%d, nr:%d)\n", 1314169689Skan local_reg_freq[regno], 1315169689Skan local_reg_live_length[regno], 1316169689Skan local_reg_n_refs[regno]); 1317169689Skan } 1318169689Skan 131918334Speter for (k = 0; k < max_regno; k++) 132018334Speter if (reg_renumber[k] >= 0) 132118334Speter { 132218334Speter int r = reg_renumber[k]; 132318334Speter int endregno 1324169689Skan = r + hard_regno_nregs[r][PSEUDO_REGNO_MODE (k)]; 132518334Speter 132618334Speter if (regno >= r && regno < endregno) 1327169689Skan { 1328169689Skan if (dump_file) 1329169689Skan fprintf (dump_file, 1330169689Skan "Local Reg %d now on stack\n", k); 1331169689Skan reg_renumber[k] = -1; 1332169689Skan } 133318334Speter } 133418334Speter 133518334Speter best_reg = regno; 133618334Speter break; 133718334Speter } 133818334Speter } 133918334Speter } 134018334Speter } 134118334Speter 134218334Speter /* Did we find a register? */ 134318334Speter 134418334Speter if (best_reg >= 0) 134518334Speter { 134690075Sobrien int lim, j; 134718334Speter HARD_REG_SET this_reg; 134818334Speter 134918334Speter /* Yes. Record it as the hard register of this pseudo-reg. */ 135090075Sobrien reg_renumber[allocno[num].reg] = best_reg; 135118334Speter /* Also of any pseudo-regs that share with it. */ 135290075Sobrien if (reg_may_share[allocno[num].reg]) 135318334Speter for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++) 135490075Sobrien if (reg_allocno[j] == num) 135518334Speter reg_renumber[j] = best_reg; 135618334Speter 135718334Speter /* Make a set of the hard regs being allocated. */ 135818334Speter CLEAR_HARD_REG_SET (this_reg); 1359169689Skan lim = best_reg + hard_regno_nregs[best_reg][mode]; 136018334Speter for (j = best_reg; j < lim; j++) 136118334Speter { 136218334Speter SET_HARD_REG_BIT (this_reg, j); 136318334Speter SET_HARD_REG_BIT (regs_used_so_far, j); 136418334Speter /* This is no longer a reg used just by local regs. */ 136518334Speter local_reg_n_refs[j] = 0; 136690075Sobrien local_reg_freq[j] = 0; 136718334Speter } 136818334Speter /* For each other pseudo-reg conflicting with this one, 136918334Speter mark it as conflicting with the hard regs this one occupies. */ 137090075Sobrien lim = num; 137190075Sobrien EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + lim * allocno_row_words, j, 137290075Sobrien { 137390075Sobrien IOR_HARD_REG_SET (allocno[j].hard_reg_conflicts, this_reg); 137490075Sobrien }); 137518334Speter } 137618334Speter} 137718334Speter 137818334Speter/* Called from `reload' to look for a hard reg to put pseudo reg REGNO in. 137918334Speter Perhaps it had previously seemed not worth a hard reg, 138018334Speter or perhaps its old hard reg has been commandeered for reloads. 138118334Speter FORBIDDEN_REGS indicates certain hard regs that may not be used, even if 138218334Speter they do not appear to be allocated. 138318334Speter If FORBIDDEN_REGS is zero, no regs are forbidden. */ 138418334Speter 138518334Spetervoid 1386132718Skanretry_global_alloc (int regno, HARD_REG_SET forbidden_regs) 138718334Speter{ 138890075Sobrien int alloc_no = reg_allocno[regno]; 138990075Sobrien if (alloc_no >= 0) 139018334Speter { 139118334Speter /* If we have more than one register class, 139218334Speter first try allocating in the class that is cheapest 139318334Speter for this pseudo-reg. If that fails, try any reg. */ 139418334Speter if (N_REG_CLASSES > 1) 139590075Sobrien find_reg (alloc_no, forbidden_regs, 0, 0, 1); 139618334Speter if (reg_renumber[regno] < 0 139718334Speter && reg_alternate_class (regno) != NO_REGS) 139890075Sobrien find_reg (alloc_no, forbidden_regs, 1, 0, 1); 139918334Speter 140018334Speter /* If we found a register, modify the RTL for the register to 140118334Speter show the hard register, and mark that register live. */ 140218334Speter if (reg_renumber[regno] >= 0) 140318334Speter { 140418334Speter REGNO (regno_reg_rtx[regno]) = reg_renumber[regno]; 140518334Speter mark_home_live (regno); 140618334Speter } 140718334Speter } 140818334Speter} 140918334Speter 141018334Speter/* Record a conflict between register REGNO 141118334Speter and everything currently live. 141218334Speter REGNO must not be a pseudo reg that was allocated 141318334Speter by local_alloc; such numbers must be translated through 141418334Speter reg_renumber before calling here. */ 141518334Speter 141618334Speterstatic void 1417132718Skanrecord_one_conflict (int regno) 141818334Speter{ 141990075Sobrien int j; 142018334Speter 142118334Speter if (regno < FIRST_PSEUDO_REGISTER) 142218334Speter /* When a hard register becomes live, 142318334Speter record conflicts with live pseudo regs. */ 142490075Sobrien EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, j, 142518334Speter { 142690075Sobrien SET_HARD_REG_BIT (allocno[j].hard_reg_conflicts, regno); 142790075Sobrien }); 142818334Speter else 142918334Speter /* When a pseudo-register becomes live, 143018334Speter record conflicts first with hard regs, 143118334Speter then with other pseudo regs. */ 143218334Speter { 143390075Sobrien int ialloc = reg_allocno[regno]; 143490075Sobrien int ialloc_prod = ialloc * allocno_row_words; 143590075Sobrien 143690075Sobrien IOR_HARD_REG_SET (allocno[ialloc].hard_reg_conflicts, hard_regs_live); 143718334Speter for (j = allocno_row_words - 1; j >= 0; j--) 1438169689Skan conflicts[ialloc_prod + j] |= allocnos_live[j]; 143918334Speter } 144018334Speter} 144118334Speter 144218334Speter/* Record all allocnos currently live as conflicting 144390075Sobrien with all hard regs currently live. 144490075Sobrien 144518334Speter ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that 144618334Speter are currently live. Their bits are also flagged in allocnos_live. */ 144718334Speter 144818334Speterstatic void 1449132718Skanrecord_conflicts (int *allocno_vec, int len) 145018334Speter{ 145118334Speter while (--len >= 0) 1452132718Skan IOR_HARD_REG_SET (allocno[allocno_vec[len]].hard_reg_conflicts, 1453132718Skan hard_regs_live); 145418334Speter} 145590075Sobrien 145690075Sobrien/* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */ 145790075Sobrienstatic void 1458132718Skanmirror_conflicts (void) 145990075Sobrien{ 146090075Sobrien int i, j; 146190075Sobrien int rw = allocno_row_words; 146290075Sobrien int rwb = rw * INT_BITS; 146390075Sobrien INT_TYPE *p = conflicts; 146490075Sobrien INT_TYPE *q0 = conflicts, *q1, *q2; 146590075Sobrien unsigned INT_TYPE mask; 146690075Sobrien 146790075Sobrien for (i = max_allocno - 1, mask = 1; i >= 0; i--, mask <<= 1) 146890075Sobrien { 146990075Sobrien if (! mask) 147090075Sobrien { 147190075Sobrien mask = 1; 147290075Sobrien q0++; 147390075Sobrien } 147490075Sobrien for (j = allocno_row_words - 1, q1 = q0; j >= 0; j--, q1 += rwb) 147590075Sobrien { 147690075Sobrien unsigned INT_TYPE word; 147790075Sobrien 147890075Sobrien for (word = (unsigned INT_TYPE) *p++, q2 = q1; word; 147990075Sobrien word >>= 1, q2 += rw) 148090075Sobrien { 148190075Sobrien if (word & 1) 148290075Sobrien *q2 |= mask; 148390075Sobrien } 148490075Sobrien } 148590075Sobrien } 148690075Sobrien} 148718334Speter 148818334Speter/* Handle the case where REG is set by the insn being scanned, 148918334Speter during the forward scan to accumulate conflicts. 149018334Speter Store a 1 in regs_live or allocnos_live for this register, record how many 149118334Speter consecutive hardware registers it actually needs, 149218334Speter and record a conflict with all other registers already live. 149318334Speter 149418334Speter Note that even if REG does not remain alive after this insn, 149518334Speter we must mark it here as live, to ensure a conflict between 149618334Speter REG and any other regs set in this insn that really do live. 149718334Speter This is because those other regs could be considered after this. 149818334Speter 149918334Speter REG might actually be something other than a register; 150018334Speter if so, we do nothing. 150118334Speter 150218334Speter SETTER is 0 if this register was modified by an auto-increment (i.e., 150352284Sobrien a REG_INC note was found for it). */ 150418334Speter 150518334Speterstatic void 1506132718Skanmark_reg_store (rtx reg, rtx setter, void *data ATTRIBUTE_UNUSED) 150718334Speter{ 150890075Sobrien int regno; 150918334Speter 151018334Speter if (GET_CODE (reg) == SUBREG) 151190075Sobrien reg = SUBREG_REG (reg); 151218334Speter 1513169689Skan if (!REG_P (reg)) 151418334Speter return; 151518334Speter 151618334Speter regs_set[n_regs_set++] = reg; 151718334Speter 151852284Sobrien if (setter && GET_CODE (setter) != CLOBBER) 151918334Speter set_preference (reg, SET_SRC (setter)); 152018334Speter 152118334Speter regno = REGNO (reg); 152218334Speter 152318334Speter /* Either this is one of the max_allocno pseudo regs not allocated, 152418334Speter or it is or has a hardware reg. First handle the pseudo-regs. */ 152518334Speter if (regno >= FIRST_PSEUDO_REGISTER) 152618334Speter { 152718334Speter if (reg_allocno[regno] >= 0) 152818334Speter { 152918334Speter SET_ALLOCNO_LIVE (reg_allocno[regno]); 153018334Speter record_one_conflict (regno); 153118334Speter } 153218334Speter } 153352284Sobrien 153452284Sobrien if (reg_renumber[regno] >= 0) 153590075Sobrien regno = reg_renumber[regno]; 153652284Sobrien 153718334Speter /* Handle hardware regs (and pseudos allocated to hard regs). */ 153852284Sobrien if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno]) 153918334Speter { 1540169689Skan int last = regno + hard_regno_nregs[regno][GET_MODE (reg)]; 154118334Speter while (regno < last) 154218334Speter { 154318334Speter record_one_conflict (regno); 154418334Speter SET_HARD_REG_BIT (hard_regs_live, regno); 154518334Speter regno++; 154618334Speter } 154718334Speter } 154818334Speter} 154918334Speter 1550169689Skan/* Like mark_reg_store except notice just CLOBBERs; ignore SETs. */ 155118334Speter 155218334Speterstatic void 1553169689Skanmark_reg_clobber (rtx reg, rtx setter, void *data) 155418334Speter{ 155552284Sobrien if (GET_CODE (setter) == CLOBBER) 155690075Sobrien mark_reg_store (reg, setter, data); 155718334Speter} 155818334Speter 155918334Speter/* Record that REG has conflicts with all the regs currently live. 156018334Speter Do not mark REG itself as live. */ 156118334Speter 156218334Speterstatic void 1563132718Skanmark_reg_conflicts (rtx reg) 156418334Speter{ 156590075Sobrien int regno; 156618334Speter 156718334Speter if (GET_CODE (reg) == SUBREG) 156818334Speter reg = SUBREG_REG (reg); 156918334Speter 1570169689Skan if (!REG_P (reg)) 157118334Speter return; 157218334Speter 157318334Speter regno = REGNO (reg); 157418334Speter 157518334Speter /* Either this is one of the max_allocno pseudo regs not allocated, 157618334Speter or it is or has a hardware reg. First handle the pseudo-regs. */ 157718334Speter if (regno >= FIRST_PSEUDO_REGISTER) 157818334Speter { 157918334Speter if (reg_allocno[regno] >= 0) 158018334Speter record_one_conflict (regno); 158118334Speter } 158252284Sobrien 158352284Sobrien if (reg_renumber[regno] >= 0) 158452284Sobrien regno = reg_renumber[regno]; 158552284Sobrien 158618334Speter /* Handle hardware regs (and pseudos allocated to hard regs). */ 158752284Sobrien if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno]) 158818334Speter { 1589169689Skan int last = regno + hard_regno_nregs[regno][GET_MODE (reg)]; 159018334Speter while (regno < last) 159118334Speter { 159218334Speter record_one_conflict (regno); 159318334Speter regno++; 159418334Speter } 159518334Speter } 159618334Speter} 159718334Speter 159818334Speter/* Mark REG as being dead (following the insn being scanned now). 159918334Speter Store a 0 in regs_live or allocnos_live for this register. */ 160018334Speter 160118334Speterstatic void 1602132718Skanmark_reg_death (rtx reg) 160318334Speter{ 160490075Sobrien int regno = REGNO (reg); 160518334Speter 160618334Speter /* Either this is one of the max_allocno pseudo regs not allocated, 160718334Speter or it is a hardware reg. First handle the pseudo-regs. */ 160818334Speter if (regno >= FIRST_PSEUDO_REGISTER) 160918334Speter { 161018334Speter if (reg_allocno[regno] >= 0) 161118334Speter CLEAR_ALLOCNO_LIVE (reg_allocno[regno]); 161218334Speter } 161352284Sobrien 161452284Sobrien /* For pseudo reg, see if it has been assigned a hardware reg. */ 161552284Sobrien if (reg_renumber[regno] >= 0) 161652284Sobrien regno = reg_renumber[regno]; 161752284Sobrien 161818334Speter /* Handle hardware regs (and pseudos allocated to hard regs). */ 161952284Sobrien if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno]) 162018334Speter { 162118334Speter /* Pseudo regs already assigned hardware regs are treated 162218334Speter almost the same as explicit hardware regs. */ 1623169689Skan int last = regno + hard_regno_nregs[regno][GET_MODE (reg)]; 162418334Speter while (regno < last) 162518334Speter { 162618334Speter CLEAR_HARD_REG_BIT (hard_regs_live, regno); 162718334Speter regno++; 162818334Speter } 162918334Speter } 163018334Speter} 163118334Speter 163218334Speter/* Mark hard reg REGNO as currently live, assuming machine mode MODE 163318334Speter for the value stored in it. MODE determines how many consecutive 163418334Speter registers are actually in use. Do not record conflicts; 163518334Speter it is assumed that the caller will do that. */ 163618334Speter 163718334Speterstatic void 1638132718Skanmark_reg_live_nc (int regno, enum machine_mode mode) 163918334Speter{ 1640169689Skan int last = regno + hard_regno_nregs[regno][mode]; 164118334Speter while (regno < last) 164218334Speter { 164318334Speter SET_HARD_REG_BIT (hard_regs_live, regno); 164418334Speter regno++; 164518334Speter } 164618334Speter} 164718334Speter 164818334Speter/* Try to set a preference for an allocno to a hard register. 164918334Speter We are passed DEST and SRC which are the operands of a SET. It is known 165018334Speter that SRC is a register. If SRC or the first operand of SRC is a register, 165118334Speter try to set a preference. If one of the two is a hard register and the other 165218334Speter is a pseudo-register, mark the preference. 1653117395Skan 165418334Speter Note that we are not as aggressive as local-alloc in trying to tie a 165518334Speter pseudo-register to a hard register. */ 165618334Speter 165718334Speterstatic void 1658132718Skanset_preference (rtx dest, rtx src) 165918334Speter{ 166090075Sobrien unsigned int src_regno, dest_regno; 166118334Speter /* Amount to add to the hard regno for SRC, or subtract from that for DEST, 166218334Speter to compensate for subregs in SRC or DEST. */ 166318334Speter int offset = 0; 166490075Sobrien unsigned int i; 166518334Speter int copy = 1; 166618334Speter 166718334Speter if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e') 166818334Speter src = XEXP (src, 0), copy = 0; 166918334Speter 167018334Speter /* Get the reg number for both SRC and DEST. 167118334Speter If neither is a reg, give up. */ 167218334Speter 1673169689Skan if (REG_P (src)) 167418334Speter src_regno = REGNO (src); 1675169689Skan else if (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))) 167618334Speter { 167718334Speter src_regno = REGNO (SUBREG_REG (src)); 167890075Sobrien 167990075Sobrien if (REGNO (SUBREG_REG (src)) < FIRST_PSEUDO_REGISTER) 168090075Sobrien offset += subreg_regno_offset (REGNO (SUBREG_REG (src)), 168190075Sobrien GET_MODE (SUBREG_REG (src)), 168290075Sobrien SUBREG_BYTE (src), 168390075Sobrien GET_MODE (src)); 168490075Sobrien else 168590075Sobrien offset += (SUBREG_BYTE (src) 168690075Sobrien / REGMODE_NATURAL_SIZE (GET_MODE (src))); 168718334Speter } 168818334Speter else 168918334Speter return; 169018334Speter 1691169689Skan if (REG_P (dest)) 169218334Speter dest_regno = REGNO (dest); 1693169689Skan else if (GET_CODE (dest) == SUBREG && REG_P (SUBREG_REG (dest))) 169418334Speter { 169518334Speter dest_regno = REGNO (SUBREG_REG (dest)); 169690075Sobrien 169790075Sobrien if (REGNO (SUBREG_REG (dest)) < FIRST_PSEUDO_REGISTER) 169890075Sobrien offset -= subreg_regno_offset (REGNO (SUBREG_REG (dest)), 169990075Sobrien GET_MODE (SUBREG_REG (dest)), 170090075Sobrien SUBREG_BYTE (dest), 170190075Sobrien GET_MODE (dest)); 170290075Sobrien else 170390075Sobrien offset -= (SUBREG_BYTE (dest) 170490075Sobrien / REGMODE_NATURAL_SIZE (GET_MODE (dest))); 170518334Speter } 170618334Speter else 170718334Speter return; 170818334Speter 170918334Speter /* Convert either or both to hard reg numbers. */ 171018334Speter 171118334Speter if (reg_renumber[src_regno] >= 0) 171218334Speter src_regno = reg_renumber[src_regno]; 171318334Speter 171418334Speter if (reg_renumber[dest_regno] >= 0) 171518334Speter dest_regno = reg_renumber[dest_regno]; 171618334Speter 171718334Speter /* Now if one is a hard reg and the other is a global pseudo 171818334Speter then give the other a preference. */ 171918334Speter 172018334Speter if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER 172118334Speter && reg_allocno[src_regno] >= 0) 172218334Speter { 172318334Speter dest_regno -= offset; 172490075Sobrien if (dest_regno < FIRST_PSEUDO_REGISTER) 172518334Speter { 172618334Speter if (copy) 172718334Speter SET_REGBIT (hard_reg_copy_preferences, 172818334Speter reg_allocno[src_regno], dest_regno); 172918334Speter 173018334Speter SET_REGBIT (hard_reg_preferences, 173118334Speter reg_allocno[src_regno], dest_regno); 173218334Speter for (i = dest_regno; 1733169689Skan i < dest_regno + hard_regno_nregs[dest_regno][GET_MODE (dest)]; 173418334Speter i++) 173518334Speter SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i); 173618334Speter } 173718334Speter } 173818334Speter 173918334Speter if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER 174018334Speter && reg_allocno[dest_regno] >= 0) 174118334Speter { 174218334Speter src_regno += offset; 174390075Sobrien if (src_regno < FIRST_PSEUDO_REGISTER) 174418334Speter { 174518334Speter if (copy) 174618334Speter SET_REGBIT (hard_reg_copy_preferences, 174718334Speter reg_allocno[dest_regno], src_regno); 174818334Speter 174918334Speter SET_REGBIT (hard_reg_preferences, 175018334Speter reg_allocno[dest_regno], src_regno); 175118334Speter for (i = src_regno; 1752169689Skan i < src_regno + hard_regno_nregs[src_regno][GET_MODE (src)]; 175318334Speter i++) 175418334Speter SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i); 175518334Speter } 175618334Speter } 175718334Speter} 175818334Speter 175918334Speter/* Indicate that hard register number FROM was eliminated and replaced with 176018334Speter an offset from hard register number TO. The status of hard registers live 176118334Speter at the start of a basic block is updated by replacing a use of FROM with 176218334Speter a use of TO. */ 176318334Speter 176418334Spetervoid 1765132718Skanmark_elimination (int from, int to) 176618334Speter{ 1767117395Skan basic_block bb; 176818334Speter 1769117395Skan FOR_EACH_BB (bb) 177052284Sobrien { 1771169689Skan regset r = bb->il.rtl->global_live_at_start; 177252284Sobrien if (REGNO_REG_SET_P (r, from)) 177352284Sobrien { 177452284Sobrien CLEAR_REGNO_REG_SET (r, from); 177552284Sobrien SET_REGNO_REG_SET (r, to); 177652284Sobrien } 177752284Sobrien } 177818334Speter} 177918334Speter 178052284Sobrien/* Used for communication between the following functions. Holds the 178152284Sobrien current life information. */ 178252284Sobrienstatic regset live_relevant_regs; 178352284Sobrien 178490075Sobrien/* Record in live_relevant_regs and REGS_SET that register REG became live. 178590075Sobrien This is called via note_stores. */ 178652284Sobrienstatic void 1787132718Skanreg_becomes_live (rtx reg, rtx setter ATTRIBUTE_UNUSED, void *regs_set) 178852284Sobrien{ 178952284Sobrien int regno; 179052284Sobrien 179152284Sobrien if (GET_CODE (reg) == SUBREG) 179252284Sobrien reg = SUBREG_REG (reg); 179352284Sobrien 1794169689Skan if (!REG_P (reg)) 179552284Sobrien return; 1796117395Skan 179752284Sobrien regno = REGNO (reg); 179852284Sobrien if (regno < FIRST_PSEUDO_REGISTER) 179952284Sobrien { 1800169689Skan int nregs = hard_regno_nregs[regno][GET_MODE (reg)]; 180152284Sobrien while (nregs-- > 0) 180290075Sobrien { 180390075Sobrien SET_REGNO_REG_SET (live_relevant_regs, regno); 180490075Sobrien if (! fixed_regs[regno]) 180590075Sobrien SET_REGNO_REG_SET ((regset) regs_set, regno); 180690075Sobrien regno++; 180790075Sobrien } 180852284Sobrien } 180952284Sobrien else if (reg_renumber[regno] >= 0) 181090075Sobrien { 181190075Sobrien SET_REGNO_REG_SET (live_relevant_regs, regno); 181290075Sobrien SET_REGNO_REG_SET ((regset) regs_set, regno); 181390075Sobrien } 181452284Sobrien} 181552284Sobrien 181652284Sobrien/* Record in live_relevant_regs that register REGNO died. */ 181752284Sobrienstatic void 1818132718Skanreg_dies (int regno, enum machine_mode mode, struct insn_chain *chain) 181952284Sobrien{ 182052284Sobrien if (regno < FIRST_PSEUDO_REGISTER) 182152284Sobrien { 1822169689Skan int nregs = hard_regno_nregs[regno][mode]; 182352284Sobrien while (nregs-- > 0) 182490075Sobrien { 182590075Sobrien CLEAR_REGNO_REG_SET (live_relevant_regs, regno); 182690075Sobrien if (! fixed_regs[regno]) 182790075Sobrien SET_REGNO_REG_SET (&chain->dead_or_set, regno); 182890075Sobrien regno++; 182990075Sobrien } 183052284Sobrien } 183152284Sobrien else 183290075Sobrien { 183390075Sobrien CLEAR_REGNO_REG_SET (live_relevant_regs, regno); 183490075Sobrien if (reg_renumber[regno] >= 0) 183590075Sobrien SET_REGNO_REG_SET (&chain->dead_or_set, regno); 183690075Sobrien } 183752284Sobrien} 183852284Sobrien 183952284Sobrien/* Walk the insns of the current function and build reload_insn_chain, 184052284Sobrien and record register life information. */ 184190075Sobrienvoid 1842132718Skanbuild_insn_chain (rtx first) 184352284Sobrien{ 184452284Sobrien struct insn_chain **p = &reload_insn_chain; 184552284Sobrien struct insn_chain *prev = 0; 1846117395Skan basic_block b = ENTRY_BLOCK_PTR->next_bb; 184752284Sobrien 1848169689Skan live_relevant_regs = ALLOC_REG_SET (®_obstack); 184952284Sobrien 185052284Sobrien for (; first; first = NEXT_INSN (first)) 185152284Sobrien { 185252284Sobrien struct insn_chain *c; 185352284Sobrien 1854132718Skan if (first == BB_HEAD (b)) 185552284Sobrien { 1856169689Skan unsigned i; 1857169689Skan bitmap_iterator bi; 185890075Sobrien 185952284Sobrien CLEAR_REG_SET (live_relevant_regs); 186052284Sobrien 1861169689Skan EXECUTE_IF_SET_IN_BITMAP (b->il.rtl->global_live_at_start, 0, i, bi) 1862169689Skan { 1863169689Skan if (i < FIRST_PSEUDO_REGISTER 1864169689Skan ? ! TEST_HARD_REG_BIT (eliminable_regset, i) 1865169689Skan : reg_renumber[i] >= 0) 1866169689Skan SET_REGNO_REG_SET (live_relevant_regs, i); 1867169689Skan } 1868117395Skan } 186952284Sobrien 1870169689Skan if (!NOTE_P (first) && !BARRIER_P (first)) 187152284Sobrien { 187252284Sobrien c = new_insn_chain (); 187352284Sobrien c->prev = prev; 187452284Sobrien prev = c; 187552284Sobrien *p = c; 187652284Sobrien p = &c->next; 187752284Sobrien c->insn = first; 1878117395Skan c->block = b->index; 187952284Sobrien 188090075Sobrien if (INSN_P (first)) 188152284Sobrien { 188252284Sobrien rtx link; 188352284Sobrien 188452284Sobrien /* Mark the death of everything that dies in this instruction. */ 188552284Sobrien 188652284Sobrien for (link = REG_NOTES (first); link; link = XEXP (link, 1)) 188752284Sobrien if (REG_NOTE_KIND (link) == REG_DEAD 1888169689Skan && REG_P (XEXP (link, 0))) 188990075Sobrien reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)), 189090075Sobrien c); 189152284Sobrien 189290075Sobrien COPY_REG_SET (&c->live_throughout, live_relevant_regs); 189390075Sobrien 189452284Sobrien /* Mark everything born in this instruction as live. */ 189552284Sobrien 189690075Sobrien note_stores (PATTERN (first), reg_becomes_live, 189790075Sobrien &c->dead_or_set); 189852284Sobrien } 189990075Sobrien else 190090075Sobrien COPY_REG_SET (&c->live_throughout, live_relevant_regs); 190152284Sobrien 190290075Sobrien if (INSN_P (first)) 190352284Sobrien { 190452284Sobrien rtx link; 190552284Sobrien 190652284Sobrien /* Mark anything that is set in this insn and then unused as dying. */ 190752284Sobrien 190852284Sobrien for (link = REG_NOTES (first); link; link = XEXP (link, 1)) 190952284Sobrien if (REG_NOTE_KIND (link) == REG_UNUSED 1910169689Skan && REG_P (XEXP (link, 0))) 191190075Sobrien reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)), 191290075Sobrien c); 191352284Sobrien } 191452284Sobrien } 191552284Sobrien 1916132718Skan if (first == BB_END (b)) 1917117395Skan b = b->next_bb; 191852284Sobrien 191952284Sobrien /* Stop after we pass the end of the last basic block. Verify that 192052284Sobrien no real insns are after the end of the last basic block. 192152284Sobrien 192252284Sobrien We may want to reorganize the loop somewhat since this test should 192390075Sobrien always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if 192490075Sobrien the previous real insn is a JUMP_INSN. */ 1925117395Skan if (b == EXIT_BLOCK_PTR) 192652284Sobrien { 1927169689Skan#ifdef ENABLE_CHECKING 1928169689Skan for (first = NEXT_INSN (first); first; first = NEXT_INSN (first)) 1929169689Skan gcc_assert (!INSN_P (first) 1930169689Skan || GET_CODE (PATTERN (first)) == USE 1931169689Skan || ((GET_CODE (PATTERN (first)) == ADDR_VEC 1932169689Skan || GET_CODE (PATTERN (first)) == ADDR_DIFF_VEC) 1933169689Skan && prev_real_insn (first) != 0 1934169689Skan && JUMP_P (prev_real_insn (first)))); 1935169689Skan#endif 193652284Sobrien break; 193752284Sobrien } 193852284Sobrien } 193952284Sobrien FREE_REG_SET (live_relevant_regs); 194052284Sobrien *p = 0; 194152284Sobrien} 194252284Sobrien 194390075Sobrien/* Print debugging trace information if -dg switch is given, 194418334Speter showing the information on which the allocation decisions are based. */ 194518334Speter 194618334Speterstatic void 1947132718Skandump_conflicts (FILE *file) 194818334Speter{ 194990075Sobrien int i; 195090075Sobrien int has_preferences; 195190075Sobrien int nregs; 195252284Sobrien nregs = 0; 195318334Speter for (i = 0; i < max_allocno; i++) 195418334Speter { 195590075Sobrien if (reg_renumber[allocno[allocno_order[i]].reg] >= 0) 1956117395Skan continue; 195752284Sobrien nregs++; 195852284Sobrien } 195952284Sobrien fprintf (file, ";; %d regs to allocate:", nregs); 196052284Sobrien for (i = 0; i < max_allocno; i++) 196152284Sobrien { 196218334Speter int j; 196390075Sobrien if (reg_renumber[allocno[allocno_order[i]].reg] >= 0) 196452284Sobrien continue; 196590075Sobrien fprintf (file, " %d", allocno[allocno_order[i]].reg); 196618334Speter for (j = 0; j < max_regno; j++) 196718334Speter if (reg_allocno[j] == allocno_order[i] 196890075Sobrien && j != allocno[allocno_order[i]].reg) 196918334Speter fprintf (file, "+%d", j); 197090075Sobrien if (allocno[allocno_order[i]].size != 1) 197190075Sobrien fprintf (file, " (%d)", allocno[allocno_order[i]].size); 197218334Speter } 197318334Speter fprintf (file, "\n"); 197418334Speter 197518334Speter for (i = 0; i < max_allocno; i++) 197618334Speter { 197790075Sobrien int j; 197890075Sobrien fprintf (file, ";; %d conflicts:", allocno[i].reg); 197918334Speter for (j = 0; j < max_allocno; j++) 198090075Sobrien if (CONFLICTP (j, i)) 198190075Sobrien fprintf (file, " %d", allocno[j].reg); 198218334Speter for (j = 0; j < FIRST_PSEUDO_REGISTER; j++) 198390075Sobrien if (TEST_HARD_REG_BIT (allocno[i].hard_reg_conflicts, j)) 198418334Speter fprintf (file, " %d", j); 198518334Speter fprintf (file, "\n"); 198618334Speter 198718334Speter has_preferences = 0; 198818334Speter for (j = 0; j < FIRST_PSEUDO_REGISTER; j++) 198990075Sobrien if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j)) 199018334Speter has_preferences = 1; 199118334Speter 199218334Speter if (! has_preferences) 199318334Speter continue; 199490075Sobrien fprintf (file, ";; %d preferences:", allocno[i].reg); 199518334Speter for (j = 0; j < FIRST_PSEUDO_REGISTER; j++) 199690075Sobrien if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j)) 199718334Speter fprintf (file, " %d", j); 199818334Speter fprintf (file, "\n"); 199918334Speter } 200018334Speter fprintf (file, "\n"); 200118334Speter} 200218334Speter 200318334Spetervoid 2004132718Skandump_global_regs (FILE *file) 200518334Speter{ 200690075Sobrien int i, j; 2007117395Skan 200818334Speter fprintf (file, ";; Register dispositions:\n"); 200918334Speter for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++) 201018334Speter if (reg_renumber[i] >= 0) 201118334Speter { 201218334Speter fprintf (file, "%d in %d ", i, reg_renumber[i]); 2013117395Skan if (++j % 6 == 0) 201418334Speter fprintf (file, "\n"); 201518334Speter } 201618334Speter 201718334Speter fprintf (file, "\n\n;; Hard regs used: "); 201818334Speter for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 201918334Speter if (regs_ever_live[i]) 202018334Speter fprintf (file, " %d", i); 202118334Speter fprintf (file, "\n\n"); 202218334Speter} 2023169689Skan 2024169689Skan 2025169689Skan 2026169689Skan/* This page contains code to make live information more accurate. 2027169689Skan The accurate register liveness at program point P means: 2028169689Skan o there is a path from P to usage of the register and the 2029169689Skan register is not redefined or killed on the path. 2030169689Skan o register at P is partially available, i.e. there is a path from 2031169689Skan a register definition to the point P and the register is not 2032169689Skan killed (clobbered) on the path 2033169689Skan 2034169689Skan The standard GCC live information means only the first condition. 2035169689Skan Without the partial availability, there will be more register 2036169689Skan conflicts and as a consequence worse register allocation. The 2037169689Skan typical example where the information can be different is a 2038169689Skan register initialized in the loop at the basic block preceding the 2039169689Skan loop in CFG. */ 2040169689Skan 2041169689Skan/* The following structure contains basic block data flow information 2042169689Skan used to calculate partial availability of registers. */ 2043169689Skan 2044169689Skanstruct bb_info 2045169689Skan{ 2046169689Skan /* The basic block reverse post-order number. */ 2047169689Skan int rts_number; 2048169689Skan /* Registers used uninitialized in an insn in which there is an 2049169689Skan early clobbered register might get the same hard register. */ 2050169689Skan bitmap earlyclobber; 2051169689Skan /* Registers correspondingly killed (clobbered) and defined but not 2052169689Skan killed afterward in the basic block. */ 2053169689Skan bitmap killed, avloc; 2054169689Skan /* Registers partially available and living (in other words whose 2055169689Skan values were calculated and used) correspondingly at the start 2056169689Skan and end of the basic block. */ 2057169689Skan bitmap live_pavin, live_pavout; 2058169689Skan}; 2059169689Skan 2060169689Skan/* Macros for accessing data flow information of basic blocks. */ 2061169689Skan 2062169689Skan#define BB_INFO(BB) ((struct bb_info *) (BB)->aux) 2063169689Skan#define BB_INFO_BY_INDEX(N) BB_INFO (BASIC_BLOCK(N)) 2064169689Skan 2065169689Skanstatic struct bitmap_obstack greg_obstack; 2066169689Skan/* The function allocates the info structures of each basic block. It 2067169689Skan also initialized LIVE_PAVIN and LIVE_PAVOUT as if all hard 2068169689Skan registers were partially available. */ 2069169689Skan 2070169689Skanstatic void 2071169689Skanallocate_bb_info (void) 2072169689Skan{ 2073169689Skan int i; 2074169689Skan basic_block bb; 2075169689Skan struct bb_info *bb_info; 2076169689Skan bitmap init; 2077169689Skan 2078169689Skan alloc_aux_for_blocks (sizeof (struct bb_info)); 2079169689Skan init = BITMAP_ALLOC (NULL); 2080169689Skan for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 2081169689Skan bitmap_set_bit (init, i); 2082169689Skan bitmap_obstack_initialize (&greg_obstack); 2083169689Skan FOR_EACH_BB (bb) 2084169689Skan { 2085169689Skan bb_info = bb->aux; 2086169689Skan bb_info->earlyclobber = BITMAP_ALLOC (&greg_obstack); 2087169689Skan bb_info->avloc = BITMAP_ALLOC (&greg_obstack); 2088169689Skan bb_info->killed = BITMAP_ALLOC (&greg_obstack); 2089169689Skan bb_info->live_pavin = BITMAP_ALLOC (&greg_obstack); 2090169689Skan bb_info->live_pavout = BITMAP_ALLOC (&greg_obstack); 2091169689Skan bitmap_copy (bb_info->live_pavin, init); 2092169689Skan bitmap_copy (bb_info->live_pavout, init); 2093169689Skan } 2094169689Skan BITMAP_FREE (init); 2095169689Skan} 2096169689Skan 2097169689Skan/* The function frees the allocated info of all basic blocks. */ 2098169689Skan 2099169689Skanstatic void 2100169689Skanfree_bb_info (void) 2101169689Skan{ 2102169689Skan bitmap_obstack_release (&greg_obstack); 2103169689Skan free_aux_for_blocks (); 2104169689Skan} 2105169689Skan 2106169689Skan/* The function modifies local info for register REG being changed in 2107169689Skan SETTER. DATA is used to pass the current basic block info. */ 2108169689Skan 2109169689Skanstatic void 2110169689Skanmark_reg_change (rtx reg, rtx setter, void *data) 2111169689Skan{ 2112169689Skan int regno; 2113169689Skan basic_block bb = data; 2114169689Skan struct bb_info *bb_info = BB_INFO (bb); 2115169689Skan 2116169689Skan if (GET_CODE (reg) == SUBREG) 2117169689Skan reg = SUBREG_REG (reg); 2118169689Skan 2119169689Skan if (!REG_P (reg)) 2120169689Skan return; 2121169689Skan 2122169689Skan regno = REGNO (reg); 2123169689Skan bitmap_set_bit (bb_info->killed, regno); 2124169689Skan 2125169689Skan if (GET_CODE (setter) != CLOBBER) 2126169689Skan bitmap_set_bit (bb_info->avloc, regno); 2127169689Skan else 2128169689Skan bitmap_clear_bit (bb_info->avloc, regno); 2129169689Skan} 2130169689Skan 2131169689Skan/* Classes of registers which could be early clobbered in the current 2132169689Skan insn. */ 2133169689Skan 2134169689Skanstatic VEC(int,heap) *earlyclobber_regclass; 2135169689Skan 2136169689Skan/* This function finds and stores register classes that could be early 2137169689Skan clobbered in INSN. If any earlyclobber classes are found, the function 2138169689Skan returns TRUE, in all other cases it returns FALSE. */ 2139169689Skan 2140169689Skanstatic bool 2141169689Skancheck_earlyclobber (rtx insn) 2142169689Skan{ 2143169689Skan int opno; 2144169689Skan bool found = false; 2145169689Skan 2146169689Skan extract_insn (insn); 2147169689Skan 2148169689Skan VEC_truncate (int, earlyclobber_regclass, 0); 2149169689Skan for (opno = 0; opno < recog_data.n_operands; opno++) 2150169689Skan { 2151169689Skan char c; 2152169689Skan bool amp_p; 2153169689Skan int i; 2154169689Skan enum reg_class class; 2155169689Skan const char *p = recog_data.constraints[opno]; 2156169689Skan 2157169689Skan class = NO_REGS; 2158169689Skan amp_p = false; 2159169689Skan for (;;) 2160169689Skan { 2161169689Skan c = *p; 2162169689Skan switch (c) 2163169689Skan { 2164169689Skan case '=': case '+': case '?': 2165169689Skan case '#': case '!': 2166169689Skan case '*': case '%': 2167169689Skan case 'm': case '<': case '>': case 'V': case 'o': 2168169689Skan case 'E': case 'F': case 'G': case 'H': 2169169689Skan case 's': case 'i': case 'n': 2170169689Skan case 'I': case 'J': case 'K': case 'L': 2171169689Skan case 'M': case 'N': case 'O': case 'P': 2172169689Skan case 'X': 2173169689Skan case '0': case '1': case '2': case '3': case '4': 2174169689Skan case '5': case '6': case '7': case '8': case '9': 2175169689Skan /* These don't say anything we care about. */ 2176169689Skan break; 2177169689Skan 2178169689Skan case '&': 2179169689Skan amp_p = true; 2180169689Skan break; 2181169689Skan case '\0': 2182169689Skan case ',': 2183169689Skan if (amp_p && class != NO_REGS) 2184169689Skan { 2185169689Skan int rc; 2186169689Skan 2187169689Skan found = true; 2188169689Skan for (i = 0; 2189169689Skan VEC_iterate (int, earlyclobber_regclass, i, rc); 2190169689Skan i++) 2191169689Skan { 2192169689Skan if (rc == (int) class) 2193169689Skan goto found_rc; 2194169689Skan } 2195169689Skan 2196169689Skan /* We use VEC_quick_push here because 2197169689Skan earlyclobber_regclass holds no more than 2198169689Skan N_REG_CLASSES elements. */ 2199169689Skan VEC_quick_push (int, earlyclobber_regclass, (int) class); 2200169689Skan found_rc: 2201169689Skan ; 2202169689Skan } 2203169689Skan 2204169689Skan amp_p = false; 2205169689Skan class = NO_REGS; 2206169689Skan break; 2207169689Skan 2208169689Skan case 'r': 2209169689Skan class = GENERAL_REGS; 2210169689Skan break; 2211169689Skan 2212169689Skan default: 2213169689Skan class = REG_CLASS_FROM_CONSTRAINT (c, p); 2214169689Skan break; 2215169689Skan } 2216169689Skan if (c == '\0') 2217169689Skan break; 2218169689Skan p += CONSTRAINT_LEN (c, p); 2219169689Skan } 2220169689Skan } 2221169689Skan 2222169689Skan return found; 2223169689Skan} 2224169689Skan 2225169689Skan/* The function checks that pseudo-register *X has a class 2226169689Skan intersecting with the class of pseudo-register could be early 2227169689Skan clobbered in the same insn. 2228169689Skan This function is a no-op if earlyclobber_regclass is empty. */ 2229169689Skan 2230169689Skanstatic int 2231169689Skanmark_reg_use_for_earlyclobber (rtx *x, void *data ATTRIBUTE_UNUSED) 2232169689Skan{ 2233169689Skan enum reg_class pref_class, alt_class; 2234169689Skan int i, regno; 2235169689Skan basic_block bb = data; 2236169689Skan struct bb_info *bb_info = BB_INFO (bb); 2237169689Skan 2238169689Skan if (REG_P (*x) && REGNO (*x) >= FIRST_PSEUDO_REGISTER) 2239169689Skan { 2240169689Skan int rc; 2241169689Skan 2242169689Skan regno = REGNO (*x); 2243169689Skan if (bitmap_bit_p (bb_info->killed, regno) 2244169689Skan || bitmap_bit_p (bb_info->avloc, regno)) 2245169689Skan return 0; 2246169689Skan pref_class = reg_preferred_class (regno); 2247169689Skan alt_class = reg_alternate_class (regno); 2248169689Skan for (i = 0; VEC_iterate (int, earlyclobber_regclass, i, rc); i++) 2249169689Skan { 2250169689Skan if (reg_classes_intersect_p (rc, pref_class) 2251169689Skan || (rc != NO_REGS 2252169689Skan && reg_classes_intersect_p (rc, alt_class))) 2253169689Skan { 2254169689Skan bitmap_set_bit (bb_info->earlyclobber, regno); 2255169689Skan break; 2256169689Skan } 2257169689Skan } 2258169689Skan } 2259169689Skan return 0; 2260169689Skan} 2261169689Skan 2262169689Skan/* The function processes all pseudo-registers in *X with the aid of 2263169689Skan previous function. */ 2264169689Skan 2265169689Skanstatic void 2266169689Skanmark_reg_use_for_earlyclobber_1 (rtx *x, void *data) 2267169689Skan{ 2268169689Skan for_each_rtx (x, mark_reg_use_for_earlyclobber, data); 2269169689Skan} 2270169689Skan 2271169689Skan/* The function calculates local info for each basic block. */ 2272169689Skan 2273169689Skanstatic void 2274169689Skancalculate_local_reg_bb_info (void) 2275169689Skan{ 2276169689Skan basic_block bb; 2277169689Skan rtx insn, bound; 2278169689Skan 2279169689Skan /* We know that earlyclobber_regclass holds no more than 2280169689Skan N_REG_CLASSES elements. See check_earlyclobber. */ 2281169689Skan earlyclobber_regclass = VEC_alloc (int, heap, N_REG_CLASSES); 2282169689Skan FOR_EACH_BB (bb) 2283169689Skan { 2284169689Skan bound = NEXT_INSN (BB_END (bb)); 2285169689Skan for (insn = BB_HEAD (bb); insn != bound; insn = NEXT_INSN (insn)) 2286169689Skan if (INSN_P (insn)) 2287169689Skan { 2288169689Skan note_stores (PATTERN (insn), mark_reg_change, bb); 2289169689Skan if (check_earlyclobber (insn)) 2290169689Skan note_uses (&PATTERN (insn), mark_reg_use_for_earlyclobber_1, bb); 2291169689Skan } 2292169689Skan } 2293169689Skan VEC_free (int, heap, earlyclobber_regclass); 2294169689Skan} 2295169689Skan 2296169689Skan/* The function sets up reverse post-order number of each basic 2297169689Skan block. */ 2298169689Skan 2299169689Skanstatic void 2300169689Skanset_up_bb_rts_numbers (void) 2301169689Skan{ 2302169689Skan int i; 2303169689Skan int *rts_order; 2304169689Skan 2305169689Skan rts_order = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS); 2306169689Skan post_order_compute (rts_order, false); 2307169689Skan for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++) 2308169689Skan BB_INFO_BY_INDEX (rts_order [i])->rts_number = i; 2309169689Skan free (rts_order); 2310169689Skan} 2311169689Skan 2312169689Skan/* Compare function for sorting blocks in reverse postorder. */ 2313169689Skan 2314169689Skanstatic int 2315169689Skanrpost_cmp (const void *bb1, const void *bb2) 2316169689Skan{ 2317169689Skan basic_block b1 = *(basic_block *) bb1, b2 = *(basic_block *) bb2; 2318169689Skan 2319169689Skan return BB_INFO (b2)->rts_number - BB_INFO (b1)->rts_number; 2320169689Skan} 2321169689Skan 2322169689Skan/* Temporary bitmap used for live_pavin, live_pavout calculation. */ 2323169689Skanstatic bitmap temp_bitmap; 2324169689Skan 2325169689Skan/* The function calculates partial register availability according to 2326169689Skan the following equations: 2327169689Skan 2328169689Skan bb.live_pavin 2329169689Skan = empty for entry block 2330169689Skan | union (live_pavout of predecessors) & global_live_at_start 2331169689Skan bb.live_pavout = union (bb.live_pavin - bb.killed, bb.avloc) 2332169689Skan & global_live_at_end */ 2333169689Skan 2334169689Skanstatic void 2335169689Skancalculate_reg_pav (void) 2336169689Skan{ 2337169689Skan basic_block bb, succ; 2338169689Skan edge e; 2339169689Skan int i, nel; 2340169689Skan VEC(basic_block,heap) *bbs, *new_bbs, *temp; 2341169689Skan basic_block *bb_array; 2342169689Skan sbitmap wset; 2343169689Skan 2344169689Skan bbs = VEC_alloc (basic_block, heap, n_basic_blocks); 2345169689Skan new_bbs = VEC_alloc (basic_block, heap, n_basic_blocks); 2346169689Skan temp_bitmap = BITMAP_ALLOC (NULL); 2347169689Skan FOR_EACH_BB (bb) 2348169689Skan { 2349169689Skan VEC_quick_push (basic_block, bbs, bb); 2350169689Skan } 2351169689Skan wset = sbitmap_alloc (n_basic_blocks + 1); 2352169689Skan while (VEC_length (basic_block, bbs)) 2353169689Skan { 2354169689Skan bb_array = VEC_address (basic_block, bbs); 2355169689Skan nel = VEC_length (basic_block, bbs); 2356169689Skan qsort (bb_array, nel, sizeof (basic_block), rpost_cmp); 2357169689Skan sbitmap_zero (wset); 2358169689Skan for (i = 0; i < nel; i++) 2359169689Skan { 2360169689Skan edge_iterator ei; 2361169689Skan struct bb_info *bb_info; 2362169689Skan bitmap bb_live_pavin, bb_live_pavout; 2363169689Skan 2364169689Skan bb = bb_array [i]; 2365169689Skan bb_info = BB_INFO (bb); 2366169689Skan bb_live_pavin = bb_info->live_pavin; 2367169689Skan bb_live_pavout = bb_info->live_pavout; 2368169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 2369169689Skan { 2370169689Skan basic_block pred = e->src; 2371169689Skan 2372169689Skan if (pred->index != ENTRY_BLOCK) 2373169689Skan bitmap_ior_into (bb_live_pavin, BB_INFO (pred)->live_pavout); 2374169689Skan } 2375169689Skan bitmap_and_into (bb_live_pavin, bb->il.rtl->global_live_at_start); 2376169689Skan bitmap_ior_and_compl (temp_bitmap, bb_info->avloc, 2377169689Skan bb_live_pavin, bb_info->killed); 2378169689Skan bitmap_and_into (temp_bitmap, bb->il.rtl->global_live_at_end); 2379169689Skan if (! bitmap_equal_p (temp_bitmap, bb_live_pavout)) 2380169689Skan { 2381169689Skan bitmap_copy (bb_live_pavout, temp_bitmap); 2382169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 2383169689Skan { 2384169689Skan succ = e->dest; 2385169689Skan if (succ->index != EXIT_BLOCK 2386169689Skan && !TEST_BIT (wset, succ->index)) 2387169689Skan { 2388169689Skan SET_BIT (wset, succ->index); 2389169689Skan VEC_quick_push (basic_block, new_bbs, succ); 2390169689Skan } 2391169689Skan } 2392169689Skan } 2393169689Skan } 2394169689Skan temp = bbs; 2395169689Skan bbs = new_bbs; 2396169689Skan new_bbs = temp; 2397169689Skan VEC_truncate (basic_block, new_bbs, 0); 2398169689Skan } 2399169689Skan sbitmap_free (wset); 2400169689Skan BITMAP_FREE (temp_bitmap); 2401169689Skan VEC_free (basic_block, heap, new_bbs); 2402169689Skan VEC_free (basic_block, heap, bbs); 2403169689Skan} 2404169689Skan 2405169689Skan/* The function modifies partial availability information for two 2406169689Skan special cases to prevent incorrect work of the subsequent passes 2407169689Skan with the accurate live information based on the partial 2408169689Skan availability. */ 2409169689Skan 2410169689Skanstatic void 2411169689Skanmodify_reg_pav (void) 2412169689Skan{ 2413169689Skan basic_block bb; 2414169689Skan struct bb_info *bb_info; 2415169689Skan#ifdef STACK_REGS 2416169689Skan int i; 2417169689Skan HARD_REG_SET zero, stack_hard_regs, used; 2418169689Skan bitmap stack_regs; 2419169689Skan 2420169689Skan CLEAR_HARD_REG_SET (zero); 2421169689Skan CLEAR_HARD_REG_SET (stack_hard_regs); 2422169689Skan for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++) 2423169689Skan SET_HARD_REG_BIT(stack_hard_regs, i); 2424169689Skan stack_regs = BITMAP_ALLOC (&greg_obstack); 2425169689Skan for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 2426169689Skan { 2427169689Skan COPY_HARD_REG_SET (used, reg_class_contents[reg_preferred_class (i)]); 2428169689Skan IOR_HARD_REG_SET (used, reg_class_contents[reg_alternate_class (i)]); 2429169689Skan AND_HARD_REG_SET (used, stack_hard_regs); 2430169689Skan GO_IF_HARD_REG_EQUAL(used, zero, skip); 2431169689Skan bitmap_set_bit (stack_regs, i); 2432169689Skan skip: 2433169689Skan ; 2434169689Skan } 2435169689Skan#endif 2436169689Skan FOR_EACH_BB (bb) 2437169689Skan { 2438169689Skan bb_info = BB_INFO (bb); 2439169689Skan 2440169689Skan /* Reload can assign the same hard register to uninitialized 2441169689Skan pseudo-register and early clobbered pseudo-register in an 2442169689Skan insn if the pseudo-register is used first time in given BB 2443169689Skan and not lived at the BB start. To prevent this we don't 2444169689Skan change life information for such pseudo-registers. */ 2445169689Skan bitmap_ior_into (bb_info->live_pavin, bb_info->earlyclobber); 2446169689Skan#ifdef STACK_REGS 2447169689Skan /* We can not use the same stack register for uninitialized 2448169689Skan pseudo-register and another living pseudo-register because if the 2449169689Skan uninitialized pseudo-register dies, subsequent pass reg-stack 2450169689Skan will be confused (it will believe that the other register 2451169689Skan dies). */ 2452169689Skan bitmap_ior_into (bb_info->live_pavin, stack_regs); 2453169689Skan#endif 2454169689Skan } 2455169689Skan#ifdef STACK_REGS 2456169689Skan BITMAP_FREE (stack_regs); 2457169689Skan#endif 2458169689Skan} 2459169689Skan 2460169689Skan/* The following function makes live information more accurate by 2461169689Skan modifying global_live_at_start and global_live_at_end of basic 2462169689Skan blocks. 2463169689Skan 2464169689Skan The standard GCC life analysis permits registers to live 2465169689Skan uninitialized, for example: 2466169689Skan 2467169689Skan R is never used 2468169689Skan ..... 2469169689Skan Loop: 2470169689Skan R is defined 2471169689Skan ... 2472169689Skan R is used. 2473169689Skan 2474169689Skan With normal life_analysis, R would be live before "Loop:". 2475169689Skan The result is that R causes many interferences that do not 2476169689Skan serve any purpose. 2477169689Skan 2478169689Skan After the function call a register lives at a program point 2479169689Skan only if it is initialized on a path from CFG entry to the 2480169689Skan program point. */ 2481169689Skan 2482169689Skanstatic void 2483169689Skanmake_accurate_live_analysis (void) 2484169689Skan{ 2485169689Skan basic_block bb; 2486169689Skan struct bb_info *bb_info; 2487169689Skan 2488169689Skan max_regno = max_reg_num (); 2489169689Skan compact_blocks (); 2490169689Skan allocate_bb_info (); 2491169689Skan calculate_local_reg_bb_info (); 2492169689Skan set_up_bb_rts_numbers (); 2493169689Skan calculate_reg_pav (); 2494169689Skan modify_reg_pav (); 2495169689Skan FOR_EACH_BB (bb) 2496169689Skan { 2497169689Skan bb_info = BB_INFO (bb); 2498169689Skan 2499169689Skan bitmap_and_into (bb->il.rtl->global_live_at_start, bb_info->live_pavin); 2500169689Skan bitmap_and_into (bb->il.rtl->global_live_at_end, bb_info->live_pavout); 2501169689Skan } 2502169689Skan free_bb_info (); 2503169689Skan} 2504169689Skan/* Run old register allocator. Return TRUE if we must exit 2505169689Skan rest_of_compilation upon return. */ 2506169689Skanstatic unsigned int 2507169689Skanrest_of_handle_global_alloc (void) 2508169689Skan{ 2509169689Skan bool failure; 2510169689Skan 2511169689Skan /* If optimizing, allocate remaining pseudo-regs. Do the reload 2512169689Skan pass fixing up any insns that are invalid. */ 2513169689Skan 2514169689Skan if (optimize) 2515169689Skan failure = global_alloc (); 2516169689Skan else 2517169689Skan { 2518169689Skan build_insn_chain (get_insns ()); 2519169689Skan failure = reload (get_insns (), 0); 2520169689Skan } 2521169689Skan 2522169689Skan if (dump_enabled_p (pass_global_alloc.static_pass_number)) 2523169689Skan { 2524169689Skan timevar_push (TV_DUMP); 2525169689Skan dump_global_regs (dump_file); 2526169689Skan timevar_pop (TV_DUMP); 2527169689Skan } 2528169689Skan 2529169689Skan gcc_assert (reload_completed || failure); 2530169689Skan reload_completed = !failure; 2531169689Skan return 0; 2532169689Skan} 2533169689Skan 2534169689Skanstruct tree_opt_pass pass_global_alloc = 2535169689Skan{ 2536169689Skan "greg", /* name */ 2537169689Skan NULL, /* gate */ 2538169689Skan rest_of_handle_global_alloc, /* execute */ 2539169689Skan NULL, /* sub */ 2540169689Skan NULL, /* next */ 2541169689Skan 0, /* static_pass_number */ 2542169689Skan TV_GLOBAL_ALLOC, /* tv_id */ 2543169689Skan 0, /* properties_required */ 2544169689Skan 0, /* properties_provided */ 2545169689Skan 0, /* properties_destroyed */ 2546169689Skan 0, /* todo_flags_start */ 2547169689Skan TODO_dump_func | 2548169689Skan TODO_ggc_collect, /* todo_flags_finish */ 2549169689Skan 'g' /* letter */ 2550169689Skan}; 2551169689Skan 2552