1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 88, 91, 94, 96-98, 1999 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
26 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "insn-config.h"
36 /* This pass of the compiler performs global register allocation.
37 It assigns hard register numbers to all the pseudo registers
38 that were not handled in local_alloc. Assignments are recorded
39 in the vector reg_renumber, not by changing the rtl code.
40 (Such changes are made by final). The entry point is
41 the function global_alloc.
43 After allocation is complete, the reload pass is run as a subroutine
44 of this pass, so that when a pseudo reg loses its hard reg due to
45 spilling it is possible to make a second attempt to find a hard
46 reg for it. The reload pass is independent in other respects
47 and it is run even when stupid register allocation is in use.
49 1. Assign allocation-numbers (allocnos) to the pseudo-registers
50 still needing allocations and to the pseudo-registers currently
51 allocated by local-alloc which may be spilled by reload.
52 Set up tables reg_allocno and allocno_reg to map
53 reg numbers to allocnos and vice versa.
54 max_allocno gets the number of allocnos in use.
56 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
57 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
58 for conflicts between allocnos and explicit hard register use
59 (which includes use of pseudo-registers allocated by local_alloc).
61 3. For each basic block
62 walk forward through the block, recording which
63 pseudo-registers and which hardware registers are live.
64 Build the conflict matrix between the pseudo-registers
65 and another of pseudo-registers versus hardware registers.
66 Also record the preferred hardware registers
67 for each pseudo-register.
69 4. Sort a table of the allocnos into order of
70 desirability of the variables.
72 5. Allocate the variables in that order; each if possible into
73 a preferred register, else into another register. */
75 /* Number of pseudo-registers which are candidates for allocation. */
77 static int max_allocno
;
79 /* Indexed by (pseudo) reg number, gives the allocno, or -1
80 for pseudo registers which are not to be allocated. */
82 static int *reg_allocno
;
84 /* Indexed by allocno, gives the reg number. */
86 static int *allocno_reg
;
88 /* A vector of the integers from 0 to max_allocno-1,
89 sorted in the order of first-to-be-allocated first. */
91 static int *allocno_order
;
93 /* Indexed by an allocno, gives the number of consecutive
94 hard registers needed by that pseudo reg. */
96 static int *allocno_size
;
98 /* Indexed by (pseudo) reg number, gives the number of another
99 lower-numbered pseudo reg which can share a hard reg with this pseudo
100 *even if the two pseudos would otherwise appear to conflict*. */
102 static int *reg_may_share
;
104 /* Define the number of bits in each element of `conflicts' and what
105 type that element has. We use the largest integer format on the
108 #define INT_BITS HOST_BITS_PER_WIDE_INT
109 #define INT_TYPE HOST_WIDE_INT
111 /* max_allocno by max_allocno array of bits,
112 recording whether two allocno's conflict (can't go in the same
115 `conflicts' is not symmetric; a conflict between allocno's i and j
116 is recorded either in element i,j or in element j,i. */
118 static INT_TYPE
*conflicts
;
120 /* Number of ints require to hold max_allocno bits.
121 This is the length of a row in `conflicts'. */
123 static int allocno_row_words
;
125 /* Two macros to test or store 1 in an element of `conflicts'. */
127 #define CONFLICTP(I, J) \
128 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
129 & ((INT_TYPE) 1 << ((J) % INT_BITS)))
131 #define SET_CONFLICT(I, J) \
132 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
133 |= ((INT_TYPE) 1 << ((J) % INT_BITS)))
135 /* Set of hard regs currently live (during scan of all insns). */
137 static HARD_REG_SET hard_regs_live
;
139 /* Indexed by N, set of hard regs conflicting with allocno N. */
141 static HARD_REG_SET
*hard_reg_conflicts
;
143 /* Indexed by N, set of hard regs preferred by allocno N.
144 This is used to make allocnos go into regs that are copied to or from them,
145 when possible, to reduce register shuffling. */
147 static HARD_REG_SET
*hard_reg_preferences
;
149 /* Similar, but just counts register preferences made in simple copy
150 operations, rather than arithmetic. These are given priority because
151 we can always eliminate an insn by using these, but using a register
152 in the above list won't always eliminate an insn. */
154 static HARD_REG_SET
*hard_reg_copy_preferences
;
156 /* Similar to hard_reg_preferences, but includes bits for subsequent
157 registers when an allocno is multi-word. The above variable is used for
158 allocation while this is used to build reg_someone_prefers, below. */
160 static HARD_REG_SET
*hard_reg_full_preferences
;
162 /* Indexed by N, set of hard registers that some later allocno has a
165 static HARD_REG_SET
*regs_someone_prefers
;
167 /* Set of registers that global-alloc isn't supposed to use. */
169 static HARD_REG_SET no_global_alloc_regs
;
171 /* Set of registers used so far. */
173 static HARD_REG_SET regs_used_so_far
;
175 /* Number of calls crossed by each allocno. */
177 static int *allocno_calls_crossed
;
179 /* Number of refs (weighted) to each allocno. */
181 static int *allocno_n_refs
;
183 /* Guess at live length of each allocno.
184 This is actually the max of the live lengths of the regs. */
186 static int *allocno_live_length
;
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. */
191 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
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. */
196 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
198 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
199 for vector element I, and hard register number J. */
201 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
203 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
205 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
207 /* Bit mask for allocnos live at current point in the scan. */
209 static INT_TYPE
*allocnos_live
;
211 /* Test, set or clear bit number I in allocnos_live,
212 a bit vector indexed by allocno. */
214 #define ALLOCNO_LIVE_P(I) \
215 (allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS)))
217 #define SET_ALLOCNO_LIVE(I) \
218 (allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS)))
220 #define CLEAR_ALLOCNO_LIVE(I) \
221 (allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((I) % INT_BITS)))
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.
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. */
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. */
243 int n_no_conflict_pairs
;
244 static struct { int allocno1
, allocno2
;}
245 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
248 /* Record all regs that are set in any one insn.
249 Communication from mark_reg_{store,clobber} and global_conflicts. */
251 static rtx
*regs_set
;
252 static int n_regs_set
;
254 /* All registers that can be eliminated. */
256 static HARD_REG_SET eliminable_regset
;
258 static int allocno_compare
PROTO((const GENERIC_PTR
, const GENERIC_PTR
));
259 static void global_conflicts
PROTO((void));
260 static void expand_preferences
PROTO((void));
261 static void prune_preferences
PROTO((void));
262 static void find_reg
PROTO((int, HARD_REG_SET
, int, int, int));
263 static void record_one_conflict
PROTO((int));
264 static void record_conflicts
PROTO((int *, int));
265 static void mark_reg_store
PROTO((rtx
, rtx
));
266 static void mark_reg_clobber
PROTO((rtx
, rtx
));
267 static void mark_reg_conflicts
PROTO((rtx
));
268 static void mark_reg_death
PROTO((rtx
));
269 static void mark_reg_live_nc
PROTO((int, enum machine_mode
));
270 static void set_preference
PROTO((rtx
, rtx
));
271 static void dump_conflicts
PROTO((FILE *));
272 static void reg_becomes_live
PROTO((rtx
, rtx
));
273 static void reg_dies
PROTO((int, enum machine_mode
));
274 static void build_insn_chain
PROTO((rtx
));
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.
280 Return value is nonzero if reload failed
281 and we must not do any more for this function. */
288 #ifdef ELIMINABLE_REGS
289 static struct {int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
292 = (! flag_omit_frame_pointer
293 #ifdef EXIT_IGNORE_STACK
294 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
296 || FRAME_POINTER_REQUIRED
);
303 /* A machine may have certain hard registers that
304 are safe to use only within a basic block. */
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
);
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
++)
318 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
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
);
324 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
325 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
327 SET_HARD_REG_BIT (no_global_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
331 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
333 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
336 /* Track which registers have already been used. Start with registers
337 explicitly in the rtl, then registers allocated by local register
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
348 static char leaf_regs
[] = LEAF_REGISTERS
;
350 if (only_leaf_regs_used () && leaf_function_p ())
351 cheap_regs
= leaf_regs
;
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
);
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
);
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
]);
370 /* Establish mappings from register number to allocation number
371 and vice versa. In the process, count the allocnos. */
373 reg_allocno
= (int *) alloca (max_regno
* sizeof (int));
375 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
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))
384 int r1
= REGNO (XEXP (x
, 0));
385 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
387 reg_may_share
[r1
] = r2
;
389 reg_may_share
[r2
] = r1
;
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))
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
]];
405 reg_allocno
[i
] = max_allocno
++;
406 if (REG_LIVE_LENGTH (i
) == 0)
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));
422 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
423 if (reg_allocno
[i
] >= 0)
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
);
434 /* Calculate amount of usage of each hard reg by pseudos
435 allocated by local-alloc. This is to see if we want to
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)
442 int regno
= reg_renumber
[i
];
443 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (i
));
446 for (j
= regno
; j
< endregno
; j
++)
448 local_reg_n_refs
[j
] += REG_N_REFS (i
);
449 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
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;
458 /* Allocate the space for the conflict and preference tables and
462 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
463 bzero ((char *) hard_reg_conflicts
, max_allocno
* sizeof (HARD_REG_SET
));
466 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
467 bzero ((char *) hard_reg_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
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
));
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
));
480 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
481 bzero ((char *) regs_someone_prefers
, max_allocno
* sizeof (HARD_REG_SET
));
483 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
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
));
493 allocnos_live
= (INT_TYPE
*) alloca (allocno_row_words
* sizeof (INT_TYPE
));
495 /* If there is work to be done (at least one reg to allocate),
496 perform global conflict analysis and allocate the regs. */
500 /* Scan all the insns and compute the conflicts among allocnos
501 and between allocnos and hard regs. */
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
512 for (i
= 0; i
< (size_t) max_allocno
; i
++)
514 AND_COMPL_HARD_REG_SET (hard_reg_conflicts
[i
], eliminable_regset
);
515 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[i
],
517 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[i
], eliminable_regset
);
520 /* Try to expand the preferences by merging them between allocnos. */
522 expand_preferences ();
524 /* Determine the order to allocate the remaining pseudo registers. */
526 allocno_order
= (int *) alloca (max_allocno
* sizeof (int));
527 for (i
= 0; i
< (size_t) max_allocno
; i
++)
528 allocno_order
[i
] = i
;
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
537 for (i
= 0; i
< (size_t) max_allocno
; i
++)
539 if (allocno_size
[i
] == 0)
541 if (allocno_live_length
[i
] == 0)
542 allocno_live_length
[i
] = -1;
545 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
547 prune_preferences ();
550 dump_conflicts (file
);
552 /* Try allocating them, one by one, in that order,
553 except for parameters marked with reg_live_length[regno] == -2. */
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)
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)
564 find_reg (allocno_order
[i
], 0, 0, 0, 0);
565 if (reg_renumber
[allocno_reg
[allocno_order
[i
]]] >= 0)
568 if (reg_alternate_class (allocno_reg
[allocno_order
[i
]]) != NO_REGS
)
569 find_reg (allocno_order
[i
], 0, 1, 0, 0);
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. */
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)
581 build_insn_chain (get_insns ());
582 retval
= reload (get_insns (), 1, file
);
589 /* Sort predicate for ordering the allocnos.
590 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
593 allocno_compare (v1p
, v2p
)
594 const GENERIC_PTR v1p
;
595 const GENERIC_PTR v2p
;
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. */
603 = (((double) (floor_log2 (allocno_n_refs
[v1
]) * allocno_n_refs
[v1
])
604 / allocno_live_length
[v1
])
605 * 10000 * allocno_size
[v1
]);
607 = (((double) (floor_log2 (allocno_n_refs
[v2
]) * allocno_n_refs
[v2
])
608 / allocno_live_length
[v2
])
609 * 10000 * allocno_size
[v2
]);
613 /* If regs are equally good, sort by allocno,
614 so that the results of qsort leave nothing to chance. */
618 /* Scan the rtl code and record all conflicts and register preferences in the
619 conflict matrices and preference tables. */
626 int *block_start_allocnos
;
628 /* Make a vector that mark_reg_{store,clobber} will store in. */
629 regs_set
= (rtx
*) alloca (max_parallel
* sizeof (rtx
) * 2);
631 block_start_allocnos
= (int *) alloca (max_allocno
* sizeof (int));
633 for (b
= 0; b
< n_basic_blocks
; b
++)
635 bzero ((char *) allocnos_live
, allocno_row_words
* sizeof (INT_TYPE
));
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.
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. */
651 register regset old
= basic_block_live_at_start
[b
];
654 REG_SET_TO_HARD_REG_SET (hard_regs_live
, old
);
655 EXECUTE_IF_SET_IN_REG_SET (old
, FIRST_PSEUDO_REGISTER
, i
,
657 register int a
= reg_allocno
[i
];
660 SET_ALLOCNO_LIVE (a
);
661 block_start_allocnos
[ax
++] = a
;
663 else if ((a
= reg_renumber
[i
]) >= 0)
665 (a
, PSEUDO_REGNO_MODE (i
));
668 /* Record that each allocno now live conflicts with each other
669 allocno now live, and with each hard reg now live. */
671 record_conflicts (block_start_allocnos
, ax
);
674 /* Pseudos can't go in stack regs at the start of a basic block
675 that can be reached through a computed goto, since reg-stack
676 can't handle computed gotos. */
677 if (basic_block_computed_jump_target
[b
])
678 for (ax
= FIRST_STACK_REG
; ax
<= LAST_STACK_REG
; ax
++)
679 record_one_conflict (ax
);
683 insn
= BLOCK_HEAD (b
);
685 /* Scan the code of this basic block, noting which allocnos
686 and hard regs are born or die. When one is born,
687 record a conflict with all others currently live. */
691 register RTX_CODE code
= GET_CODE (insn
);
694 /* Make regs_set an empty set. */
698 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
703 for (link
= REG_NOTES (insn
);
704 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
705 link
= XEXP (link
, 1))
706 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
708 no_conflict_pairs
[i
].allocno1
709 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
710 no_conflict_pairs
[i
].allocno2
711 = reg_allocno
[REGNO (XEXP (link
, 0))];
716 /* Mark any registers clobbered by INSN as live,
717 so they conflict with the inputs. */
719 note_stores (PATTERN (insn
), mark_reg_clobber
);
721 /* Mark any registers dead after INSN as dead now. */
723 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
724 if (REG_NOTE_KIND (link
) == REG_DEAD
)
725 mark_reg_death (XEXP (link
, 0));
727 /* Mark any registers set in INSN as live,
728 and mark them as conflicting with all other live regs.
729 Clobbers are processed again, so they conflict with
730 the registers that are set. */
732 note_stores (PATTERN (insn
), mark_reg_store
);
735 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
736 if (REG_NOTE_KIND (link
) == REG_INC
)
737 mark_reg_store (XEXP (link
, 0), NULL_RTX
);
740 /* If INSN has multiple outputs, then any reg that dies here
741 and is used inside of an output
742 must conflict with the other outputs.
744 It is unsafe to use !single_set here since it will ignore an
745 unused output. Just because an output is unused does not mean
746 the compiler can assume the side effect will not occur.
747 Consider if REG appears in the address of an output and we
748 reload the output. If we allocate REG to the same hard
749 register as an unused output we could set the hard register
750 before the output reload insn. */
751 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
752 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
753 if (REG_NOTE_KIND (link
) == REG_DEAD
)
755 int used_in_output
= 0;
757 rtx reg
= XEXP (link
, 0);
759 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
761 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
762 if (GET_CODE (set
) == SET
763 && GET_CODE (SET_DEST (set
)) != REG
764 && !rtx_equal_p (reg
, SET_DEST (set
))
765 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
769 mark_reg_conflicts (reg
);
772 /* Mark any registers set in INSN and then never used. */
774 while (n_regs_set
> 0)
775 if (find_regno_note (insn
, REG_UNUSED
,
776 REGNO (regs_set
[--n_regs_set
])))
777 mark_reg_death (regs_set
[n_regs_set
]);
780 if (insn
== BLOCK_END (b
))
782 insn
= NEXT_INSN (insn
);
786 /* Expand the preference information by looking for cases where one allocno
787 dies in an insn that sets an allocno. If those two allocnos don't conflict,
788 merge any preferences between those allocnos. */
791 expand_preferences ()
797 /* We only try to handle the most common cases here. Most of the cases
798 where this wins are reg-reg copies. */
800 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
801 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
802 && (set
= single_set (insn
)) != 0
803 && GET_CODE (SET_DEST (set
)) == REG
804 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
805 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
806 if (REG_NOTE_KIND (link
) == REG_DEAD
807 && GET_CODE (XEXP (link
, 0)) == REG
808 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
809 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
810 reg_allocno
[REGNO (XEXP (link
, 0))])
811 && ! CONFLICTP (reg_allocno
[REGNO (XEXP (link
, 0))],
812 reg_allocno
[REGNO (SET_DEST (set
))]))
814 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
815 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
817 if (XEXP (link
, 0) == SET_SRC (set
))
819 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a1
],
820 hard_reg_copy_preferences
[a2
]);
821 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a2
],
822 hard_reg_copy_preferences
[a1
]);
825 IOR_HARD_REG_SET (hard_reg_preferences
[a1
],
826 hard_reg_preferences
[a2
]);
827 IOR_HARD_REG_SET (hard_reg_preferences
[a2
],
828 hard_reg_preferences
[a1
]);
829 IOR_HARD_REG_SET (hard_reg_full_preferences
[a1
],
830 hard_reg_full_preferences
[a2
]);
831 IOR_HARD_REG_SET (hard_reg_full_preferences
[a2
],
832 hard_reg_full_preferences
[a1
]);
836 /* Prune the preferences for global registers to exclude registers that cannot
839 Compute `regs_someone_prefers', which is a bitmask of the hard registers
840 that are preferred by conflicting registers of lower priority. If possible,
841 we will avoid using these registers. */
849 /* Scan least most important to most important.
850 For each allocno, remove from preferences registers that cannot be used,
851 either because of conflicts or register type. Then compute all registers
852 preferred by each lower-priority register that conflicts. */
854 for (i
= max_allocno
- 1; i
>= 0; i
--)
858 allocno
= allocno_order
[i
];
859 COPY_HARD_REG_SET (temp
, hard_reg_conflicts
[allocno
]);
861 if (allocno_calls_crossed
[allocno
] == 0)
862 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
864 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
866 IOR_COMPL_HARD_REG_SET
868 reg_class_contents
[(int) reg_preferred_class (allocno_reg
[allocno
])]);
870 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], temp
);
871 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], temp
);
872 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences
[allocno
], temp
);
874 CLEAR_HARD_REG_SET (regs_someone_prefers
[allocno
]);
876 /* Merge in the preferences of lower-priority registers (they have
877 already been pruned). If we also prefer some of those registers,
878 don't exclude them unless we are of a smaller size (in which case
879 we want to give the lower-priority allocno the first chance for
881 for (j
= i
+ 1; j
< max_allocno
; j
++)
882 if (CONFLICTP (allocno
, allocno_order
[j
])
883 || CONFLICTP (allocno_order
[j
], allocno
))
885 COPY_HARD_REG_SET (temp
,
886 hard_reg_full_preferences
[allocno_order
[j
]]);
887 if (allocno_size
[allocno_order
[j
]] <= allocno_size
[allocno
])
888 AND_COMPL_HARD_REG_SET (temp
,
889 hard_reg_full_preferences
[allocno
]);
891 IOR_HARD_REG_SET (regs_someone_prefers
[allocno
], temp
);
896 /* Assign a hard register to ALLOCNO; look for one that is the beginning
897 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
898 The registers marked in PREFREGS are tried first.
900 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
901 be used for this allocation.
903 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
904 Otherwise ignore that preferred class and use the alternate class.
906 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
907 will have to be saved and restored at calls.
909 RETRYING is nonzero if this is called from retry_global_alloc.
911 If we find one, record it in reg_renumber.
912 If not, do nothing. */
915 find_reg (allocno
, losers
, alt_regs_p
, accept_call_clobbered
, retrying
)
919 int accept_call_clobbered
;
922 register int i
, best_reg
, pass
;
924 register /* Declare it register if it's a scalar. */
926 HARD_REG_SET used
, used1
, used2
;
928 enum reg_class
class = (alt_regs_p
929 ? reg_alternate_class (allocno_reg
[allocno
])
930 : reg_preferred_class (allocno_reg
[allocno
]));
931 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno_reg
[allocno
]);
933 if (accept_call_clobbered
)
934 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
935 else if (allocno_calls_crossed
[allocno
] == 0)
936 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
938 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
940 /* Some registers should not be allocated in global-alloc. */
941 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
943 IOR_HARD_REG_SET (used1
, losers
);
945 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
946 COPY_HARD_REG_SET (used2
, used1
);
948 IOR_HARD_REG_SET (used1
, hard_reg_conflicts
[allocno
]);
950 #ifdef CLASS_CANNOT_CHANGE_SIZE
951 if (REG_CHANGES_SIZE (allocno_reg
[allocno
]))
952 IOR_HARD_REG_SET (used1
,
953 reg_class_contents
[(int) CLASS_CANNOT_CHANGE_SIZE
]);
956 /* Try each hard reg to see if it fits. Do this in two passes.
957 In the first pass, skip registers that are preferred by some other pseudo
958 to give it a better chance of getting one of those registers. Only if
959 we can't get a register when excluding those do we take one of them.
960 However, we never allocate a register for the first time in pass 0. */
962 COPY_HARD_REG_SET (used
, used1
);
963 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
964 IOR_HARD_REG_SET (used
, regs_someone_prefers
[allocno
]);
967 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
968 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
972 COPY_HARD_REG_SET (used
, used1
);
973 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
975 #ifdef REG_ALLOC_ORDER
976 int regno
= reg_alloc_order
[i
];
980 if (! TEST_HARD_REG_BIT (used
, regno
)
981 && HARD_REGNO_MODE_OK (regno
, mode
)
982 && (allocno_calls_crossed
[allocno
] == 0
983 || accept_call_clobbered
984 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
)))
987 register int lim
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
990 && ! TEST_HARD_REG_BIT (used
, j
));
997 #ifndef REG_ALLOC_ORDER
998 i
= j
; /* Skip starting points we know will lose */
1004 /* See if there is a preferred register with the same class as the register
1005 we allocated above. Making this restriction prevents register
1006 preferencing from creating worse register allocation.
1008 Remove from the preferred registers and conflicting registers. Note that
1009 additional conflicts may have been added after `prune_preferences' was
1012 First do this for those register with copy preferences, then all
1013 preferred registers. */
1015 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], used
);
1016 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences
[allocno
],
1017 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
1021 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1022 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences
[allocno
], i
)
1023 && HARD_REGNO_MODE_OK (i
, mode
)
1024 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1025 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1026 REGNO_REG_CLASS (best_reg
))
1027 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1028 REGNO_REG_CLASS (i
))))
1031 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1034 && ! TEST_HARD_REG_BIT (used
, j
)
1035 && (REGNO_REG_CLASS (j
)
1036 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1037 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1038 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1039 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1040 REGNO_REG_CLASS (j
))));
1051 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], used
);
1052 GO_IF_HARD_REG_SUBSET (hard_reg_preferences
[allocno
],
1053 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1057 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1058 if (TEST_HARD_REG_BIT (hard_reg_preferences
[allocno
], i
)
1059 && HARD_REGNO_MODE_OK (i
, mode
)
1060 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1061 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1062 REGNO_REG_CLASS (best_reg
))
1063 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1064 REGNO_REG_CLASS (i
))))
1067 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1070 && ! TEST_HARD_REG_BIT (used
, j
)
1071 && (REGNO_REG_CLASS (j
)
1072 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1073 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1074 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1075 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1076 REGNO_REG_CLASS (j
))));
1087 /* If we haven't succeeded yet, try with caller-saves.
1088 We need not check to see if the current function has nonlocal
1089 labels because we don't put any pseudos that are live over calls in
1090 registers in that case. */
1092 if (flag_caller_saves
&& best_reg
< 0)
1094 /* Did not find a register. If it would be profitable to
1095 allocate a call-clobbered register and save and restore it
1096 around calls, do that. */
1097 if (! accept_call_clobbered
1098 && allocno_calls_crossed
[allocno
] != 0
1099 && CALLER_SAVE_PROFITABLE (allocno_n_refs
[allocno
],
1100 allocno_calls_crossed
[allocno
]))
1102 HARD_REG_SET new_losers
;
1104 CLEAR_HARD_REG_SET (new_losers
);
1106 COPY_HARD_REG_SET (new_losers
, losers
);
1108 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1109 find_reg (allocno
, new_losers
, alt_regs_p
, 1, retrying
);
1110 if (reg_renumber
[allocno_reg
[allocno
]] >= 0)
1112 caller_save_needed
= 1;
1118 /* If we haven't succeeded yet,
1119 see if some hard reg that conflicts with us
1120 was utilized poorly by local-alloc.
1121 If so, kick out the regs that were put there by local-alloc
1122 so we can use it instead. */
1123 if (best_reg
< 0 && !retrying
1124 /* Let's not bother with multi-reg allocnos. */
1125 && allocno_size
[allocno
] == 1)
1127 /* Count from the end, to find the least-used ones first. */
1128 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1130 #ifdef REG_ALLOC_ORDER
1131 int regno
= reg_alloc_order
[i
];
1136 if (local_reg_n_refs
[regno
] != 0
1137 /* Don't use a reg no good for this pseudo. */
1138 && ! TEST_HARD_REG_BIT (used2
, regno
)
1139 && HARD_REGNO_MODE_OK (regno
, mode
)
1140 #ifdef CLASS_CANNOT_CHANGE_SIZE
1141 && ! (REG_CHANGES_SIZE (allocno_reg
[allocno
])
1142 && (TEST_HARD_REG_BIT
1143 (reg_class_contents
[(int) CLASS_CANNOT_CHANGE_SIZE
],
1148 /* We explicitly evaluate the divide results into temporary
1149 variables so as to avoid excess precision problems that occur
1150 on a i386-unknown-sysv4.2 (unixware) host. */
1152 double tmp1
= ((double) local_reg_n_refs
[regno
]
1153 / local_reg_live_length
[regno
]);
1154 double tmp2
= ((double) allocno_n_refs
[allocno
]
1155 / allocno_live_length
[allocno
]);
1159 /* Hard reg REGNO was used less in total by local regs
1160 than it would be used by this one allocno! */
1162 for (k
= 0; k
< max_regno
; k
++)
1163 if (reg_renumber
[k
] >= 0)
1165 int r
= reg_renumber
[k
];
1167 = r
+ HARD_REGNO_NREGS (r
, PSEUDO_REGNO_MODE (k
));
1169 if (regno
>= r
&& regno
< endregno
)
1170 reg_renumber
[k
] = -1;
1180 /* Did we find a register? */
1184 register int lim
, j
;
1185 HARD_REG_SET this_reg
;
1187 /* Yes. Record it as the hard register of this pseudo-reg. */
1188 reg_renumber
[allocno_reg
[allocno
]] = best_reg
;
1189 /* Also of any pseudo-regs that share with it. */
1190 if (reg_may_share
[allocno_reg
[allocno
]])
1191 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1192 if (reg_allocno
[j
] == allocno
)
1193 reg_renumber
[j
] = best_reg
;
1195 /* Make a set of the hard regs being allocated. */
1196 CLEAR_HARD_REG_SET (this_reg
);
1197 lim
= best_reg
+ HARD_REGNO_NREGS (best_reg
, mode
);
1198 for (j
= best_reg
; j
< lim
; j
++)
1200 SET_HARD_REG_BIT (this_reg
, j
);
1201 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1202 /* This is no longer a reg used just by local regs. */
1203 local_reg_n_refs
[j
] = 0;
1205 /* For each other pseudo-reg conflicting with this one,
1206 mark it as conflicting with the hard regs this one occupies. */
1208 for (j
= 0; j
< max_allocno
; j
++)
1209 if (CONFLICTP (lim
, j
) || CONFLICTP (j
, lim
))
1211 IOR_HARD_REG_SET (hard_reg_conflicts
[j
], this_reg
);
1216 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1217 Perhaps it had previously seemed not worth a hard reg,
1218 or perhaps its old hard reg has been commandeered for reloads.
1219 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1220 they do not appear to be allocated.
1221 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1224 retry_global_alloc (regno
, forbidden_regs
)
1226 HARD_REG_SET forbidden_regs
;
1228 int allocno
= reg_allocno
[regno
];
1231 /* If we have more than one register class,
1232 first try allocating in the class that is cheapest
1233 for this pseudo-reg. If that fails, try any reg. */
1234 if (N_REG_CLASSES
> 1)
1235 find_reg (allocno
, forbidden_regs
, 0, 0, 1);
1236 if (reg_renumber
[regno
] < 0
1237 && reg_alternate_class (regno
) != NO_REGS
)
1238 find_reg (allocno
, forbidden_regs
, 1, 0, 1);
1240 /* If we found a register, modify the RTL for the register to
1241 show the hard register, and mark that register live. */
1242 if (reg_renumber
[regno
] >= 0)
1244 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1245 mark_home_live (regno
);
1250 /* Record a conflict between register REGNO
1251 and everything currently live.
1252 REGNO must not be a pseudo reg that was allocated
1253 by local_alloc; such numbers must be translated through
1254 reg_renumber before calling here. */
1257 record_one_conflict (regno
)
1262 if (regno
< FIRST_PSEUDO_REGISTER
)
1263 /* When a hard register becomes live,
1264 record conflicts with live pseudo regs. */
1265 for (j
= 0; j
< max_allocno
; j
++)
1267 if (ALLOCNO_LIVE_P (j
))
1268 SET_HARD_REG_BIT (hard_reg_conflicts
[j
], regno
);
1271 /* When a pseudo-register becomes live,
1272 record conflicts first with hard regs,
1273 then with other pseudo regs. */
1275 register int ialloc
= reg_allocno
[regno
];
1276 register int ialloc_prod
= ialloc
* allocno_row_words
;
1277 IOR_HARD_REG_SET (hard_reg_conflicts
[ialloc
], hard_regs_live
);
1278 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1282 for (k
= 0; k
< n_no_conflict_pairs
; k
++)
1283 if (! ((j
== no_conflict_pairs
[k
].allocno1
1284 && ialloc
== no_conflict_pairs
[k
].allocno2
)
1286 (j
== no_conflict_pairs
[k
].allocno2
1287 && ialloc
== no_conflict_pairs
[k
].allocno1
)))
1289 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1294 /* Record all allocnos currently live as conflicting
1295 with each other and with all hard regs currently live.
1296 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1297 are currently live. Their bits are also flagged in allocnos_live. */
1300 record_conflicts (allocno_vec
, len
)
1301 register int *allocno_vec
;
1304 register int allocno
;
1306 register int ialloc_prod
;
1310 allocno
= allocno_vec
[len
];
1311 ialloc_prod
= allocno
* allocno_row_words
;
1312 IOR_HARD_REG_SET (hard_reg_conflicts
[allocno
], hard_regs_live
);
1313 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1314 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1318 /* Handle the case where REG is set by the insn being scanned,
1319 during the forward scan to accumulate conflicts.
1320 Store a 1 in regs_live or allocnos_live for this register, record how many
1321 consecutive hardware registers it actually needs,
1322 and record a conflict with all other registers already live.
1324 Note that even if REG does not remain alive after this insn,
1325 we must mark it here as live, to ensure a conflict between
1326 REG and any other regs set in this insn that really do live.
1327 This is because those other regs could be considered after this.
1329 REG might actually be something other than a register;
1330 if so, we do nothing.
1332 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1333 a REG_INC note was found for it). */
1336 mark_reg_store (reg
, setter
)
1341 /* WORD is which word of a multi-register group is being stored.
1342 For the case where the store is actually into a SUBREG of REG.
1343 Except we don't use it; I believe the entire REG needs to be
1347 if (GET_CODE (reg
) == SUBREG
)
1349 word
= SUBREG_WORD (reg
);
1350 reg
= SUBREG_REG (reg
);
1353 if (GET_CODE (reg
) != REG
)
1356 regs_set
[n_regs_set
++] = reg
;
1358 if (setter
&& GET_CODE (setter
) != CLOBBER
)
1359 set_preference (reg
, SET_SRC (setter
));
1361 regno
= REGNO (reg
);
1363 /* Either this is one of the max_allocno pseudo regs not allocated,
1364 or it is or has a hardware reg. First handle the pseudo-regs. */
1365 if (regno
>= FIRST_PSEUDO_REGISTER
)
1367 if (reg_allocno
[regno
] >= 0)
1369 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1370 record_one_conflict (regno
);
1374 if (reg_renumber
[regno
] >= 0)
1375 regno
= reg_renumber
[regno
] /* + word */;
1377 /* Handle hardware regs (and pseudos allocated to hard regs). */
1378 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1380 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1381 while (regno
< last
)
1383 record_one_conflict (regno
);
1384 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1390 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1393 mark_reg_clobber (reg
, setter
)
1396 if (GET_CODE (setter
) == CLOBBER
)
1397 mark_reg_store (reg
, setter
);
1400 /* Record that REG has conflicts with all the regs currently live.
1401 Do not mark REG itself as live. */
1404 mark_reg_conflicts (reg
)
1409 if (GET_CODE (reg
) == SUBREG
)
1410 reg
= SUBREG_REG (reg
);
1412 if (GET_CODE (reg
) != REG
)
1415 regno
= REGNO (reg
);
1417 /* Either this is one of the max_allocno pseudo regs not allocated,
1418 or it is or has a hardware reg. First handle the pseudo-regs. */
1419 if (regno
>= FIRST_PSEUDO_REGISTER
)
1421 if (reg_allocno
[regno
] >= 0)
1422 record_one_conflict (regno
);
1425 if (reg_renumber
[regno
] >= 0)
1426 regno
= reg_renumber
[regno
];
1428 /* Handle hardware regs (and pseudos allocated to hard regs). */
1429 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1431 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1432 while (regno
< last
)
1434 record_one_conflict (regno
);
1440 /* Mark REG as being dead (following the insn being scanned now).
1441 Store a 0 in regs_live or allocnos_live for this register. */
1444 mark_reg_death (reg
)
1447 register int regno
= REGNO (reg
);
1449 /* Either this is one of the max_allocno pseudo regs not allocated,
1450 or it is a hardware reg. First handle the pseudo-regs. */
1451 if (regno
>= FIRST_PSEUDO_REGISTER
)
1453 if (reg_allocno
[regno
] >= 0)
1454 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1457 /* For pseudo reg, see if it has been assigned a hardware reg. */
1458 if (reg_renumber
[regno
] >= 0)
1459 regno
= reg_renumber
[regno
];
1461 /* Handle hardware regs (and pseudos allocated to hard regs). */
1462 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1464 /* Pseudo regs already assigned hardware regs are treated
1465 almost the same as explicit hardware regs. */
1466 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1467 while (regno
< last
)
1469 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1475 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1476 for the value stored in it. MODE determines how many consecutive
1477 registers are actually in use. Do not record conflicts;
1478 it is assumed that the caller will do that. */
1481 mark_reg_live_nc (regno
, mode
)
1483 enum machine_mode mode
;
1485 register int last
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1486 while (regno
< last
)
1488 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1493 /* Try to set a preference for an allocno to a hard register.
1494 We are passed DEST and SRC which are the operands of a SET. It is known
1495 that SRC is a register. If SRC or the first operand of SRC is a register,
1496 try to set a preference. If one of the two is a hard register and the other
1497 is a pseudo-register, mark the preference.
1499 Note that we are not as aggressive as local-alloc in trying to tie a
1500 pseudo-register to a hard register. */
1503 set_preference (dest
, src
)
1506 int src_regno
, dest_regno
;
1507 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1508 to compensate for subregs in SRC or DEST. */
1513 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1514 src
= XEXP (src
, 0), copy
= 0;
1516 /* Get the reg number for both SRC and DEST.
1517 If neither is a reg, give up. */
1519 if (GET_CODE (src
) == REG
)
1520 src_regno
= REGNO (src
);
1521 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1523 src_regno
= REGNO (SUBREG_REG (src
));
1524 offset
+= SUBREG_WORD (src
);
1529 if (GET_CODE (dest
) == REG
)
1530 dest_regno
= REGNO (dest
);
1531 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1533 dest_regno
= REGNO (SUBREG_REG (dest
));
1534 offset
-= SUBREG_WORD (dest
);
1539 /* Convert either or both to hard reg numbers. */
1541 if (reg_renumber
[src_regno
] >= 0)
1542 src_regno
= reg_renumber
[src_regno
];
1544 if (reg_renumber
[dest_regno
] >= 0)
1545 dest_regno
= reg_renumber
[dest_regno
];
1547 /* Now if one is a hard reg and the other is a global pseudo
1548 then give the other a preference. */
1550 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1551 && reg_allocno
[src_regno
] >= 0)
1553 dest_regno
-= offset
;
1554 if (dest_regno
>= 0 && dest_regno
< FIRST_PSEUDO_REGISTER
)
1557 SET_REGBIT (hard_reg_copy_preferences
,
1558 reg_allocno
[src_regno
], dest_regno
);
1560 SET_REGBIT (hard_reg_preferences
,
1561 reg_allocno
[src_regno
], dest_regno
);
1562 for (i
= dest_regno
;
1563 i
< dest_regno
+ HARD_REGNO_NREGS (dest_regno
, GET_MODE (dest
));
1565 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1569 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1570 && reg_allocno
[dest_regno
] >= 0)
1572 src_regno
+= offset
;
1573 if (src_regno
>= 0 && src_regno
< FIRST_PSEUDO_REGISTER
)
1576 SET_REGBIT (hard_reg_copy_preferences
,
1577 reg_allocno
[dest_regno
], src_regno
);
1579 SET_REGBIT (hard_reg_preferences
,
1580 reg_allocno
[dest_regno
], src_regno
);
1582 i
< src_regno
+ HARD_REGNO_NREGS (src_regno
, GET_MODE (src
));
1584 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1589 /* Indicate that hard register number FROM was eliminated and replaced with
1590 an offset from hard register number TO. The status of hard registers live
1591 at the start of a basic block is updated by replacing a use of FROM with
1595 mark_elimination (from
, to
)
1600 for (i
= 0; i
< n_basic_blocks
; i
++)
1601 if (REGNO_REG_SET_P (basic_block_live_at_start
[i
], from
))
1603 CLEAR_REGNO_REG_SET (basic_block_live_at_start
[i
], from
);
1604 SET_REGNO_REG_SET (basic_block_live_at_start
[i
], to
);
1608 /* Used for communication between the following functions. Holds the
1609 current life information. */
1610 static regset live_relevant_regs
;
1612 /* Record in live_relevant_regs that register REG became live. This
1613 is called via note_stores. */
1615 reg_becomes_live (reg
, setter
)
1617 rtx setter ATTRIBUTE_UNUSED
;
1621 if (GET_CODE (reg
) == SUBREG
)
1622 reg
= SUBREG_REG (reg
);
1624 if (GET_CODE (reg
) != REG
)
1627 regno
= REGNO (reg
);
1628 if (regno
< FIRST_PSEUDO_REGISTER
)
1630 int nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1632 SET_REGNO_REG_SET (live_relevant_regs
, regno
++);
1634 else if (reg_renumber
[regno
] >= 0)
1635 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1638 /* Record in live_relevant_regs that register REGNO died. */
1640 reg_dies (regno
, mode
)
1642 enum machine_mode mode
;
1644 if (regno
< FIRST_PSEUDO_REGISTER
)
1646 int nregs
= HARD_REGNO_NREGS (regno
, mode
);
1648 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
++);
1651 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1654 /* Walk the insns of the current function and build reload_insn_chain,
1655 and record register life information. */
1657 build_insn_chain (first
)
1660 struct insn_chain
**p
= &reload_insn_chain
;
1661 struct insn_chain
*prev
= 0;
1664 live_relevant_regs
= ALLOCA_REG_SET ();
1666 for (; first
; first
= NEXT_INSN (first
))
1668 struct insn_chain
*c
;
1670 if (first
== BLOCK_HEAD (b
))
1673 CLEAR_REG_SET (live_relevant_regs
);
1674 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1675 if (REGNO_REG_SET_P (basic_block_live_at_start
[b
], i
)
1676 && ! TEST_HARD_REG_BIT (eliminable_regset
, i
))
1677 SET_REGNO_REG_SET (live_relevant_regs
, i
);
1679 for (; i
< max_regno
; i
++)
1680 if (reg_renumber
[i
] >= 0
1681 && REGNO_REG_SET_P (basic_block_live_at_start
[b
], i
))
1682 SET_REGNO_REG_SET (live_relevant_regs
, i
);
1685 if (GET_CODE (first
) != NOTE
&& GET_CODE (first
) != BARRIER
)
1687 c
= new_insn_chain ();
1695 COPY_REG_SET (c
->live_before
, live_relevant_regs
);
1697 if (GET_RTX_CLASS (GET_CODE (first
)) == 'i')
1701 /* Mark the death of everything that dies in this instruction. */
1703 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1704 if (REG_NOTE_KIND (link
) == REG_DEAD
1705 && GET_CODE (XEXP (link
, 0)) == REG
)
1706 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)));
1708 /* Mark everything born in this instruction as live. */
1710 note_stores (PATTERN (first
), reg_becomes_live
);
1713 /* Remember which registers are live at the end of the insn, before
1714 killing those with REG_UNUSED notes. */
1715 COPY_REG_SET (c
->live_after
, live_relevant_regs
);
1717 if (GET_RTX_CLASS (GET_CODE (first
)) == 'i')
1721 /* Mark anything that is set in this insn and then unused as dying. */
1723 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1724 if (REG_NOTE_KIND (link
) == REG_UNUSED
1725 && GET_CODE (XEXP (link
, 0)) == REG
)
1726 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)));
1730 if (first
== BLOCK_END (b
))
1733 /* Stop after we pass the end of the last basic block. Verify that
1734 no real insns are after the end of the last basic block.
1736 We may want to reorganize the loop somewhat since this test should
1737 always be the right exit test. */
1738 if (b
== n_basic_blocks
)
1740 for (first
= NEXT_INSN (first
) ; first
; first
= NEXT_INSN (first
))
1741 if (GET_RTX_CLASS (GET_CODE (first
)) == 'i'
1742 && GET_CODE (PATTERN (first
)) != USE
)
1747 FREE_REG_SET (live_relevant_regs
);
1751 /* Print debugging trace information if -greg switch is given,
1752 showing the information on which the allocation decisions are based. */
1755 dump_conflicts (file
)
1759 register int has_preferences
;
1762 for (i
= 0; i
< max_allocno
; i
++)
1764 if (reg_renumber
[allocno_reg
[allocno_order
[i
]]] >= 0)
1768 fprintf (file
, ";; %d regs to allocate:", nregs
);
1769 for (i
= 0; i
< max_allocno
; i
++)
1772 if (reg_renumber
[allocno_reg
[allocno_order
[i
]]] >= 0)
1774 fprintf (file
, " %d", allocno_reg
[allocno_order
[i
]]);
1775 for (j
= 0; j
< max_regno
; j
++)
1776 if (reg_allocno
[j
] == allocno_order
[i
]
1777 && j
!= allocno_reg
[allocno_order
[i
]])
1778 fprintf (file
, "+%d", j
);
1779 if (allocno_size
[allocno_order
[i
]] != 1)
1780 fprintf (file
, " (%d)", allocno_size
[allocno_order
[i
]]);
1782 fprintf (file
, "\n");
1784 for (i
= 0; i
< max_allocno
; i
++)
1787 fprintf (file
, ";; %d conflicts:", allocno_reg
[i
]);
1788 for (j
= 0; j
< max_allocno
; j
++)
1789 if (CONFLICTP (i
, j
) || CONFLICTP (j
, i
))
1790 fprintf (file
, " %d", allocno_reg
[j
]);
1791 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1792 if (TEST_HARD_REG_BIT (hard_reg_conflicts
[i
], j
))
1793 fprintf (file
, " %d", j
);
1794 fprintf (file
, "\n");
1796 has_preferences
= 0;
1797 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1798 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1799 has_preferences
= 1;
1801 if (! has_preferences
)
1803 fprintf (file
, ";; %d preferences:", allocno_reg
[i
]);
1804 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1805 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1806 fprintf (file
, " %d", j
);
1807 fprintf (file
, "\n");
1809 fprintf (file
, "\n");
1813 dump_global_regs (file
)
1818 fprintf (file
, ";; Register dispositions:\n");
1819 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1820 if (reg_renumber
[i
] >= 0)
1822 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1824 fprintf (file
, "\n");
1827 fprintf (file
, "\n\n;; Hard regs used: ");
1828 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1829 if (regs_ever_live
[i
])
1830 fprintf (file
, " %d", i
);
1831 fprintf (file
, "\n\n");