1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 1988, 1991, 1994, 1996, 1997, 1998,
3 1999, 2000, 2002, 2003 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
25 #include "coretypes.h"
29 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "insn-config.h"
41 /* This pass of the compiler performs global register allocation.
42 It assigns hard register numbers to all the pseudo registers
43 that were not handled in local_alloc. Assignments are recorded
44 in the vector reg_renumber, not by changing the rtl code.
45 (Such changes are made by final). The entry point is
46 the function global_alloc.
48 After allocation is complete, the reload pass is run as a subroutine
49 of this pass, so that when a pseudo reg loses its hard reg due to
50 spilling it is possible to make a second attempt to find a hard
51 reg for it. The reload pass is independent in other respects
52 and it is run even when stupid register allocation is in use.
54 1. Assign allocation-numbers (allocnos) to the pseudo-registers
55 still needing allocations and to the pseudo-registers currently
56 allocated by local-alloc which may be spilled by reload.
57 Set up tables reg_allocno and allocno_reg to map
58 reg numbers to allocnos and vice versa.
59 max_allocno gets the number of allocnos in use.
61 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
62 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
63 for conflicts between allocnos and explicit hard register use
64 (which includes use of pseudo-registers allocated by local_alloc).
66 3. For each basic block
67 walk forward through the block, recording which
68 pseudo-registers and which hardware registers are live.
69 Build the conflict matrix between the pseudo-registers
70 and another of pseudo-registers versus hardware registers.
71 Also record the preferred hardware registers
72 for each pseudo-register.
74 4. Sort a table of the allocnos into order of
75 desirability of the variables.
77 5. Allocate the variables in that order; each if possible into
78 a preferred register, else into another register. */
80 /* Number of pseudo-registers which are candidates for allocation. */
82 static int max_allocno
;
84 /* Indexed by (pseudo) reg number, gives the allocno, or -1
85 for pseudo registers which are not to be allocated. */
87 static int *reg_allocno
;
92 /* Gives the number of consecutive hard registers needed by that
96 /* Number of calls crossed by each allocno. */
99 /* Number of calls that might throw crossed by each allocno. */
100 int throwing_calls_crossed
;
102 /* Number of refs to each allocno. */
105 /* Frequency of uses of each allocno. */
108 /* Guess at live length of each allocno.
109 This is actually the max of the live lengths of the regs. */
112 /* Set of hard regs conflicting with allocno N. */
114 HARD_REG_SET hard_reg_conflicts
;
116 /* Set of hard regs preferred by allocno N.
117 This is used to make allocnos go into regs that are copied to or from them,
118 when possible, to reduce register shuffling. */
120 HARD_REG_SET hard_reg_preferences
;
122 /* Similar, but just counts register preferences made in simple copy
123 operations, rather than arithmetic. These are given priority because
124 we can always eliminate an insn by using these, but using a register
125 in the above list won't always eliminate an insn. */
127 HARD_REG_SET hard_reg_copy_preferences
;
129 /* Similar to hard_reg_preferences, but includes bits for subsequent
130 registers when an allocno is multi-word. The above variable is used for
131 allocation while this is used to build reg_someone_prefers, below. */
133 HARD_REG_SET hard_reg_full_preferences
;
135 /* Set of hard registers that some later allocno has a preference for. */
137 HARD_REG_SET regs_someone_prefers
;
140 /* Set to true if allocno can't be allocated in the stack register. */
145 static struct allocno
*allocno
;
147 /* A vector of the integers from 0 to max_allocno-1,
148 sorted in the order of first-to-be-allocated first. */
150 static int *allocno_order
;
152 /* Indexed by (pseudo) reg number, gives the number of another
153 lower-numbered pseudo reg which can share a hard reg with this pseudo
154 *even if the two pseudos would otherwise appear to conflict*. */
156 static int *reg_may_share
;
158 /* Define the number of bits in each element of `conflicts' and what
159 type that element has. We use the largest integer format on the
162 #define INT_BITS HOST_BITS_PER_WIDE_INT
163 #define INT_TYPE HOST_WIDE_INT
165 /* max_allocno by max_allocno array of bits,
166 recording whether two allocno's conflict (can't go in the same
169 `conflicts' is symmetric after the call to mirror_conflicts. */
171 static INT_TYPE
*conflicts
;
173 /* Number of ints require to hold max_allocno bits.
174 This is the length of a row in `conflicts'. */
176 static int allocno_row_words
;
178 /* Two macros to test or store 1 in an element of `conflicts'. */
180 #define CONFLICTP(I, J) \
181 (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS] \
182 & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS)))
184 /* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
186 #define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
190 INT_TYPE *p_ = (ALLOCNO_SET); \
192 for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
193 i_--, allocno_ += INT_BITS) \
195 unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
197 for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
205 /* This doesn't work for non-GNU C due to the way CODE is macro expanded. */
207 /* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to
208 the conflicting allocno, and execute CODE. This macro assumes that
209 mirror_conflicts has been run. */
210 #define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\
211 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\
215 /* Set of hard regs currently live (during scan of all insns). */
217 static HARD_REG_SET hard_regs_live
;
219 /* Set of registers that global-alloc isn't supposed to use. */
221 static HARD_REG_SET no_global_alloc_regs
;
223 /* Set of registers used so far. */
225 static HARD_REG_SET regs_used_so_far
;
227 /* Number of refs to each hard reg, as used by local alloc.
228 It is zero for a reg that contains global pseudos or is explicitly used. */
230 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
232 /* Frequency of uses of given hard reg. */
233 static int local_reg_freq
[FIRST_PSEUDO_REGISTER
];
235 /* Guess at live length of each hard reg, as used by local alloc.
236 This is actually the sum of the live lengths of the specific regs. */
238 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
240 /* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
241 element I, and hard register number J. */
243 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
245 /* Bit mask for allocnos live at current point in the scan. */
247 static INT_TYPE
*allocnos_live
;
249 /* Test, set or clear bit number I in allocnos_live,
250 a bit vector indexed by allocno. */
252 #define SET_ALLOCNO_LIVE(I) \
253 (allocnos_live[(unsigned) (I) / INT_BITS] \
254 |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
256 #define CLEAR_ALLOCNO_LIVE(I) \
257 (allocnos_live[(unsigned) (I) / INT_BITS] \
258 &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
260 /* This is turned off because it doesn't work right for DImode.
261 (And it is only used for DImode, so the other cases are worthless.)
262 The problem is that it isn't true that there is NO possibility of conflict;
263 only that there is no conflict if the two pseudos get the exact same regs.
264 If they were allocated with a partial overlap, there would be a conflict.
265 We can't safely turn off the conflict unless we have another way to
266 prevent the partial overlap.
268 Idea: change hard_reg_conflicts so that instead of recording which
269 hard regs the allocno may not overlap, it records where the allocno
270 may not start. Change both where it is used and where it is updated.
271 Then there is a way to record that (reg:DI 108) may start at 10
272 but not at 9 or 11. There is still the question of how to record
273 this semi-conflict between two pseudos. */
275 /* Reg pairs for which conflict after the current insn
276 is inhibited by a REG_NO_CONFLICT note.
277 If the table gets full, we ignore any other notes--that is conservative. */
278 #define NUM_NO_CONFLICT_PAIRS 4
279 /* Number of pairs in use in this insn. */
280 int n_no_conflict_pairs
;
281 static struct { int allocno1
, allocno2
;}
282 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
285 /* Record all regs that are set in any one insn.
286 Communication from mark_reg_{store,clobber} and global_conflicts. */
288 static rtx
*regs_set
;
289 static int n_regs_set
;
291 /* All registers that can be eliminated. */
293 static HARD_REG_SET eliminable_regset
;
295 static int allocno_compare (const void *, const void *);
296 static void global_conflicts (void);
297 static void mirror_conflicts (void);
298 static void expand_preferences (void);
299 static void prune_preferences (void);
300 static void find_reg (int, HARD_REG_SET
, int, int, int);
301 static void record_one_conflict (int);
302 static void record_conflicts (int *, int);
303 static void mark_reg_store (rtx
, rtx
, void *);
304 static void mark_reg_clobber (rtx
, rtx
, void *);
305 static void mark_reg_conflicts (rtx
);
306 static void mark_reg_death (rtx
);
307 static void mark_reg_live_nc (int, enum machine_mode
);
308 static void set_preference (rtx
, rtx
);
309 static void dump_conflicts (FILE *);
310 static void reg_becomes_live (rtx
, rtx
, void *);
311 static void reg_dies (int, enum machine_mode
, struct insn_chain
*);
313 /* Perform allocation of pseudo-registers not allocated by local_alloc.
314 FILE is a file to output debugging information on,
315 or zero if such output is not desired.
317 Return value is nonzero if reload failed
318 and we must not do any more for this function. */
321 global_alloc (FILE *file
)
324 #ifdef ELIMINABLE_REGS
325 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
328 = (! flag_omit_frame_pointer
329 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
330 || FRAME_POINTER_REQUIRED
);
337 /* A machine may have certain hard registers that
338 are safe to use only within a basic block. */
340 CLEAR_HARD_REG_SET (no_global_alloc_regs
);
342 /* Build the regset of all eliminable registers and show we can't use those
343 that we already know won't be eliminated. */
344 #ifdef ELIMINABLE_REGS
345 for (i
= 0; i
< ARRAY_SIZE (eliminables
); i
++)
348 = (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
349 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
));
351 if (!regs_asm_clobbered
[eliminables
[i
].from
])
353 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
356 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
358 else if (cannot_elim
)
359 error ("%s cannot be used in asm here",
360 reg_names
[eliminables
[i
].from
]);
362 regs_ever_live
[eliminables
[i
].from
] = 1;
364 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
365 if (!regs_asm_clobbered
[HARD_FRAME_POINTER_REGNUM
])
367 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
369 SET_HARD_REG_BIT (no_global_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
372 error ("%s cannot be used in asm here",
373 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
375 regs_ever_live
[HARD_FRAME_POINTER_REGNUM
] = 1;
379 if (!regs_asm_clobbered
[FRAME_POINTER_REGNUM
])
381 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
383 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
386 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
388 regs_ever_live
[FRAME_POINTER_REGNUM
] = 1;
391 /* Track which registers have already been used. Start with registers
392 explicitly in the rtl, then registers allocated by local register
395 CLEAR_HARD_REG_SET (regs_used_so_far
);
396 #ifdef LEAF_REGISTERS
397 /* If we are doing the leaf function optimization, and this is a leaf
398 function, it means that the registers that take work to save are those
399 that need a register window. So prefer the ones that can be used in
402 const char *cheap_regs
;
403 const char *const leaf_regs
= LEAF_REGISTERS
;
405 if (only_leaf_regs_used () && leaf_function_p ())
406 cheap_regs
= leaf_regs
;
408 cheap_regs
= call_used_regs
;
409 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
410 if (regs_ever_live
[i
] || cheap_regs
[i
])
411 SET_HARD_REG_BIT (regs_used_so_far
, i
);
414 /* We consider registers that do not have to be saved over calls as if
415 they were already used since there is no cost in using them. */
416 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
417 if (regs_ever_live
[i
] || call_used_regs
[i
])
418 SET_HARD_REG_BIT (regs_used_so_far
, i
);
421 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
422 if (reg_renumber
[i
] >= 0)
423 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
425 /* Establish mappings from register number to allocation number
426 and vice versa. In the process, count the allocnos. */
428 reg_allocno
= xmalloc (max_regno
* sizeof (int));
430 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
433 /* Initialize the shared-hard-reg mapping
434 from the list of pairs that may share. */
435 reg_may_share
= xcalloc (max_regno
, sizeof (int));
436 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
438 int r1
= REGNO (XEXP (x
, 0));
439 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
441 reg_may_share
[r1
] = r2
;
443 reg_may_share
[r2
] = r1
;
446 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
447 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
448 that we are supposed to refrain from putting in a hard reg.
449 -2 means do make an allocno but don't allocate it. */
450 if (REG_N_REFS (i
) != 0 && REG_LIVE_LENGTH (i
) != -1
451 /* Don't allocate pseudos that cross calls,
452 if this function receives a nonlocal goto. */
453 && (! current_function_has_nonlocal_label
454 || REG_N_CALLS_CROSSED (i
) == 0))
456 if (reg_renumber
[i
] < 0 && reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
457 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
459 reg_allocno
[i
] = max_allocno
++;
460 if (REG_LIVE_LENGTH (i
) == 0)
466 allocno
= xcalloc (max_allocno
, sizeof (struct allocno
));
468 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
469 if (reg_allocno
[i
] >= 0)
471 int num
= reg_allocno
[i
];
472 allocno
[num
].reg
= i
;
473 allocno
[num
].size
= PSEUDO_REGNO_SIZE (i
);
474 allocno
[num
].calls_crossed
+= REG_N_CALLS_CROSSED (i
);
475 allocno
[num
].throwing_calls_crossed
476 += REG_N_THROWING_CALLS_CROSSED (i
);
477 allocno
[num
].n_refs
+= REG_N_REFS (i
);
478 allocno
[num
].freq
+= REG_FREQ (i
);
479 if (allocno
[num
].live_length
< REG_LIVE_LENGTH (i
))
480 allocno
[num
].live_length
= REG_LIVE_LENGTH (i
);
483 /* Calculate amount of usage of each hard reg by pseudos
484 allocated by local-alloc. This is to see if we want to
486 memset (local_reg_live_length
, 0, sizeof local_reg_live_length
);
487 memset (local_reg_n_refs
, 0, sizeof local_reg_n_refs
);
488 memset (local_reg_freq
, 0, sizeof local_reg_freq
);
489 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
490 if (reg_renumber
[i
] >= 0)
492 int regno
= reg_renumber
[i
];
493 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (i
));
496 for (j
= regno
; j
< endregno
; j
++)
498 local_reg_n_refs
[j
] += REG_N_REFS (i
);
499 local_reg_freq
[j
] += REG_FREQ (i
);
500 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
504 /* We can't override local-alloc for a reg used not just by local-alloc. */
505 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
506 if (regs_ever_live
[i
])
507 local_reg_n_refs
[i
] = 0, local_reg_freq
[i
] = 0;
509 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
511 /* We used to use alloca here, but the size of what it would try to
512 allocate would occasionally cause it to exceed the stack limit and
513 cause unpredictable core dumps. Some examples were > 2Mb in size. */
514 conflicts
= xcalloc (max_allocno
* allocno_row_words
, sizeof (INT_TYPE
));
516 allocnos_live
= xmalloc (allocno_row_words
* sizeof (INT_TYPE
));
518 /* If there is work to be done (at least one reg to allocate),
519 perform global conflict analysis and allocate the regs. */
523 /* Scan all the insns and compute the conflicts among allocnos
524 and between allocnos and hard regs. */
530 /* Eliminate conflicts between pseudos and eliminable registers. If
531 the register is not eliminated, the pseudo won't really be able to
532 live in the eliminable register, so the conflict doesn't matter.
533 If we do eliminate the register, the conflict will no longer exist.
534 So in either case, we can ignore the conflict. Likewise for
537 for (i
= 0; i
< (size_t) max_allocno
; i
++)
539 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_conflicts
,
541 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_copy_preferences
,
543 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_preferences
,
547 /* Try to expand the preferences by merging them between allocnos. */
549 expand_preferences ();
551 /* Determine the order to allocate the remaining pseudo registers. */
553 allocno_order
= xmalloc (max_allocno
* sizeof (int));
554 for (i
= 0; i
< (size_t) max_allocno
; i
++)
555 allocno_order
[i
] = i
;
557 /* Default the size to 1, since allocno_compare uses it to divide by.
558 Also convert allocno_live_length of zero to -1. A length of zero
559 can occur when all the registers for that allocno have reg_live_length
560 equal to -2. In this case, we want to make an allocno, but not
561 allocate it. So avoid the divide-by-zero and set it to a low
564 for (i
= 0; i
< (size_t) max_allocno
; i
++)
566 if (allocno
[i
].size
== 0)
568 if (allocno
[i
].live_length
== 0)
569 allocno
[i
].live_length
= -1;
572 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
574 prune_preferences ();
577 dump_conflicts (file
);
579 /* Try allocating them, one by one, in that order,
580 except for parameters marked with reg_live_length[regno] == -2. */
582 for (i
= 0; i
< (size_t) max_allocno
; i
++)
583 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] < 0
584 && REG_LIVE_LENGTH (allocno
[allocno_order
[i
]].reg
) >= 0)
586 /* If we have more than one register class,
587 first try allocating in the class that is cheapest
588 for this pseudo-reg. If that fails, try any reg. */
589 if (N_REG_CLASSES
> 1)
591 find_reg (allocno_order
[i
], 0, 0, 0, 0);
592 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
595 if (reg_alternate_class (allocno
[allocno_order
[i
]].reg
) != NO_REGS
)
596 find_reg (allocno_order
[i
], 0, 1, 0, 0);
599 free (allocno_order
);
602 /* Do the reloads now while the allocno data still exist, so that we can
603 try to assign new hard regs to any pseudo regs that are spilled. */
605 #if 0 /* We need to eliminate regs even if there is no rtl code,
606 for the sake of debugging information. */
607 if (n_basic_blocks
> 0)
610 build_insn_chain (get_insns ());
611 retval
= reload (get_insns (), 1);
616 free (reg_may_share
);
619 free (allocnos_live
);
624 /* Sort predicate for ordering the allocnos.
625 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
628 allocno_compare (const void *v1p
, const void *v2p
)
630 int v1
= *(const int *)v1p
, v2
= *(const int *)v2p
;
631 /* Note that the quotient will never be bigger than
632 the value of floor_log2 times the maximum number of
633 times a register can occur in one insn (surely less than 100)
634 weighted by the frequency (maximally REG_FREQ_MAX).
635 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
637 = (((double) (floor_log2 (allocno
[v1
].n_refs
) * allocno
[v1
].freq
)
638 / allocno
[v1
].live_length
)
639 * (10000 / REG_FREQ_MAX
) * allocno
[v1
].size
);
641 = (((double) (floor_log2 (allocno
[v2
].n_refs
) * allocno
[v2
].freq
)
642 / allocno
[v2
].live_length
)
643 * (10000 / REG_FREQ_MAX
) * allocno
[v2
].size
);
647 /* If regs are equally good, sort by allocno,
648 so that the results of qsort leave nothing to chance. */
652 /* Scan the rtl code and record all conflicts and register preferences in the
653 conflict matrices and preference tables. */
656 global_conflicts (void)
661 int *block_start_allocnos
;
663 /* Make a vector that mark_reg_{store,clobber} will store in. */
664 regs_set
= xmalloc (max_parallel
* sizeof (rtx
) * 2);
666 block_start_allocnos
= xmalloc (max_allocno
* sizeof (int));
670 memset (allocnos_live
, 0, allocno_row_words
* sizeof (INT_TYPE
));
672 /* Initialize table of registers currently live
673 to the state at the beginning of this basic block.
674 This also marks the conflicts among hard registers
675 and any allocnos that are live.
677 For pseudo-regs, there is only one bit for each one
678 no matter how many hard regs it occupies.
679 This is ok; we know the size from PSEUDO_REGNO_SIZE.
680 For explicit hard regs, we cannot know the size that way
681 since one hard reg can be used with various sizes.
682 Therefore, we must require that all the hard regs
683 implicitly live as part of a multi-word hard reg
684 are explicitly marked in basic_block_live_at_start. */
687 regset old
= b
->global_live_at_start
;
690 REG_SET_TO_HARD_REG_SET (hard_regs_live
, old
);
691 EXECUTE_IF_SET_IN_REG_SET (old
, FIRST_PSEUDO_REGISTER
, i
,
693 int a
= reg_allocno
[i
];
696 SET_ALLOCNO_LIVE (a
);
697 block_start_allocnos
[ax
++] = a
;
699 else if ((a
= reg_renumber
[i
]) >= 0)
701 (a
, PSEUDO_REGNO_MODE (i
));
704 /* Record that each allocno now live conflicts with each hard reg
707 It is not necessary to mark any conflicts between pseudos as
708 this point, even for pseudos which are live at the start of
711 Given two pseudos X and Y and any point in the CFG P.
713 On any path to point P where X and Y are live one of the
714 following conditions must be true:
716 1. X is live at some instruction on the path that
719 2. Y is live at some instruction on the path that
722 3. Either X or Y is not evaluated on the path to P
723 (ie it is used uninitialized) and thus the
724 conflict can be ignored.
726 In cases #1 and #2 the conflict will be recorded when we
727 scan the instruction that makes either X or Y become live. */
728 record_conflicts (block_start_allocnos
, ax
);
730 /* Pseudos can't go in stack regs at the start of a basic block that
731 is reached by an abnormal edge. Likewise for call clobbered regs,
732 because because caller-save, fixup_abnormal_edges, and possibly
733 the table driven EH machinery are not quite ready to handle such
734 regs live across such edges. */
738 for (e
= b
->pred
; e
; e
= e
->pred_next
)
739 if (e
->flags
& EDGE_ABNORMAL
)
745 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, ax
,
747 allocno
[ax
].no_stack_reg
= 1;
749 for (ax
= FIRST_STACK_REG
; ax
<= LAST_STACK_REG
; ax
++)
750 record_one_conflict (ax
);
753 /* No need to record conflicts for call clobbered regs if we have
754 nonlocal labels around, as we don't ever try to allocate such
755 regs in this case. */
756 if (! current_function_has_nonlocal_label
)
757 for (ax
= 0; ax
< FIRST_PSEUDO_REGISTER
; ax
++)
758 if (call_used_regs
[ax
])
759 record_one_conflict (ax
);
766 /* Scan the code of this basic block, noting which allocnos
767 and hard regs are born or die. When one is born,
768 record a conflict with all others currently live. */
772 RTX_CODE code
= GET_CODE (insn
);
775 /* Make regs_set an empty set. */
779 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
784 for (link
= REG_NOTES (insn
);
785 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
786 link
= XEXP (link
, 1))
787 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
789 no_conflict_pairs
[i
].allocno1
790 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
791 no_conflict_pairs
[i
].allocno2
792 = reg_allocno
[REGNO (XEXP (link
, 0))];
797 /* Mark any registers clobbered by INSN as live,
798 so they conflict with the inputs. */
800 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
802 /* Mark any registers dead after INSN as dead now. */
804 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
805 if (REG_NOTE_KIND (link
) == REG_DEAD
)
806 mark_reg_death (XEXP (link
, 0));
808 /* Mark any registers set in INSN as live,
809 and mark them as conflicting with all other live regs.
810 Clobbers are processed again, so they conflict with
811 the registers that are set. */
813 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
816 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
817 if (REG_NOTE_KIND (link
) == REG_INC
)
818 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
821 /* If INSN has multiple outputs, then any reg that dies here
822 and is used inside of an output
823 must conflict with the other outputs.
825 It is unsafe to use !single_set here since it will ignore an
826 unused output. Just because an output is unused does not mean
827 the compiler can assume the side effect will not occur.
828 Consider if REG appears in the address of an output and we
829 reload the output. If we allocate REG to the same hard
830 register as an unused output we could set the hard register
831 before the output reload insn. */
832 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
833 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
834 if (REG_NOTE_KIND (link
) == REG_DEAD
)
836 int used_in_output
= 0;
838 rtx reg
= XEXP (link
, 0);
840 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
842 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
843 if (GET_CODE (set
) == SET
844 && GET_CODE (SET_DEST (set
)) != REG
845 && !rtx_equal_p (reg
, SET_DEST (set
))
846 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
850 mark_reg_conflicts (reg
);
853 /* Mark any registers set in INSN and then never used. */
855 while (n_regs_set
-- > 0)
857 rtx note
= find_regno_note (insn
, REG_UNUSED
,
858 REGNO (regs_set
[n_regs_set
]));
860 mark_reg_death (XEXP (note
, 0));
864 if (insn
== BB_END (b
))
866 insn
= NEXT_INSN (insn
);
871 free (block_start_allocnos
);
874 /* Expand the preference information by looking for cases where one allocno
875 dies in an insn that sets an allocno. If those two allocnos don't conflict,
876 merge any preferences between those allocnos. */
879 expand_preferences (void)
885 /* We only try to handle the most common cases here. Most of the cases
886 where this wins are reg-reg copies. */
888 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
890 && (set
= single_set (insn
)) != 0
891 && GET_CODE (SET_DEST (set
)) == REG
892 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
893 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
894 if (REG_NOTE_KIND (link
) == REG_DEAD
895 && GET_CODE (XEXP (link
, 0)) == REG
896 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
897 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
898 reg_allocno
[REGNO (XEXP (link
, 0))]))
900 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
901 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
903 if (XEXP (link
, 0) == SET_SRC (set
))
905 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_copy_preferences
,
906 allocno
[a2
].hard_reg_copy_preferences
);
907 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_copy_preferences
,
908 allocno
[a1
].hard_reg_copy_preferences
);
911 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_preferences
,
912 allocno
[a2
].hard_reg_preferences
);
913 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_preferences
,
914 allocno
[a1
].hard_reg_preferences
);
915 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_full_preferences
,
916 allocno
[a2
].hard_reg_full_preferences
);
917 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_full_preferences
,
918 allocno
[a1
].hard_reg_full_preferences
);
922 /* Prune the preferences for global registers to exclude registers that cannot
925 Compute `regs_someone_prefers', which is a bitmask of the hard registers
926 that are preferred by conflicting registers of lower priority. If possible,
927 we will avoid using these registers. */
930 prune_preferences (void)
934 int *allocno_to_order
= xmalloc (max_allocno
* sizeof (int));
936 /* Scan least most important to most important.
937 For each allocno, remove from preferences registers that cannot be used,
938 either because of conflicts or register type. Then compute all registers
939 preferred by each lower-priority register that conflicts. */
941 for (i
= max_allocno
- 1; i
>= 0; i
--)
945 num
= allocno_order
[i
];
946 allocno_to_order
[num
] = i
;
947 COPY_HARD_REG_SET (temp
, allocno
[num
].hard_reg_conflicts
);
949 if (allocno
[num
].calls_crossed
== 0)
950 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
952 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
954 IOR_COMPL_HARD_REG_SET
956 reg_class_contents
[(int) reg_preferred_class (allocno
[num
].reg
)]);
958 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, temp
);
959 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, temp
);
960 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_full_preferences
, temp
);
963 for (i
= max_allocno
- 1; i
>= 0; i
--)
965 /* Merge in the preferences of lower-priority registers (they have
966 already been pruned). If we also prefer some of those registers,
967 don't exclude them unless we are of a smaller size (in which case
968 we want to give the lower-priority allocno the first chance for
970 HARD_REG_SET temp
, temp2
;
973 num
= allocno_order
[i
];
975 CLEAR_HARD_REG_SET (temp
);
976 CLEAR_HARD_REG_SET (temp2
);
978 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ num
* allocno_row_words
,
981 if (allocno_to_order
[allocno2
] > i
)
983 if (allocno
[allocno2
].size
<= allocno
[num
].size
)
984 IOR_HARD_REG_SET (temp
,
985 allocno
[allocno2
].hard_reg_full_preferences
);
987 IOR_HARD_REG_SET (temp2
,
988 allocno
[allocno2
].hard_reg_full_preferences
);
992 AND_COMPL_HARD_REG_SET (temp
, allocno
[num
].hard_reg_full_preferences
);
993 IOR_HARD_REG_SET (temp
, temp2
);
994 COPY_HARD_REG_SET (allocno
[num
].regs_someone_prefers
, temp
);
996 free (allocno_to_order
);
999 /* Assign a hard register to allocno NUM; look for one that is the beginning
1000 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
1001 The registers marked in PREFREGS are tried first.
1003 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
1004 be used for this allocation.
1006 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
1007 Otherwise ignore that preferred class and use the alternate class.
1009 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
1010 will have to be saved and restored at calls.
1012 RETRYING is nonzero if this is called from retry_global_alloc.
1014 If we find one, record it in reg_renumber.
1015 If not, do nothing. */
1018 find_reg (int num
, HARD_REG_SET losers
, int alt_regs_p
, int accept_call_clobbered
, int retrying
)
1020 int i
, best_reg
, pass
;
1021 HARD_REG_SET used
, used1
, used2
;
1023 enum reg_class
class = (alt_regs_p
1024 ? reg_alternate_class (allocno
[num
].reg
)
1025 : reg_preferred_class (allocno
[num
].reg
));
1026 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno
[num
].reg
);
1028 if (accept_call_clobbered
)
1029 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
1030 else if (allocno
[num
].calls_crossed
== 0)
1031 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
1033 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
1035 /* Some registers should not be allocated in global-alloc. */
1036 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
1038 IOR_HARD_REG_SET (used1
, losers
);
1040 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
1041 COPY_HARD_REG_SET (used2
, used1
);
1043 IOR_HARD_REG_SET (used1
, allocno
[num
].hard_reg_conflicts
);
1045 #ifdef CANNOT_CHANGE_MODE_CLASS
1046 cannot_change_mode_set_regs (&used1
, mode
, allocno
[num
].reg
);
1049 /* Try each hard reg to see if it fits. Do this in two passes.
1050 In the first pass, skip registers that are preferred by some other pseudo
1051 to give it a better chance of getting one of those registers. Only if
1052 we can't get a register when excluding those do we take one of them.
1053 However, we never allocate a register for the first time in pass 0. */
1055 COPY_HARD_REG_SET (used
, used1
);
1056 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
1057 IOR_HARD_REG_SET (used
, allocno
[num
].regs_someone_prefers
);
1060 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
1061 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
1065 COPY_HARD_REG_SET (used
, used1
);
1066 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1068 #ifdef REG_ALLOC_ORDER
1069 int regno
= reg_alloc_order
[i
];
1073 if (! TEST_HARD_REG_BIT (used
, regno
)
1074 && HARD_REGNO_MODE_OK (regno
, mode
)
1075 && (allocno
[num
].calls_crossed
== 0
1076 || accept_call_clobbered
1077 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
)))
1080 int lim
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1083 && ! TEST_HARD_REG_BIT (used
, j
));
1090 #ifndef REG_ALLOC_ORDER
1091 i
= j
; /* Skip starting points we know will lose */
1097 /* See if there is a preferred register with the same class as the register
1098 we allocated above. Making this restriction prevents register
1099 preferencing from creating worse register allocation.
1101 Remove from the preferred registers and conflicting registers. Note that
1102 additional conflicts may have been added after `prune_preferences' was
1105 First do this for those register with copy preferences, then all
1106 preferred registers. */
1108 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, used
);
1109 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_copy_preferences
,
1110 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
1114 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1115 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_copy_preferences
, i
)
1116 && HARD_REGNO_MODE_OK (i
, mode
)
1117 && (allocno
[num
].calls_crossed
== 0
1118 || accept_call_clobbered
1119 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1120 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1121 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1122 REGNO_REG_CLASS (best_reg
))
1123 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1124 REGNO_REG_CLASS (i
))))
1127 int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1130 && ! TEST_HARD_REG_BIT (used
, j
)
1131 && (REGNO_REG_CLASS (j
)
1132 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1133 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1134 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1135 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1136 REGNO_REG_CLASS (j
))));
1147 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, used
);
1148 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_preferences
,
1149 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1153 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1154 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_preferences
, i
)
1155 && HARD_REGNO_MODE_OK (i
, mode
)
1156 && (allocno
[num
].calls_crossed
== 0
1157 || accept_call_clobbered
1158 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1159 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1160 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1161 REGNO_REG_CLASS (best_reg
))
1162 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1163 REGNO_REG_CLASS (i
))))
1166 int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1169 && ! TEST_HARD_REG_BIT (used
, j
)
1170 && (REGNO_REG_CLASS (j
)
1171 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1172 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1173 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1174 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1175 REGNO_REG_CLASS (j
))));
1186 /* If we haven't succeeded yet, try with caller-saves.
1187 We need not check to see if the current function has nonlocal
1188 labels because we don't put any pseudos that are live over calls in
1189 registers in that case. */
1191 if (flag_caller_saves
&& best_reg
< 0)
1193 /* Did not find a register. If it would be profitable to
1194 allocate a call-clobbered register and save and restore it
1195 around calls, do that. Don't do this if it crosses any calls
1196 that might throw. */
1197 if (! accept_call_clobbered
1198 && allocno
[num
].calls_crossed
!= 0
1199 && allocno
[num
].throwing_calls_crossed
== 0
1200 && CALLER_SAVE_PROFITABLE (allocno
[num
].n_refs
,
1201 allocno
[num
].calls_crossed
))
1203 HARD_REG_SET new_losers
;
1205 CLEAR_HARD_REG_SET (new_losers
);
1207 COPY_HARD_REG_SET (new_losers
, losers
);
1209 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1210 find_reg (num
, new_losers
, alt_regs_p
, 1, retrying
);
1211 if (reg_renumber
[allocno
[num
].reg
] >= 0)
1213 caller_save_needed
= 1;
1219 /* If we haven't succeeded yet,
1220 see if some hard reg that conflicts with us
1221 was utilized poorly by local-alloc.
1222 If so, kick out the regs that were put there by local-alloc
1223 so we can use it instead. */
1224 if (best_reg
< 0 && !retrying
1225 /* Let's not bother with multi-reg allocnos. */
1226 && allocno
[num
].size
== 1)
1228 /* Count from the end, to find the least-used ones first. */
1229 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1231 #ifdef REG_ALLOC_ORDER
1232 int regno
= reg_alloc_order
[i
];
1237 if (local_reg_n_refs
[regno
] != 0
1238 /* Don't use a reg no good for this pseudo. */
1239 && ! TEST_HARD_REG_BIT (used2
, regno
)
1240 && HARD_REGNO_MODE_OK (regno
, mode
)
1241 /* The code below assumes that we need only a single
1242 register, but the check of allocno[num].size above
1243 was not enough. Sometimes we need more than one
1244 register for a single-word value. */
1245 && HARD_REGNO_NREGS (regno
, mode
) == 1
1246 && (allocno
[num
].calls_crossed
== 0
1247 || accept_call_clobbered
1248 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
))
1249 #ifdef CANNOT_CHANGE_MODE_CLASS
1250 && ! invalid_mode_change_p (regno
, REGNO_REG_CLASS (regno
),
1254 && (!allocno
[num
].no_stack_reg
1255 || regno
< FIRST_STACK_REG
|| regno
> LAST_STACK_REG
)
1259 /* We explicitly evaluate the divide results into temporary
1260 variables so as to avoid excess precision problems that occur
1261 on an i386-unknown-sysv4.2 (unixware) host. */
1263 double tmp1
= ((double) local_reg_freq
[regno
]
1264 / local_reg_live_length
[regno
]);
1265 double tmp2
= ((double) allocno
[num
].freq
1266 / allocno
[num
].live_length
);
1270 /* Hard reg REGNO was used less in total by local regs
1271 than it would be used by this one allocno! */
1273 for (k
= 0; k
< max_regno
; k
++)
1274 if (reg_renumber
[k
] >= 0)
1276 int r
= reg_renumber
[k
];
1278 = r
+ HARD_REGNO_NREGS (r
, PSEUDO_REGNO_MODE (k
));
1280 if (regno
>= r
&& regno
< endregno
)
1281 reg_renumber
[k
] = -1;
1291 /* Did we find a register? */
1296 HARD_REG_SET this_reg
;
1298 /* Yes. Record it as the hard register of this pseudo-reg. */
1299 reg_renumber
[allocno
[num
].reg
] = best_reg
;
1300 /* Also of any pseudo-regs that share with it. */
1301 if (reg_may_share
[allocno
[num
].reg
])
1302 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1303 if (reg_allocno
[j
] == num
)
1304 reg_renumber
[j
] = best_reg
;
1306 /* Make a set of the hard regs being allocated. */
1307 CLEAR_HARD_REG_SET (this_reg
);
1308 lim
= best_reg
+ HARD_REGNO_NREGS (best_reg
, mode
);
1309 for (j
= best_reg
; j
< lim
; j
++)
1311 SET_HARD_REG_BIT (this_reg
, j
);
1312 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1313 /* This is no longer a reg used just by local regs. */
1314 local_reg_n_refs
[j
] = 0;
1315 local_reg_freq
[j
] = 0;
1317 /* For each other pseudo-reg conflicting with this one,
1318 mark it as conflicting with the hard regs this one occupies. */
1320 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ lim
* allocno_row_words
, j
,
1322 IOR_HARD_REG_SET (allocno
[j
].hard_reg_conflicts
, this_reg
);
1327 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1328 Perhaps it had previously seemed not worth a hard reg,
1329 or perhaps its old hard reg has been commandeered for reloads.
1330 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1331 they do not appear to be allocated.
1332 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1335 retry_global_alloc (int regno
, HARD_REG_SET forbidden_regs
)
1337 int alloc_no
= reg_allocno
[regno
];
1340 /* If we have more than one register class,
1341 first try allocating in the class that is cheapest
1342 for this pseudo-reg. If that fails, try any reg. */
1343 if (N_REG_CLASSES
> 1)
1344 find_reg (alloc_no
, forbidden_regs
, 0, 0, 1);
1345 if (reg_renumber
[regno
] < 0
1346 && reg_alternate_class (regno
) != NO_REGS
)
1347 find_reg (alloc_no
, forbidden_regs
, 1, 0, 1);
1349 /* If we found a register, modify the RTL for the register to
1350 show the hard register, and mark that register live. */
1351 if (reg_renumber
[regno
] >= 0)
1353 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1354 mark_home_live (regno
);
1359 /* Record a conflict between register REGNO
1360 and everything currently live.
1361 REGNO must not be a pseudo reg that was allocated
1362 by local_alloc; such numbers must be translated through
1363 reg_renumber before calling here. */
1366 record_one_conflict (int regno
)
1370 if (regno
< FIRST_PSEUDO_REGISTER
)
1371 /* When a hard register becomes live,
1372 record conflicts with live pseudo regs. */
1373 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, j
,
1375 SET_HARD_REG_BIT (allocno
[j
].hard_reg_conflicts
, regno
);
1378 /* When a pseudo-register becomes live,
1379 record conflicts first with hard regs,
1380 then with other pseudo regs. */
1382 int ialloc
= reg_allocno
[regno
];
1383 int ialloc_prod
= ialloc
* allocno_row_words
;
1385 IOR_HARD_REG_SET (allocno
[ialloc
].hard_reg_conflicts
, hard_regs_live
);
1386 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1390 for (k
= 0; k
< n_no_conflict_pairs
; k
++)
1391 if (! ((j
== no_conflict_pairs
[k
].allocno1
1392 && ialloc
== no_conflict_pairs
[k
].allocno2
)
1394 (j
== no_conflict_pairs
[k
].allocno2
1395 && ialloc
== no_conflict_pairs
[k
].allocno1
)))
1397 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1402 /* Record all allocnos currently live as conflicting
1403 with all hard regs currently live.
1405 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1406 are currently live. Their bits are also flagged in allocnos_live. */
1409 record_conflicts (int *allocno_vec
, int len
)
1412 IOR_HARD_REG_SET (allocno
[allocno_vec
[len
]].hard_reg_conflicts
,
1416 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1418 mirror_conflicts (void)
1421 int rw
= allocno_row_words
;
1422 int rwb
= rw
* INT_BITS
;
1423 INT_TYPE
*p
= conflicts
;
1424 INT_TYPE
*q0
= conflicts
, *q1
, *q2
;
1425 unsigned INT_TYPE mask
;
1427 for (i
= max_allocno
- 1, mask
= 1; i
>= 0; i
--, mask
<<= 1)
1434 for (j
= allocno_row_words
- 1, q1
= q0
; j
>= 0; j
--, q1
+= rwb
)
1436 unsigned INT_TYPE word
;
1438 for (word
= (unsigned INT_TYPE
) *p
++, q2
= q1
; word
;
1439 word
>>= 1, q2
+= rw
)
1448 /* Handle the case where REG is set by the insn being scanned,
1449 during the forward scan to accumulate conflicts.
1450 Store a 1 in regs_live or allocnos_live for this register, record how many
1451 consecutive hardware registers it actually needs,
1452 and record a conflict with all other registers already live.
1454 Note that even if REG does not remain alive after this insn,
1455 we must mark it here as live, to ensure a conflict between
1456 REG and any other regs set in this insn that really do live.
1457 This is because those other regs could be considered after this.
1459 REG might actually be something other than a register;
1460 if so, we do nothing.
1462 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1463 a REG_INC note was found for it). */
1466 mark_reg_store (rtx reg
, rtx setter
, void *data ATTRIBUTE_UNUSED
)
1470 if (GET_CODE (reg
) == SUBREG
)
1471 reg
= SUBREG_REG (reg
);
1473 if (GET_CODE (reg
) != REG
)
1476 regs_set
[n_regs_set
++] = reg
;
1478 if (setter
&& GET_CODE (setter
) != CLOBBER
)
1479 set_preference (reg
, SET_SRC (setter
));
1481 regno
= REGNO (reg
);
1483 /* Either this is one of the max_allocno pseudo regs not allocated,
1484 or it is or has a hardware reg. First handle the pseudo-regs. */
1485 if (regno
>= FIRST_PSEUDO_REGISTER
)
1487 if (reg_allocno
[regno
] >= 0)
1489 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1490 record_one_conflict (regno
);
1494 if (reg_renumber
[regno
] >= 0)
1495 regno
= reg_renumber
[regno
];
1497 /* Handle hardware regs (and pseudos allocated to hard regs). */
1498 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1500 int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1501 while (regno
< last
)
1503 record_one_conflict (regno
);
1504 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1510 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1513 mark_reg_clobber (rtx reg
, rtx setter
, void *data ATTRIBUTE_UNUSED
)
1515 if (GET_CODE (setter
) == CLOBBER
)
1516 mark_reg_store (reg
, setter
, data
);
1519 /* Record that REG has conflicts with all the regs currently live.
1520 Do not mark REG itself as live. */
1523 mark_reg_conflicts (rtx reg
)
1527 if (GET_CODE (reg
) == SUBREG
)
1528 reg
= SUBREG_REG (reg
);
1530 if (GET_CODE (reg
) != REG
)
1533 regno
= REGNO (reg
);
1535 /* Either this is one of the max_allocno pseudo regs not allocated,
1536 or it is or has a hardware reg. First handle the pseudo-regs. */
1537 if (regno
>= FIRST_PSEUDO_REGISTER
)
1539 if (reg_allocno
[regno
] >= 0)
1540 record_one_conflict (regno
);
1543 if (reg_renumber
[regno
] >= 0)
1544 regno
= reg_renumber
[regno
];
1546 /* Handle hardware regs (and pseudos allocated to hard regs). */
1547 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1549 int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1550 while (regno
< last
)
1552 record_one_conflict (regno
);
1558 /* Mark REG as being dead (following the insn being scanned now).
1559 Store a 0 in regs_live or allocnos_live for this register. */
1562 mark_reg_death (rtx reg
)
1564 int regno
= REGNO (reg
);
1566 /* Either this is one of the max_allocno pseudo regs not allocated,
1567 or it is a hardware reg. First handle the pseudo-regs. */
1568 if (regno
>= FIRST_PSEUDO_REGISTER
)
1570 if (reg_allocno
[regno
] >= 0)
1571 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1574 /* For pseudo reg, see if it has been assigned a hardware reg. */
1575 if (reg_renumber
[regno
] >= 0)
1576 regno
= reg_renumber
[regno
];
1578 /* Handle hardware regs (and pseudos allocated to hard regs). */
1579 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1581 /* Pseudo regs already assigned hardware regs are treated
1582 almost the same as explicit hardware regs. */
1583 int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1584 while (regno
< last
)
1586 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1592 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1593 for the value stored in it. MODE determines how many consecutive
1594 registers are actually in use. Do not record conflicts;
1595 it is assumed that the caller will do that. */
1598 mark_reg_live_nc (int regno
, enum machine_mode mode
)
1600 int last
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1601 while (regno
< last
)
1603 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1608 /* Try to set a preference for an allocno to a hard register.
1609 We are passed DEST and SRC which are the operands of a SET. It is known
1610 that SRC is a register. If SRC or the first operand of SRC is a register,
1611 try to set a preference. If one of the two is a hard register and the other
1612 is a pseudo-register, mark the preference.
1614 Note that we are not as aggressive as local-alloc in trying to tie a
1615 pseudo-register to a hard register. */
1618 set_preference (rtx dest
, rtx src
)
1620 unsigned int src_regno
, dest_regno
;
1621 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1622 to compensate for subregs in SRC or DEST. */
1627 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1628 src
= XEXP (src
, 0), copy
= 0;
1630 /* Get the reg number for both SRC and DEST.
1631 If neither is a reg, give up. */
1633 if (GET_CODE (src
) == REG
)
1634 src_regno
= REGNO (src
);
1635 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1637 src_regno
= REGNO (SUBREG_REG (src
));
1639 if (REGNO (SUBREG_REG (src
)) < FIRST_PSEUDO_REGISTER
)
1640 offset
+= subreg_regno_offset (REGNO (SUBREG_REG (src
)),
1641 GET_MODE (SUBREG_REG (src
)),
1645 offset
+= (SUBREG_BYTE (src
)
1646 / REGMODE_NATURAL_SIZE (GET_MODE (src
)));
1651 if (GET_CODE (dest
) == REG
)
1652 dest_regno
= REGNO (dest
);
1653 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1655 dest_regno
= REGNO (SUBREG_REG (dest
));
1657 if (REGNO (SUBREG_REG (dest
)) < FIRST_PSEUDO_REGISTER
)
1658 offset
-= subreg_regno_offset (REGNO (SUBREG_REG (dest
)),
1659 GET_MODE (SUBREG_REG (dest
)),
1663 offset
-= (SUBREG_BYTE (dest
)
1664 / REGMODE_NATURAL_SIZE (GET_MODE (dest
)));
1669 /* Convert either or both to hard reg numbers. */
1671 if (reg_renumber
[src_regno
] >= 0)
1672 src_regno
= reg_renumber
[src_regno
];
1674 if (reg_renumber
[dest_regno
] >= 0)
1675 dest_regno
= reg_renumber
[dest_regno
];
1677 /* Now if one is a hard reg and the other is a global pseudo
1678 then give the other a preference. */
1680 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1681 && reg_allocno
[src_regno
] >= 0)
1683 dest_regno
-= offset
;
1684 if (dest_regno
< FIRST_PSEUDO_REGISTER
)
1687 SET_REGBIT (hard_reg_copy_preferences
,
1688 reg_allocno
[src_regno
], dest_regno
);
1690 SET_REGBIT (hard_reg_preferences
,
1691 reg_allocno
[src_regno
], dest_regno
);
1692 for (i
= dest_regno
;
1693 i
< dest_regno
+ HARD_REGNO_NREGS (dest_regno
, GET_MODE (dest
));
1695 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1699 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1700 && reg_allocno
[dest_regno
] >= 0)
1702 src_regno
+= offset
;
1703 if (src_regno
< FIRST_PSEUDO_REGISTER
)
1706 SET_REGBIT (hard_reg_copy_preferences
,
1707 reg_allocno
[dest_regno
], src_regno
);
1709 SET_REGBIT (hard_reg_preferences
,
1710 reg_allocno
[dest_regno
], src_regno
);
1712 i
< src_regno
+ HARD_REGNO_NREGS (src_regno
, GET_MODE (src
));
1714 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1719 /* Indicate that hard register number FROM was eliminated and replaced with
1720 an offset from hard register number TO. The status of hard registers live
1721 at the start of a basic block is updated by replacing a use of FROM with
1725 mark_elimination (int from
, int to
)
1731 regset r
= bb
->global_live_at_start
;
1732 if (REGNO_REG_SET_P (r
, from
))
1734 CLEAR_REGNO_REG_SET (r
, from
);
1735 SET_REGNO_REG_SET (r
, to
);
1740 /* Used for communication between the following functions. Holds the
1741 current life information. */
1742 static regset live_relevant_regs
;
1744 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1745 This is called via note_stores. */
1747 reg_becomes_live (rtx reg
, rtx setter ATTRIBUTE_UNUSED
, void *regs_set
)
1751 if (GET_CODE (reg
) == SUBREG
)
1752 reg
= SUBREG_REG (reg
);
1754 if (GET_CODE (reg
) != REG
)
1757 regno
= REGNO (reg
);
1758 if (regno
< FIRST_PSEUDO_REGISTER
)
1760 int nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1763 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1764 if (! fixed_regs
[regno
])
1765 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1769 else if (reg_renumber
[regno
] >= 0)
1771 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1772 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1776 /* Record in live_relevant_regs that register REGNO died. */
1778 reg_dies (int regno
, enum machine_mode mode
, struct insn_chain
*chain
)
1780 if (regno
< FIRST_PSEUDO_REGISTER
)
1782 int nregs
= HARD_REGNO_NREGS (regno
, mode
);
1785 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1786 if (! fixed_regs
[regno
])
1787 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1793 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1794 if (reg_renumber
[regno
] >= 0)
1795 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1799 /* Walk the insns of the current function and build reload_insn_chain,
1800 and record register life information. */
1802 build_insn_chain (rtx first
)
1804 struct insn_chain
**p
= &reload_insn_chain
;
1805 struct insn_chain
*prev
= 0;
1806 basic_block b
= ENTRY_BLOCK_PTR
->next_bb
;
1807 regset_head live_relevant_regs_head
;
1809 live_relevant_regs
= INITIALIZE_REG_SET (live_relevant_regs_head
);
1811 for (; first
; first
= NEXT_INSN (first
))
1813 struct insn_chain
*c
;
1815 if (first
== BB_HEAD (b
))
1819 CLEAR_REG_SET (live_relevant_regs
);
1821 EXECUTE_IF_SET_IN_BITMAP
1822 (b
->global_live_at_start
, 0, i
,
1824 if (i
< FIRST_PSEUDO_REGISTER
1825 ? ! TEST_HARD_REG_BIT (eliminable_regset
, i
)
1826 : reg_renumber
[i
] >= 0)
1827 SET_REGNO_REG_SET (live_relevant_regs
, i
);
1831 if (GET_CODE (first
) != NOTE
&& GET_CODE (first
) != BARRIER
)
1833 c
= new_insn_chain ();
1839 c
->block
= b
->index
;
1845 /* Mark the death of everything that dies in this instruction. */
1847 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1848 if (REG_NOTE_KIND (link
) == REG_DEAD
1849 && GET_CODE (XEXP (link
, 0)) == REG
)
1850 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1853 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1855 /* Mark everything born in this instruction as live. */
1857 note_stores (PATTERN (first
), reg_becomes_live
,
1861 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1867 /* Mark anything that is set in this insn and then unused as dying. */
1869 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1870 if (REG_NOTE_KIND (link
) == REG_UNUSED
1871 && GET_CODE (XEXP (link
, 0)) == REG
)
1872 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1877 if (first
== BB_END (b
))
1880 /* Stop after we pass the end of the last basic block. Verify that
1881 no real insns are after the end of the last basic block.
1883 We may want to reorganize the loop somewhat since this test should
1884 always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if
1885 the previous real insn is a JUMP_INSN. */
1886 if (b
== EXIT_BLOCK_PTR
)
1888 for (first
= NEXT_INSN (first
) ; first
; first
= NEXT_INSN (first
))
1890 && GET_CODE (PATTERN (first
)) != USE
1891 && ! ((GET_CODE (PATTERN (first
)) == ADDR_VEC
1892 || GET_CODE (PATTERN (first
)) == ADDR_DIFF_VEC
)
1893 && prev_real_insn (first
) != 0
1894 && GET_CODE (prev_real_insn (first
)) == JUMP_INSN
))
1899 FREE_REG_SET (live_relevant_regs
);
1903 /* Print debugging trace information if -dg switch is given,
1904 showing the information on which the allocation decisions are based. */
1907 dump_conflicts (FILE *file
)
1910 int has_preferences
;
1913 for (i
= 0; i
< max_allocno
; i
++)
1915 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1919 fprintf (file
, ";; %d regs to allocate:", nregs
);
1920 for (i
= 0; i
< max_allocno
; i
++)
1923 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1925 fprintf (file
, " %d", allocno
[allocno_order
[i
]].reg
);
1926 for (j
= 0; j
< max_regno
; j
++)
1927 if (reg_allocno
[j
] == allocno_order
[i
]
1928 && j
!= allocno
[allocno_order
[i
]].reg
)
1929 fprintf (file
, "+%d", j
);
1930 if (allocno
[allocno_order
[i
]].size
!= 1)
1931 fprintf (file
, " (%d)", allocno
[allocno_order
[i
]].size
);
1933 fprintf (file
, "\n");
1935 for (i
= 0; i
< max_allocno
; i
++)
1938 fprintf (file
, ";; %d conflicts:", allocno
[i
].reg
);
1939 for (j
= 0; j
< max_allocno
; j
++)
1940 if (CONFLICTP (j
, i
))
1941 fprintf (file
, " %d", allocno
[j
].reg
);
1942 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1943 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_conflicts
, j
))
1944 fprintf (file
, " %d", j
);
1945 fprintf (file
, "\n");
1947 has_preferences
= 0;
1948 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1949 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1950 has_preferences
= 1;
1952 if (! has_preferences
)
1954 fprintf (file
, ";; %d preferences:", allocno
[i
].reg
);
1955 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1956 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1957 fprintf (file
, " %d", j
);
1958 fprintf (file
, "\n");
1960 fprintf (file
, "\n");
1964 dump_global_regs (FILE *file
)
1968 fprintf (file
, ";; Register dispositions:\n");
1969 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1970 if (reg_renumber
[i
] >= 0)
1972 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1974 fprintf (file
, "\n");
1977 fprintf (file
, "\n\n;; Hard regs used: ");
1978 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1979 if (regs_ever_live
[i
])
1980 fprintf (file
, " %d", i
);
1981 fprintf (file
, "\n\n");