198944Sobrien/* Allocate registers for pseudo-registers that span basic blocks. 298944Sobrien Copyright (C) 1987, 88, 91, 94, 96-98, 1999 Free Software Foundation, Inc. 398944Sobrien 498944SobrienThis file is part of GNU CC. 598944Sobrien 698944SobrienGNU CC is free software; you can redistribute it and/or modify 798944Sobrienit under the terms of the GNU General Public License as published by 898944Sobrienthe Free Software Foundation; either version 2, or (at your option) 998944Sobrienany later version. 1098944Sobrien 1198944SobrienGNU CC is distributed in the hope that it will be useful, 1298944Sobrienbut WITHOUT ANY WARRANTY; without even the implied warranty of 1398944SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1498944SobrienGNU General Public License for more details. 1598944Sobrien 1698944SobrienYou should have received a copy of the GNU General Public License 1798944Sobrienalong with GNU CC; see the file COPYING. If not, write to 1898944Sobrienthe Free Software Foundation, 59 Temple Place - Suite 330, 1998944SobrienBoston, MA 02111-1307, USA. */ 2098944Sobrien 2198944Sobrien 2298944Sobrien#include "config.h" 2398944Sobrien#include "system.h" 2498944Sobrien 2598944Sobrien#include "machmode.h" 2698944Sobrien#include "hard-reg-set.h" 2798944Sobrien#include "rtl.h" 2898944Sobrien#include "flags.h" 2998944Sobrien#include "basic-block.h" 3098944Sobrien#include "regs.h" 3198944Sobrien#include "insn-config.h" 3298944Sobrien#include "reload.h" 3398944Sobrien#include "output.h" 3498944Sobrien#include "toplev.h" 35130803Smarcel 36130803Smarcel/* This pass of the compiler performs global register allocation. 3798944Sobrien It assigns hard register numbers to all the pseudo registers 3898944Sobrien that were not handled in local_alloc. Assignments are recorded 3998944Sobrien in the vector reg_renumber, not by changing the rtl code. 4098944Sobrien (Such changes are made by final). The entry point is 4198944Sobrien the function global_alloc. 4298944Sobrien 4398944Sobrien After allocation is complete, the reload pass is run as a subroutine 4498944Sobrien of this pass, so that when a pseudo reg loses its hard reg due to 4598944Sobrien spilling it is possible to make a second attempt to find a hard 4698944Sobrien reg for it. The reload pass is independent in other respects 4798944Sobrien and it is run even when stupid register allocation is in use. 4898944Sobrien 4998944Sobrien 1. Assign allocation-numbers (allocnos) to the pseudo-registers 5098944Sobrien still needing allocations and to the pseudo-registers currently 5198944Sobrien allocated by local-alloc which may be spilled by reload. 5298944Sobrien Set up tables reg_allocno and allocno_reg to map 5398944Sobrien reg numbers to allocnos and vice versa. 5498944Sobrien max_allocno gets the number of allocnos in use. 5598944Sobrien 5698944Sobrien 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it. 5798944Sobrien Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix 5898944Sobrien for conflicts between allocnos and explicit hard register use 5998944Sobrien (which includes use of pseudo-registers allocated by local_alloc). 6098944Sobrien 6198944Sobrien 3. For each basic block 62130803Smarcel walk forward through the block, recording which 6398944Sobrien pseudo-registers and which hardware registers are live. 6498944Sobrien Build the conflict matrix between the pseudo-registers 6598944Sobrien and another of pseudo-registers versus hardware registers. 6698944Sobrien Also record the preferred hardware registers 67130803Smarcel for each pseudo-register. 6898944Sobrien 6998944Sobrien 4. Sort a table of the allocnos into order of 7098944Sobrien desirability of the variables. 7198944Sobrien 7298944Sobrien 5. Allocate the variables in that order; each if possible into 7398944Sobrien a preferred register, else into another register. */ 7498944Sobrien 7598944Sobrien/* Number of pseudo-registers which are candidates for allocation. */ 7698944Sobrien 7798944Sobrienstatic int max_allocno; 7898944Sobrien 7998944Sobrien/* Indexed by (pseudo) reg number, gives the allocno, or -1 8098944Sobrien for pseudo registers which are not to be allocated. */ 81130803Smarcel 82130803Smarcelstatic int *reg_allocno; 8398944Sobrien 84130803Smarcel/* Indexed by allocno, gives the reg number. */ 85130803Smarcel 86130803Smarcelstatic int *allocno_reg; 87130803Smarcel 88130803Smarcel/* A vector of the integers from 0 to max_allocno-1, 89130803Smarcel sorted in the order of first-to-be-allocated first. */ 90130803Smarcel 91130803Smarcelstatic int *allocno_order; 92130803Smarcel 93130803Smarcel/* Indexed by an allocno, gives the number of consecutive 94130803Smarcel hard registers needed by that pseudo reg. */ 95130803Smarcel 96130803Smarcelstatic int *allocno_size; 97130803Smarcel 98130803Smarcel/* Indexed by (pseudo) reg number, gives the number of another 99130803Smarcel lower-numbered pseudo reg which can share a hard reg with this pseudo 10098944Sobrien *even if the two pseudos would otherwise appear to conflict*. */ 10198944Sobrien 10298944Sobrienstatic int *reg_may_share; 10398944Sobrien 10498944Sobrien/* Define the number of bits in each element of `conflicts' and what 10598944Sobrien type that element has. We use the largest integer format on the 10698944Sobrien host machine. */ 10798944Sobrien 10898944Sobrien#define INT_BITS HOST_BITS_PER_WIDE_INT 10998944Sobrien#define INT_TYPE HOST_WIDE_INT 11098944Sobrien 11198944Sobrien/* max_allocno by max_allocno array of bits, 11298944Sobrien recording whether two allocno's conflict (can't go in the same 11398944Sobrien hardware register). 11498944Sobrien 11598944Sobrien `conflicts' is not symmetric; a conflict between allocno's i and j 11698944Sobrien is recorded either in element i,j or in element j,i. */ 11798944Sobrien 11898944Sobrienstatic INT_TYPE *conflicts; 11998944Sobrien 12098944Sobrien/* Number of ints require to hold max_allocno bits. 12198944Sobrien This is the length of a row in `conflicts'. */ 12298944Sobrien 12398944Sobrienstatic int allocno_row_words; 12498944Sobrien 12598944Sobrien/* Two macros to test or store 1 in an element of `conflicts'. */ 12698944Sobrien 12798944Sobrien#define CONFLICTP(I, J) \ 12898944Sobrien (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \ 12998944Sobrien & ((INT_TYPE) 1 << ((J) % INT_BITS))) 13098944Sobrien 13198944Sobrien#define SET_CONFLICT(I, J) \ 13298944Sobrien (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \ 13398944Sobrien |= ((INT_TYPE) 1 << ((J) % INT_BITS))) 13498944Sobrien 13598944Sobrien/* Set of hard regs currently live (during scan of all insns). */ 13698944Sobrien 13798944Sobrienstatic HARD_REG_SET hard_regs_live; 13898944Sobrien 13998944Sobrien/* Indexed by N, set of hard regs conflicting with allocno N. */ 14098944Sobrien 14198944Sobrienstatic HARD_REG_SET *hard_reg_conflicts; 14298944Sobrien 14398944Sobrien/* Indexed by N, set of hard regs preferred by allocno N. 14498944Sobrien This is used to make allocnos go into regs that are copied to or from them, 14598944Sobrien when possible, to reduce register shuffling. */ 14698944Sobrien 14798944Sobrienstatic HARD_REG_SET *hard_reg_preferences; 14898944Sobrien 14998944Sobrien/* Similar, but just counts register preferences made in simple copy 15098944Sobrien operations, rather than arithmetic. These are given priority because 15198944Sobrien we can always eliminate an insn by using these, but using a register 152130803Smarcel in the above list won't always eliminate an insn. */ 153130803Smarcel 15498944Sobrienstatic HARD_REG_SET *hard_reg_copy_preferences; 15598944Sobrien 15698944Sobrien/* Similar to hard_reg_preferences, but includes bits for subsequent 15798944Sobrien registers when an allocno is multi-word. The above variable is used for 15898944Sobrien allocation while this is used to build reg_someone_prefers, below. */ 15998944Sobrien 16098944Sobrienstatic HARD_REG_SET *hard_reg_full_preferences; 16198944Sobrien 16298944Sobrien/* Indexed by N, set of hard registers that some later allocno has a 163130803Smarcel preference for. */ 164130803Smarcel 16598944Sobrienstatic HARD_REG_SET *regs_someone_prefers; 16698944Sobrien 16798944Sobrien/* Set of registers that global-alloc isn't supposed to use. */ 16898944Sobrien 16998944Sobrienstatic HARD_REG_SET no_global_alloc_regs; 17098944Sobrien 17198944Sobrien/* Set of registers used so far. */ 17298944Sobrien 17398944Sobrienstatic HARD_REG_SET regs_used_so_far; 17498944Sobrien 17598944Sobrien/* Number of calls crossed by each allocno. */ 17698944Sobrien 17798944Sobrienstatic int *allocno_calls_crossed; 17898944Sobrien 179/* Number of refs (weighted) to each allocno. */ 180 181static int *allocno_n_refs; 182 183/* Guess at live length of each allocno. 184 This is actually the max of the live lengths of the regs. */ 185 186static int *allocno_live_length; 187 188/* Number of refs (weighted) to each hard reg, as used by local alloc. 189 It is zero for a reg that contains global pseudos or is explicitly used. */ 190 191static int local_reg_n_refs[FIRST_PSEUDO_REGISTER]; 192 193/* Guess at live length of each hard reg, as used by local alloc. 194 This is actually the sum of the live lengths of the specific regs. */ 195 196static int local_reg_live_length[FIRST_PSEUDO_REGISTER]; 197 198/* Test a bit in TABLE, a vector of HARD_REG_SETs, 199 for vector element I, and hard register number J. */ 200 201#define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J) 202 203/* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */ 204 205#define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J) 206 207/* Bit mask for allocnos live at current point in the scan. */ 208 209static INT_TYPE *allocnos_live; 210 211/* Test, set or clear bit number I in allocnos_live, 212 a bit vector indexed by allocno. */ 213 214#define ALLOCNO_LIVE_P(I) \ 215 (allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS))) 216 217#define SET_ALLOCNO_LIVE(I) \ 218 (allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS))) 219 220#define CLEAR_ALLOCNO_LIVE(I) \ 221 (allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((I) % INT_BITS))) 222 223/* This is turned off because it doesn't work right for DImode. 224 (And it is only used for DImode, so the other cases are worthless.) 225 The problem is that it isn't true that there is NO possibility of conflict; 226 only that there is no conflict if the two pseudos get the exact same regs. 227 If they were allocated with a partial overlap, there would be a conflict. 228 We can't safely turn off the conflict unless we have another way to 229 prevent the partial overlap. 230 231 Idea: change hard_reg_conflicts so that instead of recording which 232 hard regs the allocno may not overlap, it records where the allocno 233 may not start. Change both where it is used and where it is updated. 234 Then there is a way to record that (reg:DI 108) may start at 10 235 but not at 9 or 11. There is still the question of how to record 236 this semi-conflict between two pseudos. */ 237#if 0 238/* Reg pairs for which conflict after the current insn 239 is inhibited by a REG_NO_CONFLICT note. 240 If the table gets full, we ignore any other notes--that is conservative. */ 241#define NUM_NO_CONFLICT_PAIRS 4 242/* Number of pairs in use in this insn. */ 243int n_no_conflict_pairs; 244static struct { int allocno1, allocno2;} 245 no_conflict_pairs[NUM_NO_CONFLICT_PAIRS]; 246#endif /* 0 */ 247 248/* Record all regs that are set in any one insn. 249 Communication from mark_reg_{store,clobber} and global_conflicts. */ 250 251static rtx *regs_set; 252static int n_regs_set; 253 254/* All registers that can be eliminated. */ 255 256static HARD_REG_SET eliminable_regset; 257 258static int allocno_compare PROTO((const GENERIC_PTR, const GENERIC_PTR)); 259static void global_conflicts PROTO((void)); 260static void expand_preferences PROTO((void)); 261static void prune_preferences PROTO((void)); 262static void find_reg PROTO((int, HARD_REG_SET, int, int, int)); 263static void record_one_conflict PROTO((int)); 264static void record_conflicts PROTO((int *, int)); 265static void mark_reg_store PROTO((rtx, rtx)); 266static void mark_reg_clobber PROTO((rtx, rtx)); 267static void mark_reg_conflicts PROTO((rtx)); 268static void mark_reg_death PROTO((rtx)); 269static void mark_reg_live_nc PROTO((int, enum machine_mode)); 270static void set_preference PROTO((rtx, rtx)); 271static void dump_conflicts PROTO((FILE *)); 272static void reg_becomes_live PROTO((rtx, rtx)); 273static void reg_dies PROTO((int, enum machine_mode)); 274static void build_insn_chain PROTO((rtx)); 275 276/* Perform allocation of pseudo-registers not allocated by local_alloc. 277 FILE is a file to output debugging information on, 278 or zero if such output is not desired. 279 280 Return value is nonzero if reload failed 281 and we must not do any more for this function. */ 282 283int 284global_alloc (file) 285 FILE *file; 286{ 287 int retval; 288#ifdef ELIMINABLE_REGS 289 static struct {int from, to; } eliminables[] = ELIMINABLE_REGS; 290#endif 291 int need_fp 292 = (! flag_omit_frame_pointer 293#ifdef EXIT_IGNORE_STACK 294 || (current_function_calls_alloca && EXIT_IGNORE_STACK) 295#endif 296 || FRAME_POINTER_REQUIRED); 297 298 register size_t i; 299 rtx x; 300 301 max_allocno = 0; 302 303 /* A machine may have certain hard registers that 304 are safe to use only within a basic block. */ 305 306 CLEAR_HARD_REG_SET (no_global_alloc_regs); 307#ifdef OVERLAPPING_REGNO_P 308 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 309 if (OVERLAPPING_REGNO_P (i)) 310 SET_HARD_REG_BIT (no_global_alloc_regs, i); 311#endif 312 313 /* Build the regset of all eliminable registers and show we can't use those 314 that we already know won't be eliminated. */ 315#ifdef ELIMINABLE_REGS 316 for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++) 317 { 318 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from); 319 320 if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to) 321 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp)) 322 SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from); 323 } 324#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 325 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM); 326 if (need_fp) 327 SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM); 328#endif 329 330#else 331 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM); 332 if (need_fp) 333 SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM); 334#endif 335 336 /* Track which registers have already been used. Start with registers 337 explicitly in the rtl, then registers allocated by local register 338 allocation. */ 339 340 CLEAR_HARD_REG_SET (regs_used_so_far); 341#ifdef LEAF_REGISTERS 342 /* If we are doing the leaf function optimization, and this is a leaf 343 function, it means that the registers that take work to save are those 344 that need a register window. So prefer the ones that can be used in 345 a leaf function. */ 346 { 347 char *cheap_regs; 348 static char leaf_regs[] = LEAF_REGISTERS; 349 350 if (only_leaf_regs_used () && leaf_function_p ()) 351 cheap_regs = leaf_regs; 352 else 353 cheap_regs = call_used_regs; 354 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 355 if (regs_ever_live[i] || cheap_regs[i]) 356 SET_HARD_REG_BIT (regs_used_so_far, i); 357 } 358#else 359 /* We consider registers that do not have to be saved over calls as if 360 they were already used since there is no cost in using them. */ 361 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 362 if (regs_ever_live[i] || call_used_regs[i]) 363 SET_HARD_REG_BIT (regs_used_so_far, i); 364#endif 365 366 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++) 367 if (reg_renumber[i] >= 0) 368 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]); 369 370 /* Establish mappings from register number to allocation number 371 and vice versa. In the process, count the allocnos. */ 372 373 reg_allocno = (int *) alloca (max_regno * sizeof (int)); 374 375 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 376 reg_allocno[i] = -1; 377 378 /* Initialize the shared-hard-reg mapping 379 from the list of pairs that may share. */ 380 reg_may_share = (int *) alloca (max_regno * sizeof (int)); 381 bzero ((char *) reg_may_share, max_regno * sizeof (int)); 382 for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1)) 383 { 384 int r1 = REGNO (XEXP (x, 0)); 385 int r2 = REGNO (XEXP (XEXP (x, 1), 0)); 386 if (r1 > r2) 387 reg_may_share[r1] = r2; 388 else 389 reg_may_share[r2] = r1; 390 } 391 392 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++) 393 /* Note that reg_live_length[i] < 0 indicates a "constant" reg 394 that we are supposed to refrain from putting in a hard reg. 395 -2 means do make an allocno but don't allocate it. */ 396 if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1 397 /* Don't allocate pseudos that cross calls, 398 if this function receives a nonlocal goto. */ 399 && (! current_function_has_nonlocal_label 400 || REG_N_CALLS_CROSSED (i) == 0)) 401 { 402 if (reg_renumber[i] < 0 && reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0) 403 reg_allocno[i] = reg_allocno[reg_may_share[i]]; 404 else 405 reg_allocno[i] = max_allocno++; 406 if (REG_LIVE_LENGTH (i) == 0) 407 abort (); 408 } 409 else 410 reg_allocno[i] = -1; 411 412 allocno_reg = (int *) alloca (max_allocno * sizeof (int)); 413 allocno_size = (int *) alloca (max_allocno * sizeof (int)); 414 allocno_calls_crossed = (int *) alloca (max_allocno * sizeof (int)); 415 allocno_n_refs = (int *) alloca (max_allocno * sizeof (int)); 416 allocno_live_length = (int *) alloca (max_allocno * sizeof (int)); 417 bzero ((char *) allocno_size, max_allocno * sizeof (int)); 418 bzero ((char *) allocno_calls_crossed, max_allocno * sizeof (int)); 419 bzero ((char *) allocno_n_refs, max_allocno * sizeof (int)); 420 bzero ((char *) allocno_live_length, max_allocno * sizeof (int)); 421 422 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++) 423 if (reg_allocno[i] >= 0) 424 { 425 int allocno = reg_allocno[i]; 426 allocno_reg[allocno] = i; 427 allocno_size[allocno] = PSEUDO_REGNO_SIZE (i); 428 allocno_calls_crossed[allocno] += REG_N_CALLS_CROSSED (i); 429 allocno_n_refs[allocno] += REG_N_REFS (i); 430 if (allocno_live_length[allocno] < REG_LIVE_LENGTH (i)) 431 allocno_live_length[allocno] = REG_LIVE_LENGTH (i); 432 } 433 434 /* Calculate amount of usage of each hard reg by pseudos 435 allocated by local-alloc. This is to see if we want to 436 override it. */ 437 bzero ((char *) local_reg_live_length, sizeof local_reg_live_length); 438 bzero ((char *) local_reg_n_refs, sizeof local_reg_n_refs); 439 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++) 440 if (reg_renumber[i] >= 0) 441 { 442 int regno = reg_renumber[i]; 443 int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i)); 444 int j; 445 446 for (j = regno; j < endregno; j++) 447 { 448 local_reg_n_refs[j] += REG_N_REFS (i); 449 local_reg_live_length[j] += REG_LIVE_LENGTH (i); 450 } 451 } 452 453 /* We can't override local-alloc for a reg used not just by local-alloc. */ 454 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 455 if (regs_ever_live[i]) 456 local_reg_n_refs[i] = 0; 457 458 /* Allocate the space for the conflict and preference tables and 459 initialize them. */ 460 461 hard_reg_conflicts 462 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET)); 463 bzero ((char *) hard_reg_conflicts, max_allocno * sizeof (HARD_REG_SET)); 464 465 hard_reg_preferences 466 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET)); 467 bzero ((char *) hard_reg_preferences, max_allocno * sizeof (HARD_REG_SET)); 468 469 hard_reg_copy_preferences 470 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET)); 471 bzero ((char *) hard_reg_copy_preferences, 472 max_allocno * sizeof (HARD_REG_SET)); 473 474 hard_reg_full_preferences 475 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET)); 476 bzero ((char *) hard_reg_full_preferences, 477 max_allocno * sizeof (HARD_REG_SET)); 478 479 regs_someone_prefers 480 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET)); 481 bzero ((char *) regs_someone_prefers, max_allocno * sizeof (HARD_REG_SET)); 482 483 allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS; 484 485 /* We used to use alloca here, but the size of what it would try to 486 allocate would occasionally cause it to exceed the stack limit and 487 cause unpredictable core dumps. Some examples were > 2Mb in size. */ 488 conflicts = (INT_TYPE *) xmalloc (max_allocno * allocno_row_words 489 * sizeof (INT_TYPE)); 490 bzero ((char *) conflicts, 491 max_allocno * allocno_row_words * sizeof (INT_TYPE)); 492 493 allocnos_live = (INT_TYPE *) alloca (allocno_row_words * sizeof (INT_TYPE)); 494 495 /* If there is work to be done (at least one reg to allocate), 496 perform global conflict analysis and allocate the regs. */ 497 498 if (max_allocno > 0) 499 { 500 /* Scan all the insns and compute the conflicts among allocnos 501 and between allocnos and hard regs. */ 502 503 global_conflicts (); 504 505 /* Eliminate conflicts between pseudos and eliminable registers. If 506 the register is not eliminated, the pseudo won't really be able to 507 live in the eliminable register, so the conflict doesn't matter. 508 If we do eliminate the register, the conflict will no longer exist. 509 So in either case, we can ignore the conflict. Likewise for 510 preferences. */ 511 512 for (i = 0; i < (size_t) max_allocno; i++) 513 { 514 AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset); 515 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i], 516 eliminable_regset); 517 AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset); 518 } 519 520 /* Try to expand the preferences by merging them between allocnos. */ 521 522 expand_preferences (); 523 524 /* Determine the order to allocate the remaining pseudo registers. */ 525 526 allocno_order = (int *) alloca (max_allocno * sizeof (int)); 527 for (i = 0; i < (size_t) max_allocno; i++) 528 allocno_order[i] = i; 529 530 /* Default the size to 1, since allocno_compare uses it to divide by. 531 Also convert allocno_live_length of zero to -1. A length of zero 532 can occur when all the registers for that allocno have reg_live_length 533 equal to -2. In this case, we want to make an allocno, but not 534 allocate it. So avoid the divide-by-zero and set it to a low 535 priority. */ 536 537 for (i = 0; i < (size_t) max_allocno; i++) 538 { 539 if (allocno_size[i] == 0) 540 allocno_size[i] = 1; 541 if (allocno_live_length[i] == 0) 542 allocno_live_length[i] = -1; 543 } 544 545 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare); 546 547 prune_preferences (); 548 549 if (file) 550 dump_conflicts (file); 551 552 /* Try allocating them, one by one, in that order, 553 except for parameters marked with reg_live_length[regno] == -2. */ 554 555 for (i = 0; i < (size_t) max_allocno; i++) 556 if (reg_renumber[allocno_reg[allocno_order[i]]] < 0 557 && REG_LIVE_LENGTH (allocno_reg[allocno_order[i]]) >= 0) 558 { 559 /* If we have more than one register class, 560 first try allocating in the class that is cheapest 561 for this pseudo-reg. If that fails, try any reg. */ 562 if (N_REG_CLASSES > 1) 563 { 564 find_reg (allocno_order[i], 0, 0, 0, 0); 565 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0) 566 continue; 567 } 568 if (reg_alternate_class (allocno_reg[allocno_order[i]]) != NO_REGS) 569 find_reg (allocno_order[i], 0, 1, 0, 0); 570 } 571 } 572 573 /* Do the reloads now while the allocno data still exist, so that we can 574 try to assign new hard regs to any pseudo regs that are spilled. */ 575 576#if 0 /* We need to eliminate regs even if there is no rtl code, 577 for the sake of debugging information. */ 578 if (n_basic_blocks > 0) 579#endif 580 { 581 build_insn_chain (get_insns ()); 582 retval = reload (get_insns (), 1, file); 583 } 584 585 free (conflicts); 586 return retval; 587} 588 589/* Sort predicate for ordering the allocnos. 590 Returns -1 (1) if *v1 should be allocated before (after) *v2. */ 591 592static int 593allocno_compare (v1p, v2p) 594 const GENERIC_PTR v1p; 595 const GENERIC_PTR v2p; 596{ 597 int v1 = *(int *)v1p, v2 = *(int *)v2p; 598 /* Note that the quotient will never be bigger than 599 the value of floor_log2 times the maximum number of 600 times a register can occur in one insn (surely less than 100). 601 Multiplying this by 10000 can't overflow. */ 602 register int pri1 603 = (((double) (floor_log2 (allocno_n_refs[v1]) * allocno_n_refs[v1]) 604 / allocno_live_length[v1]) 605 * 10000 * allocno_size[v1]); 606 register int pri2 607 = (((double) (floor_log2 (allocno_n_refs[v2]) * allocno_n_refs[v2]) 608 / allocno_live_length[v2]) 609 * 10000 * allocno_size[v2]); 610 if (pri2 - pri1) 611 return pri2 - pri1; 612 613 /* If regs are equally good, sort by allocno, 614 so that the results of qsort leave nothing to chance. */ 615 return v1 - v2; 616} 617 618/* Scan the rtl code and record all conflicts and register preferences in the 619 conflict matrices and preference tables. */ 620 621static void 622global_conflicts () 623{ 624 register int b, i; 625 register rtx insn; 626 int *block_start_allocnos; 627 628 /* Make a vector that mark_reg_{store,clobber} will store in. */ 629 regs_set = (rtx *) alloca (max_parallel * sizeof (rtx) * 2); 630 631 block_start_allocnos = (int *) alloca (max_allocno * sizeof (int)); 632 633 for (b = 0; b < n_basic_blocks; b++) 634 { 635 bzero ((char *) allocnos_live, allocno_row_words * sizeof (INT_TYPE)); 636 637 /* Initialize table of registers currently live 638 to the state at the beginning of this basic block. 639 This also marks the conflicts among them. 640 641 For pseudo-regs, there is only one bit for each one 642 no matter how many hard regs it occupies. 643 This is ok; we know the size from PSEUDO_REGNO_SIZE. 644 For explicit hard regs, we cannot know the size that way 645 since one hard reg can be used with various sizes. 646 Therefore, we must require that all the hard regs 647 implicitly live as part of a multi-word hard reg 648 are explicitly marked in basic_block_live_at_start. */ 649 650 { 651 register regset old = BASIC_BLOCK (b)->global_live_at_start; 652 int ax = 0; 653 654 REG_SET_TO_HARD_REG_SET (hard_regs_live, old); 655 EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i, 656 { 657 register int a = reg_allocno[i]; 658 if (a >= 0) 659 { 660 SET_ALLOCNO_LIVE (a); 661 block_start_allocnos[ax++] = a; 662 } 663 else if ((a = reg_renumber[i]) >= 0) 664 mark_reg_live_nc 665 (a, PSEUDO_REGNO_MODE (i)); 666 }); 667 668 /* Record that each allocno now live conflicts with each other 669 allocno now live, and with each hard reg now live. */ 670 671 record_conflicts (block_start_allocnos, ax); 672 673#ifdef STACK_REGS 674 { 675 /* Pseudos can't go in stack regs at the start of a basic block 676 that can be reached through a computed goto, since reg-stack 677 can't handle computed gotos. */ 678 /* ??? Seems more likely that reg-stack can't handle any abnormal 679 edges, critical or not, computed goto or otherwise. */ 680 681 edge e; 682 for (e = BASIC_BLOCK (b)->pred; e ; e = e->pred_next) 683 if (e->flags & EDGE_ABNORMAL) 684 break; 685 686 if (e != NULL) 687 for (ax = FIRST_STACK_REG; ax <= LAST_STACK_REG; ax++) 688 record_one_conflict (ax); 689 } 690#endif 691 } 692 693 insn = BLOCK_HEAD (b); 694 695 /* Scan the code of this basic block, noting which allocnos 696 and hard regs are born or die. When one is born, 697 record a conflict with all others currently live. */ 698 699 while (1) 700 { 701 register RTX_CODE code = GET_CODE (insn); 702 register rtx link; 703 704 /* Make regs_set an empty set. */ 705 706 n_regs_set = 0; 707 708 if (code == INSN || code == CALL_INSN || code == JUMP_INSN) 709 { 710 711#if 0 712 int i = 0; 713 for (link = REG_NOTES (insn); 714 link && i < NUM_NO_CONFLICT_PAIRS; 715 link = XEXP (link, 1)) 716 if (REG_NOTE_KIND (link) == REG_NO_CONFLICT) 717 { 718 no_conflict_pairs[i].allocno1 719 = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))]; 720 no_conflict_pairs[i].allocno2 721 = reg_allocno[REGNO (XEXP (link, 0))]; 722 i++; 723 } 724#endif /* 0 */ 725 726 /* Mark any registers clobbered by INSN as live, 727 so they conflict with the inputs. */ 728 729 note_stores (PATTERN (insn), mark_reg_clobber); 730 731 /* Mark any registers dead after INSN as dead now. */ 732 733 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 734 if (REG_NOTE_KIND (link) == REG_DEAD) 735 mark_reg_death (XEXP (link, 0)); 736 737 /* Mark any registers set in INSN as live, 738 and mark them as conflicting with all other live regs. 739 Clobbers are processed again, so they conflict with 740 the registers that are set. */ 741 742 note_stores (PATTERN (insn), mark_reg_store); 743 744#ifdef AUTO_INC_DEC 745 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 746 if (REG_NOTE_KIND (link) == REG_INC) 747 mark_reg_store (XEXP (link, 0), NULL_RTX); 748#endif 749 750 /* If INSN has multiple outputs, then any reg that dies here 751 and is used inside of an output 752 must conflict with the other outputs. 753 754 It is unsafe to use !single_set here since it will ignore an 755 unused output. Just because an output is unused does not mean 756 the compiler can assume the side effect will not occur. 757 Consider if REG appears in the address of an output and we 758 reload the output. If we allocate REG to the same hard 759 register as an unused output we could set the hard register 760 before the output reload insn. */ 761 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn)) 762 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 763 if (REG_NOTE_KIND (link) == REG_DEAD) 764 { 765 int used_in_output = 0; 766 int i; 767 rtx reg = XEXP (link, 0); 768 769 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) 770 { 771 rtx set = XVECEXP (PATTERN (insn), 0, i); 772 if (GET_CODE (set) == SET 773 && GET_CODE (SET_DEST (set)) != REG 774 && !rtx_equal_p (reg, SET_DEST (set)) 775 && reg_overlap_mentioned_p (reg, SET_DEST (set))) 776 used_in_output = 1; 777 } 778 if (used_in_output) 779 mark_reg_conflicts (reg); 780 } 781 782 /* Mark any registers set in INSN and then never used. */ 783 784 while (n_regs_set > 0) 785 if (find_regno_note (insn, REG_UNUSED, 786 REGNO (regs_set[--n_regs_set]))) 787 mark_reg_death (regs_set[n_regs_set]); 788 } 789 790 if (insn == BLOCK_END (b)) 791 break; 792 insn = NEXT_INSN (insn); 793 } 794 } 795} 796/* Expand the preference information by looking for cases where one allocno 797 dies in an insn that sets an allocno. If those two allocnos don't conflict, 798 merge any preferences between those allocnos. */ 799 800static void 801expand_preferences () 802{ 803 rtx insn; 804 rtx link; 805 rtx set; 806 807 /* We only try to handle the most common cases here. Most of the cases 808 where this wins are reg-reg copies. */ 809 810 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 811 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i' 812 && (set = single_set (insn)) != 0 813 && GET_CODE (SET_DEST (set)) == REG 814 && reg_allocno[REGNO (SET_DEST (set))] >= 0) 815 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 816 if (REG_NOTE_KIND (link) == REG_DEAD 817 && GET_CODE (XEXP (link, 0)) == REG 818 && reg_allocno[REGNO (XEXP (link, 0))] >= 0 819 && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))], 820 reg_allocno[REGNO (XEXP (link, 0))]) 821 && ! CONFLICTP (reg_allocno[REGNO (XEXP (link, 0))], 822 reg_allocno[REGNO (SET_DEST (set))])) 823 { 824 int a1 = reg_allocno[REGNO (SET_DEST (set))]; 825 int a2 = reg_allocno[REGNO (XEXP (link, 0))]; 826 827 if (XEXP (link, 0) == SET_SRC (set)) 828 { 829 IOR_HARD_REG_SET (hard_reg_copy_preferences[a1], 830 hard_reg_copy_preferences[a2]); 831 IOR_HARD_REG_SET (hard_reg_copy_preferences[a2], 832 hard_reg_copy_preferences[a1]); 833 } 834 835 IOR_HARD_REG_SET (hard_reg_preferences[a1], 836 hard_reg_preferences[a2]); 837 IOR_HARD_REG_SET (hard_reg_preferences[a2], 838 hard_reg_preferences[a1]); 839 IOR_HARD_REG_SET (hard_reg_full_preferences[a1], 840 hard_reg_full_preferences[a2]); 841 IOR_HARD_REG_SET (hard_reg_full_preferences[a2], 842 hard_reg_full_preferences[a1]); 843 } 844} 845 846/* Prune the preferences for global registers to exclude registers that cannot 847 be used. 848 849 Compute `regs_someone_prefers', which is a bitmask of the hard registers 850 that are preferred by conflicting registers of lower priority. If possible, 851 we will avoid using these registers. */ 852 853static void 854prune_preferences () 855{ 856 int i, j; 857 int allocno; 858 859 /* Scan least most important to most important. 860 For each allocno, remove from preferences registers that cannot be used, 861 either because of conflicts or register type. Then compute all registers 862 preferred by each lower-priority register that conflicts. */ 863 864 for (i = max_allocno - 1; i >= 0; i--) 865 { 866 HARD_REG_SET temp; 867 868 allocno = allocno_order[i]; 869 COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]); 870 871 if (allocno_calls_crossed[allocno] == 0) 872 IOR_HARD_REG_SET (temp, fixed_reg_set); 873 else 874 IOR_HARD_REG_SET (temp, call_used_reg_set); 875 876 IOR_COMPL_HARD_REG_SET 877 (temp, 878 reg_class_contents[(int) reg_preferred_class (allocno_reg[allocno])]); 879 880 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], temp); 881 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], temp); 882 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences[allocno], temp); 883 884 CLEAR_HARD_REG_SET (regs_someone_prefers[allocno]); 885 886 /* Merge in the preferences of lower-priority registers (they have 887 already been pruned). If we also prefer some of those registers, 888 don't exclude them unless we are of a smaller size (in which case 889 we want to give the lower-priority allocno the first chance for 890 these registers). */ 891 for (j = i + 1; j < max_allocno; j++) 892 if (CONFLICTP (allocno, allocno_order[j]) 893 || CONFLICTP (allocno_order[j], allocno)) 894 { 895 COPY_HARD_REG_SET (temp, 896 hard_reg_full_preferences[allocno_order[j]]); 897 if (allocno_size[allocno_order[j]] <= allocno_size[allocno]) 898 AND_COMPL_HARD_REG_SET (temp, 899 hard_reg_full_preferences[allocno]); 900 901 IOR_HARD_REG_SET (regs_someone_prefers[allocno], temp); 902 } 903 } 904} 905 906/* Assign a hard register to ALLOCNO; look for one that is the beginning 907 of a long enough stretch of hard regs none of which conflicts with ALLOCNO. 908 The registers marked in PREFREGS are tried first. 909 910 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot 911 be used for this allocation. 912 913 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg. 914 Otherwise ignore that preferred class and use the alternate class. 915 916 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that 917 will have to be saved and restored at calls. 918 919 RETRYING is nonzero if this is called from retry_global_alloc. 920 921 If we find one, record it in reg_renumber. 922 If not, do nothing. */ 923 924static void 925find_reg (allocno, losers, alt_regs_p, accept_call_clobbered, retrying) 926 int allocno; 927 HARD_REG_SET losers; 928 int alt_regs_p; 929 int accept_call_clobbered; 930 int retrying; 931{ 932 register int i, best_reg, pass; 933#ifdef HARD_REG_SET 934 register /* Declare it register if it's a scalar. */ 935#endif 936 HARD_REG_SET used, used1, used2; 937 938 enum reg_class class = (alt_regs_p 939 ? reg_alternate_class (allocno_reg[allocno]) 940 : reg_preferred_class (allocno_reg[allocno])); 941 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]); 942 943 if (accept_call_clobbered) 944 COPY_HARD_REG_SET (used1, call_fixed_reg_set); 945 else if (allocno_calls_crossed[allocno] == 0) 946 COPY_HARD_REG_SET (used1, fixed_reg_set); 947 else 948 COPY_HARD_REG_SET (used1, call_used_reg_set); 949 950 /* Some registers should not be allocated in global-alloc. */ 951 IOR_HARD_REG_SET (used1, no_global_alloc_regs); 952 if (losers) 953 IOR_HARD_REG_SET (used1, losers); 954 955 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]); 956 COPY_HARD_REG_SET (used2, used1); 957 958 IOR_HARD_REG_SET (used1, hard_reg_conflicts[allocno]); 959 960#ifdef CLASS_CANNOT_CHANGE_SIZE 961 if (REG_CHANGES_SIZE (allocno_reg[allocno])) 962 IOR_HARD_REG_SET (used1, 963 reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]); 964#endif 965 966 /* Try each hard reg to see if it fits. Do this in two passes. 967 In the first pass, skip registers that are preferred by some other pseudo 968 to give it a better chance of getting one of those registers. Only if 969 we can't get a register when excluding those do we take one of them. 970 However, we never allocate a register for the first time in pass 0. */ 971 972 COPY_HARD_REG_SET (used, used1); 973 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far); 974 IOR_HARD_REG_SET (used, regs_someone_prefers[allocno]); 975 976 best_reg = -1; 977 for (i = FIRST_PSEUDO_REGISTER, pass = 0; 978 pass <= 1 && i >= FIRST_PSEUDO_REGISTER; 979 pass++) 980 { 981 if (pass == 1) 982 COPY_HARD_REG_SET (used, used1); 983 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 984 { 985#ifdef REG_ALLOC_ORDER 986 int regno = reg_alloc_order[i]; 987#else 988 int regno = i; 989#endif 990 if (! TEST_HARD_REG_BIT (used, regno) 991 && HARD_REGNO_MODE_OK (regno, mode) 992 && (allocno_calls_crossed[allocno] == 0 993 || accept_call_clobbered 994 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))) 995 { 996 register int j; 997 register int lim = regno + HARD_REGNO_NREGS (regno, mode); 998 for (j = regno + 1; 999 (j < lim 1000 && ! TEST_HARD_REG_BIT (used, j)); 1001 j++); 1002 if (j == lim) 1003 { 1004 best_reg = regno; 1005 break; 1006 } 1007#ifndef REG_ALLOC_ORDER 1008 i = j; /* Skip starting points we know will lose */ 1009#endif 1010 } 1011 } 1012 } 1013 1014 /* See if there is a preferred register with the same class as the register 1015 we allocated above. Making this restriction prevents register 1016 preferencing from creating worse register allocation. 1017 1018 Remove from the preferred registers and conflicting registers. Note that 1019 additional conflicts may have been added after `prune_preferences' was 1020 called. 1021 1022 First do this for those register with copy preferences, then all 1023 preferred registers. */ 1024 1025 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], used); 1026 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences[allocno], 1027 reg_class_contents[(int) NO_REGS], no_copy_prefs); 1028 1029 if (best_reg >= 0) 1030 { 1031 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1032 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences[allocno], i) 1033 && HARD_REGNO_MODE_OK (i, mode) 1034 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg) 1035 || reg_class_subset_p (REGNO_REG_CLASS (i), 1036 REGNO_REG_CLASS (best_reg)) 1037 || reg_class_subset_p (REGNO_REG_CLASS (best_reg), 1038 REGNO_REG_CLASS (i)))) 1039 { 1040 register int j; 1041 register int lim = i + HARD_REGNO_NREGS (i, mode); 1042 for (j = i + 1; 1043 (j < lim 1044 && ! TEST_HARD_REG_BIT (used, j) 1045 && (REGNO_REG_CLASS (j) 1046 == REGNO_REG_CLASS (best_reg + (j - i)) 1047 || reg_class_subset_p (REGNO_REG_CLASS (j), 1048 REGNO_REG_CLASS (best_reg + (j - i))) 1049 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)), 1050 REGNO_REG_CLASS (j)))); 1051 j++); 1052 if (j == lim) 1053 { 1054 best_reg = i; 1055 goto no_prefs; 1056 } 1057 } 1058 } 1059 no_copy_prefs: 1060 1061 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], used); 1062 GO_IF_HARD_REG_SUBSET (hard_reg_preferences[allocno], 1063 reg_class_contents[(int) NO_REGS], no_prefs); 1064 1065 if (best_reg >= 0) 1066 { 1067 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1068 if (TEST_HARD_REG_BIT (hard_reg_preferences[allocno], i) 1069 && HARD_REGNO_MODE_OK (i, mode) 1070 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg) 1071 || reg_class_subset_p (REGNO_REG_CLASS (i), 1072 REGNO_REG_CLASS (best_reg)) 1073 || reg_class_subset_p (REGNO_REG_CLASS (best_reg), 1074 REGNO_REG_CLASS (i)))) 1075 { 1076 register int j; 1077 register int lim = i + HARD_REGNO_NREGS (i, mode); 1078 for (j = i + 1; 1079 (j < lim 1080 && ! TEST_HARD_REG_BIT (used, j) 1081 && (REGNO_REG_CLASS (j) 1082 == REGNO_REG_CLASS (best_reg + (j - i)) 1083 || reg_class_subset_p (REGNO_REG_CLASS (j), 1084 REGNO_REG_CLASS (best_reg + (j - i))) 1085 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)), 1086 REGNO_REG_CLASS (j)))); 1087 j++); 1088 if (j == lim) 1089 { 1090 best_reg = i; 1091 break; 1092 } 1093 } 1094 } 1095 no_prefs: 1096 1097 /* If we haven't succeeded yet, try with caller-saves. 1098 We need not check to see if the current function has nonlocal 1099 labels because we don't put any pseudos that are live over calls in 1100 registers in that case. */ 1101 1102 if (flag_caller_saves && best_reg < 0) 1103 { 1104 /* Did not find a register. If it would be profitable to 1105 allocate a call-clobbered register and save and restore it 1106 around calls, do that. */ 1107 if (! accept_call_clobbered 1108 && allocno_calls_crossed[allocno] != 0 1109 && CALLER_SAVE_PROFITABLE (allocno_n_refs[allocno], 1110 allocno_calls_crossed[allocno])) 1111 { 1112 HARD_REG_SET new_losers; 1113 if (! losers) 1114 CLEAR_HARD_REG_SET (new_losers); 1115 else 1116 COPY_HARD_REG_SET (new_losers, losers); 1117 1118 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set); 1119 find_reg (allocno, new_losers, alt_regs_p, 1, retrying); 1120 if (reg_renumber[allocno_reg[allocno]] >= 0) 1121 { 1122 caller_save_needed = 1; 1123 return; 1124 } 1125 } 1126 } 1127 1128 /* If we haven't succeeded yet, 1129 see if some hard reg that conflicts with us 1130 was utilized poorly by local-alloc. 1131 If so, kick out the regs that were put there by local-alloc 1132 so we can use it instead. */ 1133 if (best_reg < 0 && !retrying 1134 /* Let's not bother with multi-reg allocnos. */ 1135 && allocno_size[allocno] == 1) 1136 { 1137 /* Count from the end, to find the least-used ones first. */ 1138 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--) 1139 { 1140#ifdef REG_ALLOC_ORDER 1141 int regno = reg_alloc_order[i]; 1142#else 1143 int regno = i; 1144#endif 1145 1146 if (local_reg_n_refs[regno] != 0 1147 /* Don't use a reg no good for this pseudo. */ 1148 && ! TEST_HARD_REG_BIT (used2, regno) 1149 && HARD_REGNO_MODE_OK (regno, mode) 1150#ifdef CLASS_CANNOT_CHANGE_SIZE 1151 && ! (REG_CHANGES_SIZE (allocno_reg[allocno]) 1152 && (TEST_HARD_REG_BIT 1153 (reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE], 1154 regno))) 1155#endif 1156 ) 1157 { 1158 /* We explicitly evaluate the divide results into temporary 1159 variables so as to avoid excess precision problems that occur 1160 on a i386-unknown-sysv4.2 (unixware) host. */ 1161 1162 double tmp1 = ((double) local_reg_n_refs[regno] 1163 / local_reg_live_length[regno]); 1164 double tmp2 = ((double) allocno_n_refs[allocno] 1165 / allocno_live_length[allocno]); 1166 1167 if (tmp1 < tmp2) 1168 { 1169 /* Hard reg REGNO was used less in total by local regs 1170 than it would be used by this one allocno! */ 1171 int k; 1172 for (k = 0; k < max_regno; k++) 1173 if (reg_renumber[k] >= 0) 1174 { 1175 int r = reg_renumber[k]; 1176 int endregno 1177 = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k)); 1178 1179 if (regno >= r && regno < endregno) 1180 reg_renumber[k] = -1; 1181 } 1182 1183 best_reg = regno; 1184 break; 1185 } 1186 } 1187 } 1188 } 1189 1190 /* Did we find a register? */ 1191 1192 if (best_reg >= 0) 1193 { 1194 register int lim, j; 1195 HARD_REG_SET this_reg; 1196 1197 /* Yes. Record it as the hard register of this pseudo-reg. */ 1198 reg_renumber[allocno_reg[allocno]] = best_reg; 1199 /* Also of any pseudo-regs that share with it. */ 1200 if (reg_may_share[allocno_reg[allocno]]) 1201 for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++) 1202 if (reg_allocno[j] == allocno) 1203 reg_renumber[j] = best_reg; 1204 1205 /* Make a set of the hard regs being allocated. */ 1206 CLEAR_HARD_REG_SET (this_reg); 1207 lim = best_reg + HARD_REGNO_NREGS (best_reg, mode); 1208 for (j = best_reg; j < lim; j++) 1209 { 1210 SET_HARD_REG_BIT (this_reg, j); 1211 SET_HARD_REG_BIT (regs_used_so_far, j); 1212 /* This is no longer a reg used just by local regs. */ 1213 local_reg_n_refs[j] = 0; 1214 } 1215 /* For each other pseudo-reg conflicting with this one, 1216 mark it as conflicting with the hard regs this one occupies. */ 1217 lim = allocno; 1218 for (j = 0; j < max_allocno; j++) 1219 if (CONFLICTP (lim, j) || CONFLICTP (j, lim)) 1220 { 1221 IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg); 1222 } 1223 } 1224} 1225 1226/* Called from `reload' to look for a hard reg to put pseudo reg REGNO in. 1227 Perhaps it had previously seemed not worth a hard reg, 1228 or perhaps its old hard reg has been commandeered for reloads. 1229 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if 1230 they do not appear to be allocated. 1231 If FORBIDDEN_REGS is zero, no regs are forbidden. */ 1232 1233void 1234retry_global_alloc (regno, forbidden_regs) 1235 int regno; 1236 HARD_REG_SET forbidden_regs; 1237{ 1238 int allocno = reg_allocno[regno]; 1239 if (allocno >= 0) 1240 { 1241 /* If we have more than one register class, 1242 first try allocating in the class that is cheapest 1243 for this pseudo-reg. If that fails, try any reg. */ 1244 if (N_REG_CLASSES > 1) 1245 find_reg (allocno, forbidden_regs, 0, 0, 1); 1246 if (reg_renumber[regno] < 0 1247 && reg_alternate_class (regno) != NO_REGS) 1248 find_reg (allocno, forbidden_regs, 1, 0, 1); 1249 1250 /* If we found a register, modify the RTL for the register to 1251 show the hard register, and mark that register live. */ 1252 if (reg_renumber[regno] >= 0) 1253 { 1254 REGNO (regno_reg_rtx[regno]) = reg_renumber[regno]; 1255 mark_home_live (regno); 1256 } 1257 } 1258} 1259 1260/* Record a conflict between register REGNO 1261 and everything currently live. 1262 REGNO must not be a pseudo reg that was allocated 1263 by local_alloc; such numbers must be translated through 1264 reg_renumber before calling here. */ 1265 1266static void 1267record_one_conflict (regno) 1268 int regno; 1269{ 1270 register int j; 1271 1272 if (regno < FIRST_PSEUDO_REGISTER) 1273 /* When a hard register becomes live, 1274 record conflicts with live pseudo regs. */ 1275 for (j = 0; j < max_allocno; j++) 1276 { 1277 if (ALLOCNO_LIVE_P (j)) 1278 SET_HARD_REG_BIT (hard_reg_conflicts[j], regno); 1279 } 1280 else 1281 /* When a pseudo-register becomes live, 1282 record conflicts first with hard regs, 1283 then with other pseudo regs. */ 1284 { 1285 register int ialloc = reg_allocno[regno]; 1286 register int ialloc_prod = ialloc * allocno_row_words; 1287 IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live); 1288 for (j = allocno_row_words - 1; j >= 0; j--) 1289 { 1290#if 0 1291 int k; 1292 for (k = 0; k < n_no_conflict_pairs; k++) 1293 if (! ((j == no_conflict_pairs[k].allocno1 1294 && ialloc == no_conflict_pairs[k].allocno2) 1295 || 1296 (j == no_conflict_pairs[k].allocno2 1297 && ialloc == no_conflict_pairs[k].allocno1))) 1298#endif /* 0 */ 1299 conflicts[ialloc_prod + j] |= allocnos_live[j]; 1300 } 1301 } 1302} 1303 1304/* Record all allocnos currently live as conflicting 1305 with each other and with all hard regs currently live. 1306 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that 1307 are currently live. Their bits are also flagged in allocnos_live. */ 1308 1309static void 1310record_conflicts (allocno_vec, len) 1311 register int *allocno_vec; 1312 register int len; 1313{ 1314 register int allocno; 1315 register int j; 1316 register int ialloc_prod; 1317 1318 while (--len >= 0) 1319 { 1320 allocno = allocno_vec[len]; 1321 ialloc_prod = allocno * allocno_row_words; 1322 IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live); 1323 for (j = allocno_row_words - 1; j >= 0; j--) 1324 conflicts[ialloc_prod + j] |= allocnos_live[j]; 1325 } 1326} 1327 1328/* Handle the case where REG is set by the insn being scanned, 1329 during the forward scan to accumulate conflicts. 1330 Store a 1 in regs_live or allocnos_live for this register, record how many 1331 consecutive hardware registers it actually needs, 1332 and record a conflict with all other registers already live. 1333 1334 Note that even if REG does not remain alive after this insn, 1335 we must mark it here as live, to ensure a conflict between 1336 REG and any other regs set in this insn that really do live. 1337 This is because those other regs could be considered after this. 1338 1339 REG might actually be something other than a register; 1340 if so, we do nothing. 1341 1342 SETTER is 0 if this register was modified by an auto-increment (i.e., 1343 a REG_INC note was found for it). */ 1344 1345static void 1346mark_reg_store (reg, setter) 1347 rtx reg, setter; 1348{ 1349 register int regno; 1350 1351 /* WORD is which word of a multi-register group is being stored. 1352 For the case where the store is actually into a SUBREG of REG. 1353 Except we don't use it; I believe the entire REG needs to be 1354 made live. */ 1355 int word = 0; 1356 1357 if (GET_CODE (reg) == SUBREG) 1358 { 1359 word = SUBREG_WORD (reg); 1360 reg = SUBREG_REG (reg); 1361 } 1362 1363 if (GET_CODE (reg) != REG) 1364 return; 1365 1366 regs_set[n_regs_set++] = reg; 1367 1368 if (setter && GET_CODE (setter) != CLOBBER) 1369 set_preference (reg, SET_SRC (setter)); 1370 1371 regno = REGNO (reg); 1372 1373 /* Either this is one of the max_allocno pseudo regs not allocated, 1374 or it is or has a hardware reg. First handle the pseudo-regs. */ 1375 if (regno >= FIRST_PSEUDO_REGISTER) 1376 { 1377 if (reg_allocno[regno] >= 0) 1378 { 1379 SET_ALLOCNO_LIVE (reg_allocno[regno]); 1380 record_one_conflict (regno); 1381 } 1382 } 1383 1384 if (reg_renumber[regno] >= 0) 1385 regno = reg_renumber[regno] /* + word */; 1386 1387 /* Handle hardware regs (and pseudos allocated to hard regs). */ 1388 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno]) 1389 { 1390 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)); 1391 while (regno < last) 1392 { 1393 record_one_conflict (regno); 1394 SET_HARD_REG_BIT (hard_regs_live, regno); 1395 regno++; 1396 } 1397 } 1398} 1399 1400/* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */ 1401 1402static void 1403mark_reg_clobber (reg, setter) 1404 rtx reg, setter; 1405{ 1406 if (GET_CODE (setter) == CLOBBER) 1407 mark_reg_store (reg, setter); 1408} 1409 1410/* Record that REG has conflicts with all the regs currently live. 1411 Do not mark REG itself as live. */ 1412 1413static void 1414mark_reg_conflicts (reg) 1415 rtx reg; 1416{ 1417 register int regno; 1418 1419 if (GET_CODE (reg) == SUBREG) 1420 reg = SUBREG_REG (reg); 1421 1422 if (GET_CODE (reg) != REG) 1423 return; 1424 1425 regno = REGNO (reg); 1426 1427 /* Either this is one of the max_allocno pseudo regs not allocated, 1428 or it is or has a hardware reg. First handle the pseudo-regs. */ 1429 if (regno >= FIRST_PSEUDO_REGISTER) 1430 { 1431 if (reg_allocno[regno] >= 0) 1432 record_one_conflict (regno); 1433 } 1434 1435 if (reg_renumber[regno] >= 0) 1436 regno = reg_renumber[regno]; 1437 1438 /* Handle hardware regs (and pseudos allocated to hard regs). */ 1439 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno]) 1440 { 1441 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)); 1442 while (regno < last) 1443 { 1444 record_one_conflict (regno); 1445 regno++; 1446 } 1447 } 1448} 1449 1450/* Mark REG as being dead (following the insn being scanned now). 1451 Store a 0 in regs_live or allocnos_live for this register. */ 1452 1453static void 1454mark_reg_death (reg) 1455 rtx reg; 1456{ 1457 register int regno = REGNO (reg); 1458 1459 /* Either this is one of the max_allocno pseudo regs not allocated, 1460 or it is a hardware reg. First handle the pseudo-regs. */ 1461 if (regno >= FIRST_PSEUDO_REGISTER) 1462 { 1463 if (reg_allocno[regno] >= 0) 1464 CLEAR_ALLOCNO_LIVE (reg_allocno[regno]); 1465 } 1466 1467 /* For pseudo reg, see if it has been assigned a hardware reg. */ 1468 if (reg_renumber[regno] >= 0) 1469 regno = reg_renumber[regno]; 1470 1471 /* Handle hardware regs (and pseudos allocated to hard regs). */ 1472 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno]) 1473 { 1474 /* Pseudo regs already assigned hardware regs are treated 1475 almost the same as explicit hardware regs. */ 1476 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)); 1477 while (regno < last) 1478 { 1479 CLEAR_HARD_REG_BIT (hard_regs_live, regno); 1480 regno++; 1481 } 1482 } 1483} 1484 1485/* Mark hard reg REGNO as currently live, assuming machine mode MODE 1486 for the value stored in it. MODE determines how many consecutive 1487 registers are actually in use. Do not record conflicts; 1488 it is assumed that the caller will do that. */ 1489 1490static void 1491mark_reg_live_nc (regno, mode) 1492 register int regno; 1493 enum machine_mode mode; 1494{ 1495 register int last = regno + HARD_REGNO_NREGS (regno, mode); 1496 while (regno < last) 1497 { 1498 SET_HARD_REG_BIT (hard_regs_live, regno); 1499 regno++; 1500 } 1501} 1502 1503/* Try to set a preference for an allocno to a hard register. 1504 We are passed DEST and SRC which are the operands of a SET. It is known 1505 that SRC is a register. If SRC or the first operand of SRC is a register, 1506 try to set a preference. If one of the two is a hard register and the other 1507 is a pseudo-register, mark the preference. 1508 1509 Note that we are not as aggressive as local-alloc in trying to tie a 1510 pseudo-register to a hard register. */ 1511 1512static void 1513set_preference (dest, src) 1514 rtx dest, src; 1515{ 1516 int src_regno, dest_regno; 1517 /* Amount to add to the hard regno for SRC, or subtract from that for DEST, 1518 to compensate for subregs in SRC or DEST. */ 1519 int offset = 0; 1520 int i; 1521 int copy = 1; 1522 1523 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e') 1524 src = XEXP (src, 0), copy = 0; 1525 1526 /* Get the reg number for both SRC and DEST. 1527 If neither is a reg, give up. */ 1528 1529 if (GET_CODE (src) == REG) 1530 src_regno = REGNO (src); 1531 else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG) 1532 { 1533 src_regno = REGNO (SUBREG_REG (src)); 1534 offset += SUBREG_WORD (src); 1535 } 1536 else 1537 return; 1538 1539 if (GET_CODE (dest) == REG) 1540 dest_regno = REGNO (dest); 1541 else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG) 1542 { 1543 dest_regno = REGNO (SUBREG_REG (dest)); 1544 offset -= SUBREG_WORD (dest); 1545 } 1546 else 1547 return; 1548 1549 /* Convert either or both to hard reg numbers. */ 1550 1551 if (reg_renumber[src_regno] >= 0) 1552 src_regno = reg_renumber[src_regno]; 1553 1554 if (reg_renumber[dest_regno] >= 0) 1555 dest_regno = reg_renumber[dest_regno]; 1556 1557 /* Now if one is a hard reg and the other is a global pseudo 1558 then give the other a preference. */ 1559 1560 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER 1561 && reg_allocno[src_regno] >= 0) 1562 { 1563 dest_regno -= offset; 1564 if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER) 1565 { 1566 if (copy) 1567 SET_REGBIT (hard_reg_copy_preferences, 1568 reg_allocno[src_regno], dest_regno); 1569 1570 SET_REGBIT (hard_reg_preferences, 1571 reg_allocno[src_regno], dest_regno); 1572 for (i = dest_regno; 1573 i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest)); 1574 i++) 1575 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i); 1576 } 1577 } 1578 1579 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER 1580 && reg_allocno[dest_regno] >= 0) 1581 { 1582 src_regno += offset; 1583 if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER) 1584 { 1585 if (copy) 1586 SET_REGBIT (hard_reg_copy_preferences, 1587 reg_allocno[dest_regno], src_regno); 1588 1589 SET_REGBIT (hard_reg_preferences, 1590 reg_allocno[dest_regno], src_regno); 1591 for (i = src_regno; 1592 i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src)); 1593 i++) 1594 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i); 1595 } 1596 } 1597} 1598 1599/* Indicate that hard register number FROM was eliminated and replaced with 1600 an offset from hard register number TO. The status of hard registers live 1601 at the start of a basic block is updated by replacing a use of FROM with 1602 a use of TO. */ 1603 1604void 1605mark_elimination (from, to) 1606 int from, to; 1607{ 1608 int i; 1609 1610 for (i = 0; i < n_basic_blocks; i++) 1611 { 1612 register regset r = BASIC_BLOCK (i)->global_live_at_start; 1613 if (REGNO_REG_SET_P (r, from)) 1614 { 1615 CLEAR_REGNO_REG_SET (r, from); 1616 SET_REGNO_REG_SET (r, to); 1617 } 1618 } 1619} 1620 1621/* Used for communication between the following functions. Holds the 1622 current life information. */ 1623static regset live_relevant_regs; 1624 1625/* Record in live_relevant_regs that register REG became live. This 1626 is called via note_stores. */ 1627static void 1628reg_becomes_live (reg, setter) 1629 rtx reg; 1630 rtx setter ATTRIBUTE_UNUSED; 1631{ 1632 int regno; 1633 1634 if (GET_CODE (reg) == SUBREG) 1635 reg = SUBREG_REG (reg); 1636 1637 if (GET_CODE (reg) != REG) 1638 return; 1639 1640 regno = REGNO (reg); 1641 if (regno < FIRST_PSEUDO_REGISTER) 1642 { 1643 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg)); 1644 while (nregs-- > 0) 1645 SET_REGNO_REG_SET (live_relevant_regs, regno++); 1646 } 1647 else if (reg_renumber[regno] >= 0) 1648 SET_REGNO_REG_SET (live_relevant_regs, regno); 1649} 1650 1651/* Record in live_relevant_regs that register REGNO died. */ 1652static void 1653reg_dies (regno, mode) 1654 int regno; 1655 enum machine_mode mode; 1656{ 1657 if (regno < FIRST_PSEUDO_REGISTER) 1658 { 1659 int nregs = HARD_REGNO_NREGS (regno, mode); 1660 while (nregs-- > 0) 1661 CLEAR_REGNO_REG_SET (live_relevant_regs, regno++); 1662 } 1663 else 1664 CLEAR_REGNO_REG_SET (live_relevant_regs, regno); 1665} 1666 1667/* Walk the insns of the current function and build reload_insn_chain, 1668 and record register life information. */ 1669static void 1670build_insn_chain (first) 1671 rtx first; 1672{ 1673 struct insn_chain **p = &reload_insn_chain; 1674 struct insn_chain *prev = 0; 1675 int b = 0; 1676 1677 live_relevant_regs = ALLOCA_REG_SET (); 1678 1679 for (; first; first = NEXT_INSN (first)) 1680 { 1681 struct insn_chain *c; 1682 1683 if (first == BLOCK_HEAD (b)) 1684 { 1685 int i; 1686 CLEAR_REG_SET (live_relevant_regs); 1687 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1688 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, i) 1689 && ! TEST_HARD_REG_BIT (eliminable_regset, i)) 1690 SET_REGNO_REG_SET (live_relevant_regs, i); 1691 1692 for (; i < max_regno; i++) 1693 if (reg_renumber[i] >= 0 1694 && REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, i)) 1695 SET_REGNO_REG_SET (live_relevant_regs, i); 1696 } 1697 1698 if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER) 1699 { 1700 c = new_insn_chain (); 1701 c->prev = prev; 1702 prev = c; 1703 *p = c; 1704 p = &c->next; 1705 c->insn = first; 1706 c->block = b; 1707 1708 COPY_REG_SET (c->live_before, live_relevant_regs); 1709 1710 if (GET_RTX_CLASS (GET_CODE (first)) == 'i') 1711 { 1712 rtx link; 1713 1714 /* Mark the death of everything that dies in this instruction. */ 1715 1716 for (link = REG_NOTES (first); link; link = XEXP (link, 1)) 1717 if (REG_NOTE_KIND (link) == REG_DEAD 1718 && GET_CODE (XEXP (link, 0)) == REG) 1719 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0))); 1720 1721 /* Mark everything born in this instruction as live. */ 1722 1723 note_stores (PATTERN (first), reg_becomes_live); 1724 } 1725 1726 /* Remember which registers are live at the end of the insn, before 1727 killing those with REG_UNUSED notes. */ 1728 COPY_REG_SET (c->live_after, live_relevant_regs); 1729 1730 if (GET_RTX_CLASS (GET_CODE (first)) == 'i') 1731 { 1732 rtx link; 1733 1734 /* Mark anything that is set in this insn and then unused as dying. */ 1735 1736 for (link = REG_NOTES (first); link; link = XEXP (link, 1)) 1737 if (REG_NOTE_KIND (link) == REG_UNUSED 1738 && GET_CODE (XEXP (link, 0)) == REG) 1739 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0))); 1740 } 1741 } 1742 1743 if (first == BLOCK_END (b)) 1744 b++; 1745 1746 /* Stop after we pass the end of the last basic block. Verify that 1747 no real insns are after the end of the last basic block. 1748 1749 We may want to reorganize the loop somewhat since this test should 1750 always be the right exit test. */ 1751 if (b == n_basic_blocks) 1752 { 1753 for (first = NEXT_INSN (first) ; first; first = NEXT_INSN (first)) 1754 if (GET_RTX_CLASS (GET_CODE (first)) == 'i' 1755 && GET_CODE (PATTERN (first)) != USE) 1756 abort (); 1757 break; 1758 } 1759 } 1760 FREE_REG_SET (live_relevant_regs); 1761 *p = 0; 1762} 1763 1764/* Print debugging trace information if -greg switch is given, 1765 showing the information on which the allocation decisions are based. */ 1766 1767static void 1768dump_conflicts (file) 1769 FILE *file; 1770{ 1771 register int i; 1772 register int has_preferences; 1773 register int nregs; 1774 nregs = 0; 1775 for (i = 0; i < max_allocno; i++) 1776 { 1777 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0) 1778 continue; 1779 nregs++; 1780 } 1781 fprintf (file, ";; %d regs to allocate:", nregs); 1782 for (i = 0; i < max_allocno; i++) 1783 { 1784 int j; 1785 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0) 1786 continue; 1787 fprintf (file, " %d", allocno_reg[allocno_order[i]]); 1788 for (j = 0; j < max_regno; j++) 1789 if (reg_allocno[j] == allocno_order[i] 1790 && j != allocno_reg[allocno_order[i]]) 1791 fprintf (file, "+%d", j); 1792 if (allocno_size[allocno_order[i]] != 1) 1793 fprintf (file, " (%d)", allocno_size[allocno_order[i]]); 1794 } 1795 fprintf (file, "\n"); 1796 1797 for (i = 0; i < max_allocno; i++) 1798 { 1799 register int j; 1800 fprintf (file, ";; %d conflicts:", allocno_reg[i]); 1801 for (j = 0; j < max_allocno; j++) 1802 if (CONFLICTP (i, j) || CONFLICTP (j, i)) 1803 fprintf (file, " %d", allocno_reg[j]); 1804 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++) 1805 if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j)) 1806 fprintf (file, " %d", j); 1807 fprintf (file, "\n"); 1808 1809 has_preferences = 0; 1810 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++) 1811 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j)) 1812 has_preferences = 1; 1813 1814 if (! has_preferences) 1815 continue; 1816 fprintf (file, ";; %d preferences:", allocno_reg[i]); 1817 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++) 1818 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j)) 1819 fprintf (file, " %d", j); 1820 fprintf (file, "\n"); 1821 } 1822 fprintf (file, "\n"); 1823} 1824 1825void 1826dump_global_regs (file) 1827 FILE *file; 1828{ 1829 register int i, j; 1830 1831 fprintf (file, ";; Register dispositions:\n"); 1832 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++) 1833 if (reg_renumber[i] >= 0) 1834 { 1835 fprintf (file, "%d in %d ", i, reg_renumber[i]); 1836 if (++j % 6 == 0) 1837 fprintf (file, "\n"); 1838 } 1839 1840 fprintf (file, "\n\n;; Hard regs used: "); 1841 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1842 if (regs_ever_live[i]) 1843 fprintf (file, " %d", i); 1844 fprintf (file, "\n\n"); 1845} 1846