1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 88, 91, 94, 96, 1997 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"
35 /* This pass of the compiler performs global register allocation.
36 It assigns hard register numbers to all the pseudo registers
37 that were not handled in local_alloc. Assignments are recorded
38 in the vector reg_renumber, not by changing the rtl code.
39 (Such changes are made by final). The entry point is
40 the function global_alloc.
42 After allocation is complete, the reload pass is run as a subroutine
43 of this pass, so that when a pseudo reg loses its hard reg due to
44 spilling it is possible to make a second attempt to find a hard
45 reg for it. The reload pass is independent in other respects
46 and it is run even when stupid register allocation is in use.
48 1. Assign allocation-numbers (allocnos) to the pseudo-registers
49 still needing allocations and to the pseudo-registers currently
50 allocated by local-alloc which may be spilled by reload.
51 Set up tables reg_allocno and allocno_reg to map
52 reg numbers to allocnos and vice versa.
53 max_allocno gets the number of allocnos in use.
55 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
56 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
57 for conflicts between allocnos and explicit hard register use
58 (which includes use of pseudo-registers allocated by local_alloc).
60 3. For each basic block
61 walk forward through the block, recording which
62 pseudo-registers and which hardware registers are live.
63 Build the conflict matrix between the pseudo-registers
64 and another of pseudo-registers versus hardware registers.
65 Also record the preferred hardware registers
66 for each pseudo-register.
68 4. Sort a table of the allocnos into order of
69 desirability of the variables.
71 5. Allocate the variables in that order; each if possible into
72 a preferred register, else into another register. */
74 /* Number of pseudo-registers which are candidates for allocation. */
76 static int max_allocno
;
78 /* Indexed by (pseudo) reg number, gives the allocno, or -1
79 for pseudo registers which are not to be allocated. */
81 static int *reg_allocno
;
83 /* Indexed by allocno, gives the reg number. */
85 static int *allocno_reg
;
87 /* A vector of the integers from 0 to max_allocno-1,
88 sorted in the order of first-to-be-allocated first. */
90 static int *allocno_order
;
92 /* Indexed by an allocno, gives the number of consecutive
93 hard registers needed by that pseudo reg. */
95 static int *allocno_size
;
97 /* Indexed by (pseudo) reg number, gives the number of another
98 lower-numbered pseudo reg which can share a hard reg with this pseudo
99 *even if the two pseudos would otherwise appear to conflict*. */
101 static int *reg_may_share
;
103 /* Define the number of bits in each element of `conflicts' and what
104 type that element has. We use the largest integer format on the
107 #define INT_BITS HOST_BITS_PER_WIDE_INT
108 #define INT_TYPE HOST_WIDE_INT
110 /* max_allocno by max_allocno array of bits,
111 recording whether two allocno's conflict (can't go in the same
114 `conflicts' is not symmetric; a conflict between allocno's i and j
115 is recorded either in element i,j or in element j,i. */
117 static INT_TYPE
*conflicts
;
119 /* Number of ints require to hold max_allocno bits.
120 This is the length of a row in `conflicts'. */
122 static int allocno_row_words
;
124 /* Two macros to test or store 1 in an element of `conflicts'. */
126 #define CONFLICTP(I, J) \
127 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
128 & ((INT_TYPE) 1 << ((J) % INT_BITS)))
130 #define SET_CONFLICT(I, J) \
131 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
132 |= ((INT_TYPE) 1 << ((J) % INT_BITS)))
134 /* Set of hard regs currently live (during scan of all insns). */
136 static HARD_REG_SET hard_regs_live
;
138 /* Indexed by N, set of hard regs conflicting with allocno N. */
140 static HARD_REG_SET
*hard_reg_conflicts
;
142 /* Indexed by N, set of hard regs preferred by allocno N.
143 This is used to make allocnos go into regs that are copied to or from them,
144 when possible, to reduce register shuffling. */
146 static HARD_REG_SET
*hard_reg_preferences
;
148 /* Similar, but just counts register preferences made in simple copy
149 operations, rather than arithmetic. These are given priority because
150 we can always eliminate an insn by using these, but using a register
151 in the above list won't always eliminate an insn. */
153 static HARD_REG_SET
*hard_reg_copy_preferences
;
155 /* Similar to hard_reg_preferences, but includes bits for subsequent
156 registers when an allocno is multi-word. The above variable is used for
157 allocation while this is used to build reg_someone_prefers, below. */
159 static HARD_REG_SET
*hard_reg_full_preferences
;
161 /* Indexed by N, set of hard registers that some later allocno has a
164 static HARD_REG_SET
*regs_someone_prefers
;
166 /* Set of registers that global-alloc isn't supposed to use. */
168 static HARD_REG_SET no_global_alloc_regs
;
170 /* Set of registers used so far. */
172 static HARD_REG_SET regs_used_so_far
;
174 /* Number of calls crossed by each allocno. */
176 static int *allocno_calls_crossed
;
178 /* Number of refs (weighted) to each allocno. */
180 static int *allocno_n_refs
;
182 /* Guess at live length of each allocno.
183 This is actually the max of the live lengths of the regs. */
185 static int *allocno_live_length
;
187 /* Number of refs (weighted) to each hard reg, as used by local alloc.
188 It is zero for a reg that contains global pseudos or is explicitly used. */
190 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
192 /* Guess at live length of each hard reg, as used by local alloc.
193 This is actually the sum of the live lengths of the specific regs. */
195 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
197 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
198 for vector element I, and hard register number J. */
200 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
202 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
204 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
206 /* Bit mask for allocnos live at current point in the scan. */
208 static INT_TYPE
*allocnos_live
;
210 /* Test, set or clear bit number I in allocnos_live,
211 a bit vector indexed by allocno. */
213 #define ALLOCNO_LIVE_P(I) \
214 (allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS)))
216 #define SET_ALLOCNO_LIVE(I) \
217 (allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS)))
219 #define CLEAR_ALLOCNO_LIVE(I) \
220 (allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((I) % INT_BITS)))
222 /* This is turned off because it doesn't work right for DImode.
223 (And it is only used for DImode, so the other cases are worthless.)
224 The problem is that it isn't true that there is NO possibility of conflict;
225 only that there is no conflict if the two pseudos get the exact same regs.
226 If they were allocated with a partial overlap, there would be a conflict.
227 We can't safely turn off the conflict unless we have another way to
228 prevent the partial overlap.
230 Idea: change hard_reg_conflicts so that instead of recording which
231 hard regs the allocno may not overlap, it records where the allocno
232 may not start. Change both where it is used and where it is updated.
233 Then there is a way to record that (reg:DI 108) may start at 10
234 but not at 9 or 11. There is still the question of how to record
235 this semi-conflict between two pseudos. */
237 /* Reg pairs for which conflict after the current insn
238 is inhibited by a REG_NO_CONFLICT note.
239 If the table gets full, we ignore any other notes--that is conservative. */
240 #define NUM_NO_CONFLICT_PAIRS 4
241 /* Number of pairs in use in this insn. */
242 int n_no_conflict_pairs
;
243 static struct { int allocno1
, allocno2
;}
244 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
247 /* Record all regs that are set in any one insn.
248 Communication from mark_reg_{store,clobber} and global_conflicts. */
250 static rtx
*regs_set
;
251 static int n_regs_set
;
253 /* All registers that can be eliminated. */
255 static HARD_REG_SET eliminable_regset
;
257 static int allocno_compare
PROTO((const GENERIC_PTR
, const GENERIC_PTR
));
258 static void global_conflicts
PROTO((void));
259 static void expand_preferences
PROTO((void));
260 static void prune_preferences
PROTO((void));
261 static void find_reg
PROTO((int, HARD_REG_SET
, int, int, int));
262 static void record_one_conflict
PROTO((int));
263 static void record_conflicts
PROTO((short *, int));
264 static void mark_reg_store
PROTO((rtx
, rtx
));
265 static void mark_reg_clobber
PROTO((rtx
, rtx
));
266 static void mark_reg_conflicts
PROTO((rtx
));
267 static void mark_reg_death
PROTO((rtx
));
268 static void mark_reg_live_nc
PROTO((int, enum machine_mode
));
269 static void set_preference
PROTO((rtx
, rtx
));
270 static void dump_conflicts
PROTO((FILE *));
272 /* Perform allocation of pseudo-registers not allocated by local_alloc.
273 FILE is a file to output debugging information on,
274 or zero if such output is not desired.
276 Return value is nonzero if reload failed
277 and we must not do any more for this function. */
284 #ifdef ELIMINABLE_REGS
285 static struct {int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
288 = (! flag_omit_frame_pointer
289 #ifdef EXIT_IGNORE_STACK
290 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
292 || FRAME_POINTER_REQUIRED
);
299 /* A machine may have certain hard registers that
300 are safe to use only within a basic block. */
302 CLEAR_HARD_REG_SET (no_global_alloc_regs
);
303 #ifdef OVERLAPPING_REGNO_P
304 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
305 if (OVERLAPPING_REGNO_P (i
))
306 SET_HARD_REG_BIT (no_global_alloc_regs
, i
);
309 /* Build the regset of all eliminable registers and show we can't use those
310 that we already know won't be eliminated. */
311 #ifdef ELIMINABLE_REGS
312 for (i
= 0; i
< sizeof eliminables
/ sizeof eliminables
[0]; i
++)
314 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
316 if (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
317 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
))
318 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
320 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
321 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
323 SET_HARD_REG_BIT (no_global_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
327 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
329 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
332 /* Track which registers have already been used. Start with registers
333 explicitly in the rtl, then registers allocated by local register
336 CLEAR_HARD_REG_SET (regs_used_so_far
);
337 #ifdef LEAF_REGISTERS
338 /* If we are doing the leaf function optimization, and this is a leaf
339 function, it means that the registers that take work to save are those
340 that need a register window. So prefer the ones that can be used in
344 static char leaf_regs
[] = LEAF_REGISTERS
;
346 if (only_leaf_regs_used () && leaf_function_p ())
347 cheap_regs
= leaf_regs
;
349 cheap_regs
= call_used_regs
;
350 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
351 if (regs_ever_live
[i
] || cheap_regs
[i
])
352 SET_HARD_REG_BIT (regs_used_so_far
, i
);
355 /* We consider registers that do not have to be saved over calls as if
356 they were already used since there is no cost in using them. */
357 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
358 if (regs_ever_live
[i
] || call_used_regs
[i
])
359 SET_HARD_REG_BIT (regs_used_so_far
, i
);
362 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
363 if (reg_renumber
[i
] >= 0)
364 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
366 /* Establish mappings from register number to allocation number
367 and vice versa. In the process, count the allocnos. */
369 reg_allocno
= (int *) alloca (max_regno
* sizeof (int));
371 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
374 /* Initialize the shared-hard-reg mapping
375 from the list of pairs that may share. */
376 reg_may_share
= (int *) alloca (max_regno
* sizeof (int));
377 bzero ((char *) reg_may_share
, max_regno
* sizeof (int));
378 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
380 int r1
= REGNO (XEXP (x
, 0));
381 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
383 reg_may_share
[r1
] = r2
;
385 reg_may_share
[r2
] = r1
;
388 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
389 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
390 that we are supposed to refrain from putting in a hard reg.
391 -2 means do make an allocno but don't allocate it. */
392 if (REG_N_REFS (i
) != 0 && REG_LIVE_LENGTH (i
) != -1
393 /* Don't allocate pseudos that cross calls,
394 if this function receives a nonlocal goto. */
395 && (! current_function_has_nonlocal_label
396 || REG_N_CALLS_CROSSED (i
) == 0))
398 if (reg_renumber
[i
] < 0 && reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
399 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
401 reg_allocno
[i
] = max_allocno
++;
402 if (REG_LIVE_LENGTH (i
) == 0)
408 allocno_reg
= (int *) alloca (max_allocno
* sizeof (int));
409 allocno_size
= (int *) alloca (max_allocno
* sizeof (int));
410 allocno_calls_crossed
= (int *) alloca (max_allocno
* sizeof (int));
411 allocno_n_refs
= (int *) alloca (max_allocno
* sizeof (int));
412 allocno_live_length
= (int *) alloca (max_allocno
* sizeof (int));
413 bzero ((char *) allocno_size
, max_allocno
* sizeof (int));
414 bzero ((char *) allocno_calls_crossed
, max_allocno
* sizeof (int));
415 bzero ((char *) allocno_n_refs
, max_allocno
* sizeof (int));
416 bzero ((char *) allocno_live_length
, max_allocno
* sizeof (int));
418 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
419 if (reg_allocno
[i
] >= 0)
421 int allocno
= reg_allocno
[i
];
422 allocno_reg
[allocno
] = i
;
423 allocno_size
[allocno
] = PSEUDO_REGNO_SIZE (i
);
424 allocno_calls_crossed
[allocno
] += REG_N_CALLS_CROSSED (i
);
425 allocno_n_refs
[allocno
] += REG_N_REFS (i
);
426 if (allocno_live_length
[allocno
] < REG_LIVE_LENGTH (i
))
427 allocno_live_length
[allocno
] = REG_LIVE_LENGTH (i
);
430 /* Calculate amount of usage of each hard reg by pseudos
431 allocated by local-alloc. This is to see if we want to
433 bzero ((char *) local_reg_live_length
, sizeof local_reg_live_length
);
434 bzero ((char *) local_reg_n_refs
, sizeof local_reg_n_refs
);
435 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
436 if (reg_renumber
[i
] >= 0)
438 int regno
= reg_renumber
[i
];
439 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (i
));
442 for (j
= regno
; j
< endregno
; j
++)
444 local_reg_n_refs
[j
] += REG_N_REFS (i
);
445 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
449 /* We can't override local-alloc for a reg used not just by local-alloc. */
450 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
451 if (regs_ever_live
[i
])
452 local_reg_n_refs
[i
] = 0;
454 /* Likewise for regs used in a SCRATCH. */
455 for (i
= 0; i
< scratch_list_length
; i
++)
458 int regno
= REGNO (scratch_list
[i
]);
459 int lim
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (scratch_list
[i
]));
462 for (j
= regno
; j
< lim
; j
++)
463 local_reg_n_refs
[j
] = 0;
466 /* Allocate the space for the conflict and preference tables and
470 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
471 bzero ((char *) hard_reg_conflicts
, max_allocno
* sizeof (HARD_REG_SET
));
474 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
475 bzero ((char *) hard_reg_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
477 hard_reg_copy_preferences
478 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
479 bzero ((char *) hard_reg_copy_preferences
,
480 max_allocno
* sizeof (HARD_REG_SET
));
482 hard_reg_full_preferences
483 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
484 bzero ((char *) hard_reg_full_preferences
,
485 max_allocno
* sizeof (HARD_REG_SET
));
488 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
489 bzero ((char *) regs_someone_prefers
, max_allocno
* sizeof (HARD_REG_SET
));
491 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
493 /* We used to use alloca here, but the size of what it would try to
494 allocate would occasionally cause it to exceed the stack limit and
495 cause unpredictable core dumps. Some examples were > 2Mb in size. */
496 conflicts
= (INT_TYPE
*) xmalloc (max_allocno
* allocno_row_words
497 * sizeof (INT_TYPE
));
498 bzero ((char *) conflicts
,
499 max_allocno
* allocno_row_words
* sizeof (INT_TYPE
));
501 allocnos_live
= (INT_TYPE
*) alloca (allocno_row_words
* sizeof (INT_TYPE
));
503 /* If there is work to be done (at least one reg to allocate),
504 perform global conflict analysis and allocate the regs. */
508 /* Scan all the insns and compute the conflicts among allocnos
509 and between allocnos and hard regs. */
513 /* Eliminate conflicts between pseudos and eliminable registers. If
514 the register is not eliminated, the pseudo won't really be able to
515 live in the eliminable register, so the conflict doesn't matter.
516 If we do eliminate the register, the conflict will no longer exist.
517 So in either case, we can ignore the conflict. Likewise for
520 for (i
= 0; i
< max_allocno
; i
++)
522 AND_COMPL_HARD_REG_SET (hard_reg_conflicts
[i
], eliminable_regset
);
523 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[i
],
525 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[i
], eliminable_regset
);
528 /* Try to expand the preferences by merging them between allocnos. */
530 expand_preferences ();
532 /* Determine the order to allocate the remaining pseudo registers. */
534 allocno_order
= (int *) alloca (max_allocno
* sizeof (int));
535 for (i
= 0; i
< max_allocno
; i
++)
536 allocno_order
[i
] = i
;
538 /* Default the size to 1, since allocno_compare uses it to divide by.
539 Also convert allocno_live_length of zero to -1. A length of zero
540 can occur when all the registers for that allocno have reg_live_length
541 equal to -2. In this case, we want to make an allocno, but not
542 allocate it. So avoid the divide-by-zero and set it to a low
545 for (i
= 0; i
< max_allocno
; i
++)
547 if (allocno_size
[i
] == 0)
549 if (allocno_live_length
[i
] == 0)
550 allocno_live_length
[i
] = -1;
553 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
555 prune_preferences ();
558 dump_conflicts (file
);
560 /* Try allocating them, one by one, in that order,
561 except for parameters marked with reg_live_length[regno] == -2. */
563 for (i
= 0; i
< max_allocno
; i
++)
564 if (reg_renumber
[allocno_reg
[allocno_order
[i
]]] < 0
565 && REG_LIVE_LENGTH (allocno_reg
[allocno_order
[i
]]) >= 0)
567 /* If we have more than one register class,
568 first try allocating in the class that is cheapest
569 for this pseudo-reg. If that fails, try any reg. */
570 if (N_REG_CLASSES
> 1)
572 find_reg (allocno_order
[i
], 0, 0, 0, 0);
573 if (reg_renumber
[allocno_reg
[allocno_order
[i
]]] >= 0)
576 if (reg_alternate_class (allocno_reg
[allocno_order
[i
]]) != NO_REGS
)
577 find_reg (allocno_order
[i
], 0, 1, 0, 0);
581 /* Do the reloads now while the allocno data still exist, so that we can
582 try to assign new hard regs to any pseudo regs that are spilled. */
584 #if 0 /* We need to eliminate regs even if there is no rtl code,
585 for the sake of debugging information. */
586 if (n_basic_blocks
> 0)
588 retval
= reload (get_insns (), 1, file
);
594 /* Sort predicate for ordering the allocnos.
595 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
598 allocno_compare (v1p
, v2p
)
599 const GENERIC_PTR v1p
;
600 const GENERIC_PTR v2p
;
602 int v1
= *(int *)v1p
, v2
= *(int *)v2p
;
603 /* Note that the quotient will never be bigger than
604 the value of floor_log2 times the maximum number of
605 times a register can occur in one insn (surely less than 100).
606 Multiplying this by 10000 can't overflow. */
608 = (((double) (floor_log2 (allocno_n_refs
[v1
]) * allocno_n_refs
[v1
])
609 / allocno_live_length
[v1
])
610 * 10000 * allocno_size
[v1
]);
612 = (((double) (floor_log2 (allocno_n_refs
[v2
]) * allocno_n_refs
[v2
])
613 / allocno_live_length
[v2
])
614 * 10000 * allocno_size
[v2
]);
618 /* If regs are equally good, sort by allocno,
619 so that the results of qsort leave nothing to chance. */
623 /* Scan the rtl code and record all conflicts and register preferences in the
624 conflict matrices and preference tables. */
631 short *block_start_allocnos
;
633 /* Make a vector that mark_reg_{store,clobber} will store in. */
634 regs_set
= (rtx
*) alloca (max_parallel
* sizeof (rtx
) * 2);
636 block_start_allocnos
= (short *) alloca (max_allocno
* sizeof (short));
638 for (b
= 0; b
< n_basic_blocks
; b
++)
640 bzero ((char *) allocnos_live
, allocno_row_words
* sizeof (INT_TYPE
));
642 /* Initialize table of registers currently live
643 to the state at the beginning of this basic block.
644 This also marks the conflicts among them.
646 For pseudo-regs, there is only one bit for each one
647 no matter how many hard regs it occupies.
648 This is ok; we know the size from PSEUDO_REGNO_SIZE.
649 For explicit hard regs, we cannot know the size that way
650 since one hard reg can be used with various sizes.
651 Therefore, we must require that all the hard regs
652 implicitly live as part of a multi-word hard reg
653 are explicitly marked in basic_block_live_at_start. */
656 register regset old
= basic_block_live_at_start
[b
];
659 REG_SET_TO_HARD_REG_SET (hard_regs_live
, old
);
660 EXECUTE_IF_SET_IN_REG_SET (old
, FIRST_PSEUDO_REGISTER
, i
,
662 register int a
= reg_allocno
[i
];
665 SET_ALLOCNO_LIVE (a
);
666 block_start_allocnos
[ax
++] = a
;
668 else if ((a
= reg_renumber
[i
]) >= 0)
670 (a
, PSEUDO_REGNO_MODE (i
));
673 /* Record that each allocno now live conflicts with each other
674 allocno now live, and with each hard reg now live. */
676 record_conflicts (block_start_allocnos
, ax
);
679 /* Pseudos can't go in stack regs at the start of a basic block
680 that can be reached through a computed goto, since reg-stack
681 can't handle computed gotos. */
682 if (basic_block_computed_jump_target
[b
])
683 for (ax
= FIRST_STACK_REG
; ax
<= LAST_STACK_REG
; ax
++)
684 record_one_conflict (ax
);
688 insn
= basic_block_head
[b
];
690 /* Scan the code of this basic block, noting which allocnos
691 and hard regs are born or die. When one is born,
692 record a conflict with all others currently live. */
696 register RTX_CODE code
= GET_CODE (insn
);
699 /* Make regs_set an empty set. */
703 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
708 for (link
= REG_NOTES (insn
);
709 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
710 link
= XEXP (link
, 1))
711 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
713 no_conflict_pairs
[i
].allocno1
714 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
715 no_conflict_pairs
[i
].allocno2
716 = reg_allocno
[REGNO (XEXP (link
, 0))];
721 /* Mark any registers clobbered by INSN as live,
722 so they conflict with the inputs. */
724 note_stores (PATTERN (insn
), mark_reg_clobber
);
726 /* Mark any registers dead after INSN as dead now. */
728 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
729 if (REG_NOTE_KIND (link
) == REG_DEAD
)
730 mark_reg_death (XEXP (link
, 0));
732 /* Mark any registers set in INSN as live,
733 and mark them as conflicting with all other live regs.
734 Clobbers are processed again, so they conflict with
735 the registers that are set. */
737 note_stores (PATTERN (insn
), mark_reg_store
);
740 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
741 if (REG_NOTE_KIND (link
) == REG_INC
)
742 mark_reg_store (XEXP (link
, 0), NULL_RTX
);
745 /* If INSN has multiple outputs, then any reg that dies here
746 and is used inside of an output
747 must conflict with the other outputs. */
749 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& !single_set (insn
))
750 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
751 if (REG_NOTE_KIND (link
) == REG_DEAD
)
753 int used_in_output
= 0;
755 rtx reg
= XEXP (link
, 0);
757 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
759 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
760 if (GET_CODE (set
) == SET
761 && GET_CODE (SET_DEST (set
)) != REG
762 && !rtx_equal_p (reg
, SET_DEST (set
))
763 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
767 mark_reg_conflicts (reg
);
770 /* Mark any registers set in INSN and then never used. */
772 while (n_regs_set
> 0)
773 if (find_regno_note (insn
, REG_UNUSED
,
774 REGNO (regs_set
[--n_regs_set
])))
775 mark_reg_death (regs_set
[n_regs_set
]);
778 if (insn
== basic_block_end
[b
])
780 insn
= NEXT_INSN (insn
);
784 /* Expand the preference information by looking for cases where one allocno
785 dies in an insn that sets an allocno. If those two allocnos don't conflict,
786 merge any preferences between those allocnos. */
789 expand_preferences ()
795 /* We only try to handle the most common cases here. Most of the cases
796 where this wins are reg-reg copies. */
798 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
799 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
800 && (set
= single_set (insn
)) != 0
801 && GET_CODE (SET_DEST (set
)) == REG
802 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
803 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
804 if (REG_NOTE_KIND (link
) == REG_DEAD
805 && GET_CODE (XEXP (link
, 0)) == REG
806 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
807 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
808 reg_allocno
[REGNO (XEXP (link
, 0))])
809 && ! CONFLICTP (reg_allocno
[REGNO (XEXP (link
, 0))],
810 reg_allocno
[REGNO (SET_DEST (set
))]))
812 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
813 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
815 if (XEXP (link
, 0) == SET_SRC (set
))
817 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a1
],
818 hard_reg_copy_preferences
[a2
]);
819 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a2
],
820 hard_reg_copy_preferences
[a1
]);
823 IOR_HARD_REG_SET (hard_reg_preferences
[a1
],
824 hard_reg_preferences
[a2
]);
825 IOR_HARD_REG_SET (hard_reg_preferences
[a2
],
826 hard_reg_preferences
[a1
]);
827 IOR_HARD_REG_SET (hard_reg_full_preferences
[a1
],
828 hard_reg_full_preferences
[a2
]);
829 IOR_HARD_REG_SET (hard_reg_full_preferences
[a2
],
830 hard_reg_full_preferences
[a1
]);
834 /* Prune the preferences for global registers to exclude registers that cannot
837 Compute `regs_someone_prefers', which is a bitmask of the hard registers
838 that are preferred by conflicting registers of lower priority. If possible,
839 we will avoid using these registers. */
847 /* Scan least most important to most important.
848 For each allocno, remove from preferences registers that cannot be used,
849 either because of conflicts or register type. Then compute all registers
850 preferred by each lower-priority register that conflicts. */
852 for (i
= max_allocno
- 1; i
>= 0; i
--)
856 allocno
= allocno_order
[i
];
857 COPY_HARD_REG_SET (temp
, hard_reg_conflicts
[allocno
]);
859 if (allocno_calls_crossed
[allocno
] == 0)
860 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
862 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
864 IOR_COMPL_HARD_REG_SET
866 reg_class_contents
[(int) reg_preferred_class (allocno_reg
[allocno
])]);
868 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], temp
);
869 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], temp
);
870 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences
[allocno
], temp
);
872 CLEAR_HARD_REG_SET (regs_someone_prefers
[allocno
]);
874 /* Merge in the preferences of lower-priority registers (they have
875 already been pruned). If we also prefer some of those registers,
876 don't exclude them unless we are of a smaller size (in which case
877 we want to give the lower-priority allocno the first chance for
879 for (j
= i
+ 1; j
< max_allocno
; j
++)
880 if (CONFLICTP (allocno
, allocno_order
[j
])
881 || CONFLICTP (allocno_order
[j
], allocno
))
883 COPY_HARD_REG_SET (temp
,
884 hard_reg_full_preferences
[allocno_order
[j
]]);
885 if (allocno_size
[allocno_order
[j
]] <= allocno_size
[allocno
])
886 AND_COMPL_HARD_REG_SET (temp
,
887 hard_reg_full_preferences
[allocno
]);
889 IOR_HARD_REG_SET (regs_someone_prefers
[allocno
], temp
);
894 /* Assign a hard register to ALLOCNO; look for one that is the beginning
895 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
896 The registers marked in PREFREGS are tried first.
898 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
899 be used for this allocation.
901 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
902 Otherwise ignore that preferred class and use the alternate class.
904 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
905 will have to be saved and restored at calls.
907 RETRYING is nonzero if this is called from retry_global_alloc.
909 If we find one, record it in reg_renumber.
910 If not, do nothing. */
913 find_reg (allocno
, losers
, alt_regs_p
, accept_call_clobbered
, retrying
)
917 int accept_call_clobbered
;
920 register int i
, best_reg
, pass
;
922 register /* Declare it register if it's a scalar. */
924 HARD_REG_SET used
, used1
, used2
;
926 enum reg_class
class = (alt_regs_p
927 ? reg_alternate_class (allocno_reg
[allocno
])
928 : reg_preferred_class (allocno_reg
[allocno
]));
929 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno_reg
[allocno
]);
931 if (accept_call_clobbered
)
932 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
933 else if (allocno_calls_crossed
[allocno
] == 0)
934 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
936 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
938 /* Some registers should not be allocated in global-alloc. */
939 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
941 IOR_HARD_REG_SET (used1
, losers
);
943 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
944 COPY_HARD_REG_SET (used2
, used1
);
946 IOR_HARD_REG_SET (used1
, hard_reg_conflicts
[allocno
]);
948 #ifdef CLASS_CANNOT_CHANGE_SIZE
949 if (REG_CHANGES_SIZE (allocno_reg
[allocno
]))
950 IOR_HARD_REG_SET (used1
,
951 reg_class_contents
[(int) CLASS_CANNOT_CHANGE_SIZE
]);
954 /* Try each hard reg to see if it fits. Do this in two passes.
955 In the first pass, skip registers that are preferred by some other pseudo
956 to give it a better chance of getting one of those registers. Only if
957 we can't get a register when excluding those do we take one of them.
958 However, we never allocate a register for the first time in pass 0. */
960 COPY_HARD_REG_SET (used
, used1
);
961 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
962 IOR_HARD_REG_SET (used
, regs_someone_prefers
[allocno
]);
965 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
966 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
970 COPY_HARD_REG_SET (used
, used1
);
971 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
973 #ifdef REG_ALLOC_ORDER
974 int regno
= reg_alloc_order
[i
];
978 if (! TEST_HARD_REG_BIT (used
, regno
)
979 && HARD_REGNO_MODE_OK (regno
, mode
)
980 && (allocno_calls_crossed
[allocno
] == 0
981 || accept_call_clobbered
982 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
)))
985 register int lim
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
988 && ! TEST_HARD_REG_BIT (used
, j
));
995 #ifndef REG_ALLOC_ORDER
996 i
= j
; /* Skip starting points we know will lose */
1002 /* See if there is a preferred register with the same class as the register
1003 we allocated above. Making this restriction prevents register
1004 preferencing from creating worse register allocation.
1006 Remove from the preferred registers and conflicting registers. Note that
1007 additional conflicts may have been added after `prune_preferences' was
1010 First do this for those register with copy preferences, then all
1011 preferred registers. */
1013 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], used
);
1014 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences
[allocno
],
1015 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
1019 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1020 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences
[allocno
], i
)
1021 && HARD_REGNO_MODE_OK (i
, mode
)
1022 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1023 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1024 REGNO_REG_CLASS (best_reg
))
1025 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1026 REGNO_REG_CLASS (i
))))
1029 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1032 && ! TEST_HARD_REG_BIT (used
, j
)
1033 && (REGNO_REG_CLASS (j
)
1034 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1035 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1036 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1037 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1038 REGNO_REG_CLASS (j
))));
1049 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], used
);
1050 GO_IF_HARD_REG_SUBSET (hard_reg_preferences
[allocno
],
1051 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1055 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1056 if (TEST_HARD_REG_BIT (hard_reg_preferences
[allocno
], i
)
1057 && HARD_REGNO_MODE_OK (i
, mode
)
1058 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1059 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1060 REGNO_REG_CLASS (best_reg
))
1061 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1062 REGNO_REG_CLASS (i
))))
1065 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1068 && ! TEST_HARD_REG_BIT (used
, j
)
1069 && (REGNO_REG_CLASS (j
)
1070 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1071 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1072 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1073 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1074 REGNO_REG_CLASS (j
))));
1085 /* If we haven't succeeded yet, try with caller-saves.
1086 We need not check to see if the current function has nonlocal
1087 labels because we don't put any pseudos that are live over calls in
1088 registers in that case. */
1090 if (flag_caller_saves
&& best_reg
< 0)
1092 /* Did not find a register. If it would be profitable to
1093 allocate a call-clobbered register and save and restore it
1094 around calls, do that. */
1095 if (! accept_call_clobbered
1096 && allocno_calls_crossed
[allocno
] != 0
1097 && CALLER_SAVE_PROFITABLE (allocno_n_refs
[allocno
],
1098 allocno_calls_crossed
[allocno
]))
1100 HARD_REG_SET new_losers
;
1102 CLEAR_HARD_REG_SET (new_losers
);
1104 COPY_HARD_REG_SET (new_losers
, losers
);
1106 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1107 find_reg (allocno
, new_losers
, alt_regs_p
, 1, retrying
);
1108 if (reg_renumber
[allocno_reg
[allocno
]] >= 0)
1110 caller_save_needed
= 1;
1116 /* If we haven't succeeded yet,
1117 see if some hard reg that conflicts with us
1118 was utilized poorly by local-alloc.
1119 If so, kick out the regs that were put there by local-alloc
1120 so we can use it instead. */
1121 if (best_reg
< 0 && !retrying
1122 /* Let's not bother with multi-reg allocnos. */
1123 && allocno_size
[allocno
] == 1)
1125 /* Count from the end, to find the least-used ones first. */
1126 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1128 #ifdef REG_ALLOC_ORDER
1129 int regno
= reg_alloc_order
[i
];
1134 if (local_reg_n_refs
[regno
] != 0
1135 /* Don't use a reg no good for this pseudo. */
1136 && ! TEST_HARD_REG_BIT (used2
, regno
)
1137 && HARD_REGNO_MODE_OK (regno
, mode
)
1138 #ifdef CLASS_CANNOT_CHANGE_SIZE
1139 && ! (REG_CHANGES_SIZE (allocno_reg
[allocno
])
1140 && (TEST_HARD_REG_BIT
1141 (reg_class_contents
[(int) CLASS_CANNOT_CHANGE_SIZE
],
1146 /* We explicitly evaluate the divide results into temporary
1147 variables so as to avoid excess precision problems that occur
1148 on a i386-unknown-sysv4.2 (unixware) host. */
1150 double tmp1
= ((double) local_reg_n_refs
[regno
]
1151 / local_reg_live_length
[regno
]);
1152 double tmp2
= ((double) allocno_n_refs
[allocno
]
1153 / allocno_live_length
[allocno
]);
1157 /* Hard reg REGNO was used less in total by local regs
1158 than it would be used by this one allocno! */
1160 for (k
= 0; k
< max_regno
; k
++)
1161 if (reg_renumber
[k
] >= 0)
1163 int r
= reg_renumber
[k
];
1165 = r
+ HARD_REGNO_NREGS (r
, PSEUDO_REGNO_MODE (k
));
1167 if (regno
>= r
&& regno
< endregno
)
1168 reg_renumber
[k
] = -1;
1178 /* Did we find a register? */
1182 register int lim
, j
;
1183 HARD_REG_SET this_reg
;
1185 /* Yes. Record it as the hard register of this pseudo-reg. */
1186 reg_renumber
[allocno_reg
[allocno
]] = best_reg
;
1187 /* Also of any pseudo-regs that share with it. */
1188 if (reg_may_share
[allocno_reg
[allocno
]])
1189 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1190 if (reg_allocno
[j
] == allocno
)
1191 reg_renumber
[j
] = best_reg
;
1193 /* Make a set of the hard regs being allocated. */
1194 CLEAR_HARD_REG_SET (this_reg
);
1195 lim
= best_reg
+ HARD_REGNO_NREGS (best_reg
, mode
);
1196 for (j
= best_reg
; j
< lim
; j
++)
1198 SET_HARD_REG_BIT (this_reg
, j
);
1199 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1200 /* This is no longer a reg used just by local regs. */
1201 local_reg_n_refs
[j
] = 0;
1203 /* For each other pseudo-reg conflicting with this one,
1204 mark it as conflicting with the hard regs this one occupies. */
1206 for (j
= 0; j
< max_allocno
; j
++)
1207 if (CONFLICTP (lim
, j
) || CONFLICTP (j
, lim
))
1209 IOR_HARD_REG_SET (hard_reg_conflicts
[j
], this_reg
);
1214 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1215 Perhaps it had previously seemed not worth a hard reg,
1216 or perhaps its old hard reg has been commandeered for reloads.
1217 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1218 they do not appear to be allocated.
1219 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1222 retry_global_alloc (regno
, forbidden_regs
)
1224 HARD_REG_SET forbidden_regs
;
1226 int allocno
= reg_allocno
[regno
];
1229 /* If we have more than one register class,
1230 first try allocating in the class that is cheapest
1231 for this pseudo-reg. If that fails, try any reg. */
1232 if (N_REG_CLASSES
> 1)
1233 find_reg (allocno
, forbidden_regs
, 0, 0, 1);
1234 if (reg_renumber
[regno
] < 0
1235 && reg_alternate_class (regno
) != NO_REGS
)
1236 find_reg (allocno
, forbidden_regs
, 1, 0, 1);
1238 /* If we found a register, modify the RTL for the register to
1239 show the hard register, and mark that register live. */
1240 if (reg_renumber
[regno
] >= 0)
1242 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1243 mark_home_live (regno
);
1248 /* Record a conflict between register REGNO
1249 and everything currently live.
1250 REGNO must not be a pseudo reg that was allocated
1251 by local_alloc; such numbers must be translated through
1252 reg_renumber before calling here. */
1255 record_one_conflict (regno
)
1260 if (regno
< FIRST_PSEUDO_REGISTER
)
1261 /* When a hard register becomes live,
1262 record conflicts with live pseudo regs. */
1263 for (j
= 0; j
< max_allocno
; j
++)
1265 if (ALLOCNO_LIVE_P (j
))
1266 SET_HARD_REG_BIT (hard_reg_conflicts
[j
], regno
);
1269 /* When a pseudo-register becomes live,
1270 record conflicts first with hard regs,
1271 then with other pseudo regs. */
1273 register int ialloc
= reg_allocno
[regno
];
1274 register int ialloc_prod
= ialloc
* allocno_row_words
;
1275 IOR_HARD_REG_SET (hard_reg_conflicts
[ialloc
], hard_regs_live
);
1276 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1280 for (k
= 0; k
< n_no_conflict_pairs
; k
++)
1281 if (! ((j
== no_conflict_pairs
[k
].allocno1
1282 && ialloc
== no_conflict_pairs
[k
].allocno2
)
1284 (j
== no_conflict_pairs
[k
].allocno2
1285 && ialloc
== no_conflict_pairs
[k
].allocno1
)))
1287 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1292 /* Record all allocnos currently live as conflicting
1293 with each other and with all hard regs currently live.
1294 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1295 are currently live. Their bits are also flagged in allocnos_live. */
1298 record_conflicts (allocno_vec
, len
)
1299 register short *allocno_vec
;
1302 register int allocno
;
1304 register int ialloc_prod
;
1308 allocno
= allocno_vec
[len
];
1309 ialloc_prod
= allocno
* allocno_row_words
;
1310 IOR_HARD_REG_SET (hard_reg_conflicts
[allocno
], hard_regs_live
);
1311 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1312 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1316 /* Handle the case where REG is set by the insn being scanned,
1317 during the forward scan to accumulate conflicts.
1318 Store a 1 in regs_live or allocnos_live for this register, record how many
1319 consecutive hardware registers it actually needs,
1320 and record a conflict with all other registers already live.
1322 Note that even if REG does not remain alive after this insn,
1323 we must mark it here as live, to ensure a conflict between
1324 REG and any other regs set in this insn that really do live.
1325 This is because those other regs could be considered after this.
1327 REG might actually be something other than a register;
1328 if so, we do nothing.
1330 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1331 a REG_INC note was found for it).
1333 CLOBBERs are processed here by calling mark_reg_clobber. */
1336 mark_reg_store (orig_reg
, setter
)
1337 rtx orig_reg
, setter
;
1340 register rtx reg
= orig_reg
;
1342 /* WORD is which word of a multi-register group is being stored.
1343 For the case where the store is actually into a SUBREG of REG.
1344 Except we don't use it; I believe the entire REG needs to be
1348 if (GET_CODE (reg
) == SUBREG
)
1350 word
= SUBREG_WORD (reg
);
1351 reg
= SUBREG_REG (reg
);
1354 if (GET_CODE (reg
) != REG
)
1357 if (setter
&& GET_CODE (setter
) == CLOBBER
)
1359 /* A clobber of a register should be processed here too. */
1360 mark_reg_clobber (orig_reg
, setter
);
1364 regs_set
[n_regs_set
++] = reg
;
1367 set_preference (reg
, SET_SRC (setter
));
1369 regno
= REGNO (reg
);
1371 /* Either this is one of the max_allocno pseudo regs not allocated,
1372 or it is or has a hardware reg. First handle the pseudo-regs. */
1373 if (regno
>= FIRST_PSEUDO_REGISTER
)
1375 if (reg_allocno
[regno
] >= 0)
1377 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1378 record_one_conflict (regno
);
1382 if (reg_renumber
[regno
] >= 0)
1383 regno
= reg_renumber
[regno
] /* + word */;
1385 /* Handle hardware regs (and pseudos allocated to hard regs). */
1386 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1388 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1389 while (regno
< last
)
1391 record_one_conflict (regno
);
1392 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1398 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1401 mark_reg_clobber (reg
, setter
)
1406 /* WORD is which word of a multi-register group is being stored.
1407 For the case where the store is actually into a SUBREG of REG.
1408 Except we don't use it; I believe the entire REG needs to be
1412 if (GET_CODE (setter
) != CLOBBER
)
1415 if (GET_CODE (reg
) == SUBREG
)
1417 word
= SUBREG_WORD (reg
);
1418 reg
= SUBREG_REG (reg
);
1421 if (GET_CODE (reg
) != REG
)
1424 regs_set
[n_regs_set
++] = reg
;
1426 regno
= REGNO (reg
);
1428 /* Either this is one of the max_allocno pseudo regs not allocated,
1429 or it is or has a hardware reg. First handle the pseudo-regs. */
1430 if (regno
>= FIRST_PSEUDO_REGISTER
)
1432 if (reg_allocno
[regno
] >= 0)
1434 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1435 record_one_conflict (regno
);
1439 if (reg_renumber
[regno
] >= 0)
1440 regno
= reg_renumber
[regno
] /* + word */;
1442 /* Handle hardware regs (and pseudos allocated to hard regs). */
1443 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1445 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1446 while (regno
< last
)
1448 record_one_conflict (regno
);
1449 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1455 /* Record that REG has conflicts with all the regs currently live.
1456 Do not mark REG itself as live. */
1459 mark_reg_conflicts (reg
)
1464 if (GET_CODE (reg
) == SUBREG
)
1465 reg
= SUBREG_REG (reg
);
1467 if (GET_CODE (reg
) != REG
)
1470 regno
= REGNO (reg
);
1472 /* Either this is one of the max_allocno pseudo regs not allocated,
1473 or it is or has a hardware reg. First handle the pseudo-regs. */
1474 if (regno
>= FIRST_PSEUDO_REGISTER
)
1476 if (reg_allocno
[regno
] >= 0)
1477 record_one_conflict (regno
);
1480 if (reg_renumber
[regno
] >= 0)
1481 regno
= reg_renumber
[regno
];
1483 /* Handle hardware regs (and pseudos allocated to hard regs). */
1484 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1486 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1487 while (regno
< last
)
1489 record_one_conflict (regno
);
1495 /* Mark REG as being dead (following the insn being scanned now).
1496 Store a 0 in regs_live or allocnos_live for this register. */
1499 mark_reg_death (reg
)
1502 register int regno
= REGNO (reg
);
1504 /* Either this is one of the max_allocno pseudo regs not allocated,
1505 or it is a hardware reg. First handle the pseudo-regs. */
1506 if (regno
>= FIRST_PSEUDO_REGISTER
)
1508 if (reg_allocno
[regno
] >= 0)
1509 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1512 /* For pseudo reg, see if it has been assigned a hardware reg. */
1513 if (reg_renumber
[regno
] >= 0)
1514 regno
= reg_renumber
[regno
];
1516 /* Handle hardware regs (and pseudos allocated to hard regs). */
1517 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1519 /* Pseudo regs already assigned hardware regs are treated
1520 almost the same as explicit hardware regs. */
1521 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1522 while (regno
< last
)
1524 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1530 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1531 for the value stored in it. MODE determines how many consecutive
1532 registers are actually in use. Do not record conflicts;
1533 it is assumed that the caller will do that. */
1536 mark_reg_live_nc (regno
, mode
)
1538 enum machine_mode mode
;
1540 register int last
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1541 while (regno
< last
)
1543 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1548 /* Try to set a preference for an allocno to a hard register.
1549 We are passed DEST and SRC which are the operands of a SET. It is known
1550 that SRC is a register. If SRC or the first operand of SRC is a register,
1551 try to set a preference. If one of the two is a hard register and the other
1552 is a pseudo-register, mark the preference.
1554 Note that we are not as aggressive as local-alloc in trying to tie a
1555 pseudo-register to a hard register. */
1558 set_preference (dest
, src
)
1561 int src_regno
, dest_regno
;
1562 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1563 to compensate for subregs in SRC or DEST. */
1568 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1569 src
= XEXP (src
, 0), copy
= 0;
1571 /* Get the reg number for both SRC and DEST.
1572 If neither is a reg, give up. */
1574 if (GET_CODE (src
) == REG
)
1575 src_regno
= REGNO (src
);
1576 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1578 src_regno
= REGNO (SUBREG_REG (src
));
1579 offset
+= SUBREG_WORD (src
);
1584 if (GET_CODE (dest
) == REG
)
1585 dest_regno
= REGNO (dest
);
1586 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1588 dest_regno
= REGNO (SUBREG_REG (dest
));
1589 offset
-= SUBREG_WORD (dest
);
1594 /* Convert either or both to hard reg numbers. */
1596 if (reg_renumber
[src_regno
] >= 0)
1597 src_regno
= reg_renumber
[src_regno
];
1599 if (reg_renumber
[dest_regno
] >= 0)
1600 dest_regno
= reg_renumber
[dest_regno
];
1602 /* Now if one is a hard reg and the other is a global pseudo
1603 then give the other a preference. */
1605 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1606 && reg_allocno
[src_regno
] >= 0)
1608 dest_regno
-= offset
;
1609 if (dest_regno
>= 0 && dest_regno
< FIRST_PSEUDO_REGISTER
)
1612 SET_REGBIT (hard_reg_copy_preferences
,
1613 reg_allocno
[src_regno
], dest_regno
);
1615 SET_REGBIT (hard_reg_preferences
,
1616 reg_allocno
[src_regno
], dest_regno
);
1617 for (i
= dest_regno
;
1618 i
< dest_regno
+ HARD_REGNO_NREGS (dest_regno
, GET_MODE (dest
));
1620 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1624 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1625 && reg_allocno
[dest_regno
] >= 0)
1627 src_regno
+= offset
;
1628 if (src_regno
>= 0 && src_regno
< FIRST_PSEUDO_REGISTER
)
1631 SET_REGBIT (hard_reg_copy_preferences
,
1632 reg_allocno
[dest_regno
], src_regno
);
1634 SET_REGBIT (hard_reg_preferences
,
1635 reg_allocno
[dest_regno
], src_regno
);
1637 i
< src_regno
+ HARD_REGNO_NREGS (src_regno
, GET_MODE (src
));
1639 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1644 /* Indicate that hard register number FROM was eliminated and replaced with
1645 an offset from hard register number TO. The status of hard registers live
1646 at the start of a basic block is updated by replacing a use of FROM with
1650 mark_elimination (from
, to
)
1655 for (i
= 0; i
< n_basic_blocks
; i
++)
1656 if (REGNO_REG_SET_P (basic_block_live_at_start
[i
], from
))
1658 CLEAR_REGNO_REG_SET (basic_block_live_at_start
[i
], from
);
1659 SET_REGNO_REG_SET (basic_block_live_at_start
[i
], to
);
1663 /* Print debugging trace information if -greg switch is given,
1664 showing the information on which the allocation decisions are based. */
1667 dump_conflicts (file
)
1671 register int has_preferences
;
1674 for (i
= 0; i
< max_allocno
; i
++)
1676 if (reg_renumber
[allocno_reg
[allocno_order
[i
]]] >= 0)
1680 fprintf (file
, ";; %d regs to allocate:", nregs
);
1681 for (i
= 0; i
< max_allocno
; i
++)
1684 if (reg_renumber
[allocno_reg
[allocno_order
[i
]]] >= 0)
1686 fprintf (file
, " %d", allocno_reg
[allocno_order
[i
]]);
1687 for (j
= 0; j
< max_regno
; j
++)
1688 if (reg_allocno
[j
] == allocno_order
[i
]
1689 && j
!= allocno_reg
[allocno_order
[i
]])
1690 fprintf (file
, "+%d", j
);
1691 if (allocno_size
[allocno_order
[i
]] != 1)
1692 fprintf (file
, " (%d)", allocno_size
[allocno_order
[i
]]);
1694 fprintf (file
, "\n");
1696 for (i
= 0; i
< max_allocno
; i
++)
1699 fprintf (file
, ";; %d conflicts:", allocno_reg
[i
]);
1700 for (j
= 0; j
< max_allocno
; j
++)
1701 if (CONFLICTP (i
, j
) || CONFLICTP (j
, i
))
1702 fprintf (file
, " %d", allocno_reg
[j
]);
1703 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1704 if (TEST_HARD_REG_BIT (hard_reg_conflicts
[i
], j
))
1705 fprintf (file
, " %d", j
);
1706 fprintf (file
, "\n");
1708 has_preferences
= 0;
1709 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1710 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1711 has_preferences
= 1;
1713 if (! has_preferences
)
1715 fprintf (file
, ";; %d preferences:", allocno_reg
[i
]);
1716 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1717 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1718 fprintf (file
, " %d", j
);
1719 fprintf (file
, "\n");
1721 fprintf (file
, "\n");
1725 dump_global_regs (file
)
1730 fprintf (file
, ";; Register dispositions:\n");
1731 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1732 if (reg_renumber
[i
] >= 0)
1734 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1736 fprintf (file
, "\n");
1739 fprintf (file
, "\n\n;; Hard regs used: ");
1740 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1741 if (regs_ever_live
[i
])
1742 fprintf (file
, " %d", i
);
1743 fprintf (file
, "\n\n");