1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 1988, 1991, 1994, 1996 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 "basic-block.h"
27 #include "hard-reg-set.h"
29 #include "insn-config.h"
32 /* This pass of the compiler performs global register allocation.
33 It assigns hard register numbers to all the pseudo registers
34 that were not handled in local_alloc. Assignments are recorded
35 in the vector reg_renumber, not by changing the rtl code.
36 (Such changes are made by final). The entry point is
37 the function global_alloc.
39 After allocation is complete, the reload pass is run as a subroutine
40 of this pass, so that when a pseudo reg loses its hard reg due to
41 spilling it is possible to make a second attempt to find a hard
42 reg for it. The reload pass is independent in other respects
43 and it is run even when stupid register allocation is in use.
45 1. count the pseudo-registers still needing allocation
46 and assign allocation-numbers (allocnos) to them.
47 Set up tables reg_allocno and allocno_reg to map
48 reg numbers to allocnos and vice versa.
49 max_allocno gets the number of allocnos in use.
51 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
52 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
53 for conflicts between allocnos and explicit hard register use
54 (which includes use of pseudo-registers allocated by local_alloc).
56 3. for each basic block
57 walk forward through the block, recording which
58 unallocated registers and which hardware registers are live.
59 Build the conflict matrix between the unallocated registers
60 and another of unallocated registers versus hardware registers.
61 Also record the preferred hardware registers
62 for each unallocated one.
64 4. Sort a table of the allocnos into order of
65 desirability of the variables.
67 5. Allocate the variables in that order; each if possible into
68 a preferred register, else into another register. */
70 /* Number of pseudo-registers still requiring allocation
71 (not allocated by local_allocate). */
73 static int max_allocno
;
75 /* Indexed by (pseudo) reg number, gives the allocno, or -1
76 for pseudo registers already allocated by local_allocate. */
80 /* Indexed by allocno, gives the reg number. */
82 static int *allocno_reg
;
84 /* A vector of the integers from 0 to max_allocno-1,
85 sorted in the order of first-to-be-allocated first. */
87 static int *allocno_order
;
89 /* Indexed by an allocno, gives the number of consecutive
90 hard registers needed by that pseudo reg. */
92 static int *allocno_size
;
94 /* Indexed by (pseudo) reg number, gives the number of another
95 lower-numbered pseudo reg which can share a hard reg with this pseudo
96 *even if the two pseudos would otherwise appear to conflict*. */
98 static int *reg_may_share
;
100 /* Define the number of bits in each element of `conflicts' and what
101 type that element has. We use the largest integer format on the
104 #define INT_BITS HOST_BITS_PER_WIDE_INT
105 #define INT_TYPE HOST_WIDE_INT
107 /* max_allocno by max_allocno array of bits,
108 recording whether two allocno's conflict (can't go in the same
111 `conflicts' is not symmetric; a conflict between allocno's i and j
112 is recorded either in element i,j or in element j,i. */
114 static INT_TYPE
*conflicts
;
116 /* Number of ints require to hold max_allocno bits.
117 This is the length of a row in `conflicts'. */
119 static int allocno_row_words
;
121 /* Two macros to test or store 1 in an element of `conflicts'. */
123 #define CONFLICTP(I, J) \
124 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
125 & ((INT_TYPE) 1 << ((J) % INT_BITS)))
127 #define SET_CONFLICT(I, J) \
128 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
129 |= ((INT_TYPE) 1 << ((J) % INT_BITS)))
131 /* Set of hard regs currently live (during scan of all insns). */
133 static HARD_REG_SET hard_regs_live
;
135 /* Indexed by N, set of hard regs conflicting with allocno N. */
137 static HARD_REG_SET
*hard_reg_conflicts
;
139 /* Indexed by N, set of hard regs preferred by allocno N.
140 This is used to make allocnos go into regs that are copied to or from them,
141 when possible, to reduce register shuffling. */
143 static HARD_REG_SET
*hard_reg_preferences
;
145 /* Similar, but just counts register preferences made in simple copy
146 operations, rather than arithmetic. These are given priority because
147 we can always eliminate an insn by using these, but using a register
148 in the above list won't always eliminate an insn. */
150 static HARD_REG_SET
*hard_reg_copy_preferences
;
152 /* Similar to hard_reg_preferences, but includes bits for subsequent
153 registers when an allocno is multi-word. The above variable is used for
154 allocation while this is used to build reg_someone_prefers, below. */
156 static HARD_REG_SET
*hard_reg_full_preferences
;
158 /* Indexed by N, set of hard registers that some later allocno has a
161 static HARD_REG_SET
*regs_someone_prefers
;
163 /* Set of registers that global-alloc isn't supposed to use. */
165 static HARD_REG_SET no_global_alloc_regs
;
167 /* Set of registers used so far. */
169 static HARD_REG_SET regs_used_so_far
;
171 /* Number of calls crossed by each allocno. */
173 static int *allocno_calls_crossed
;
175 /* Number of refs (weighted) to each allocno. */
177 static int *allocno_n_refs
;
179 /* Guess at live length of each allocno.
180 This is actually the max of the live lengths of the regs. */
182 static int *allocno_live_length
;
184 /* Number of refs (weighted) to each hard reg, as used by local alloc.
185 It is zero for a reg that contains global pseudos or is explicitly used. */
187 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
189 /* Guess at live length of each hard reg, as used by local alloc.
190 This is actually the sum of the live lengths of the specific regs. */
192 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
194 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
195 for vector element I, and hard register number J. */
197 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
199 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
201 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
203 /* Bit mask for allocnos live at current point in the scan. */
205 static INT_TYPE
*allocnos_live
;
207 /* Test, set or clear bit number I in allocnos_live,
208 a bit vector indexed by allocno. */
210 #define ALLOCNO_LIVE_P(I) \
211 (allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS)))
213 #define SET_ALLOCNO_LIVE(I) \
214 (allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS)))
216 #define CLEAR_ALLOCNO_LIVE(I) \
217 (allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((I) % INT_BITS)))
219 /* This is turned off because it doesn't work right for DImode.
220 (And it is only used for DImode, so the other cases are worthless.)
221 The problem is that it isn't true that there is NO possibility of conflict;
222 only that there is no conflict if the two pseudos get the exact same regs.
223 If they were allocated with a partial overlap, there would be a conflict.
224 We can't safely turn off the conflict unless we have another way to
225 prevent the partial overlap.
227 Idea: change hard_reg_conflicts so that instead of recording which
228 hard regs the allocno may not overlap, it records where the allocno
229 may not start. Change both where it is used and where it is updated.
230 Then there is a way to record that (reg:DI 108) may start at 10
231 but not at 9 or 11. There is still the question of how to record
232 this semi-conflict between two pseudos. */
234 /* Reg pairs for which conflict after the current insn
235 is inhibited by a REG_NO_CONFLICT note.
236 If the table gets full, we ignore any other notes--that is conservative. */
237 #define NUM_NO_CONFLICT_PAIRS 4
238 /* Number of pairs in use in this insn. */
239 int n_no_conflict_pairs
;
240 static struct { int allocno1
, allocno2
;}
241 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
244 /* Record all regs that are set in any one insn.
245 Communication from mark_reg_{store,clobber} and global_conflicts. */
247 static rtx
*regs_set
;
248 static int n_regs_set
;
250 /* All registers that can be eliminated. */
252 static HARD_REG_SET eliminable_regset
;
254 static int allocno_compare
PROTO((const GENERIC_PTR
, const GENERIC_PTR
));
255 static void global_conflicts
PROTO((void));
256 static void expand_preferences
PROTO((void));
257 static void prune_preferences
PROTO((void));
258 static void find_reg
PROTO((int, HARD_REG_SET
, int, int, int));
259 static void record_one_conflict
PROTO((int));
260 static void record_conflicts
PROTO((short *, int));
261 static void mark_reg_store
PROTO((rtx
, rtx
));
262 static void mark_reg_clobber
PROTO((rtx
, rtx
));
263 static void mark_reg_conflicts
PROTO((rtx
));
264 static void mark_reg_death
PROTO((rtx
));
265 static void mark_reg_live_nc
PROTO((int, enum machine_mode
));
266 static void set_preference
PROTO((rtx
, rtx
));
267 static void dump_conflicts
PROTO((FILE *));
269 /* Perform allocation of pseudo-registers not allocated by local_alloc.
270 FILE is a file to output debugging information on,
271 or zero if such output is not desired.
273 Return value is nonzero if reload failed
274 and we must not do any more for this function. */
280 #ifdef ELIMINABLE_REGS
281 static struct {int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
284 = (! flag_omit_frame_pointer
285 #ifdef EXIT_IGNORE_STACK
286 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
288 || FRAME_POINTER_REQUIRED
);
295 /* A machine may have certain hard registers that
296 are safe to use only within a basic block. */
298 CLEAR_HARD_REG_SET (no_global_alloc_regs
);
299 #ifdef OVERLAPPING_REGNO_P
300 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
301 if (OVERLAPPING_REGNO_P (i
))
302 SET_HARD_REG_BIT (no_global_alloc_regs
, i
);
305 /* Build the regset of all eliminable registers and show we can't use those
306 that we already know won't be eliminated. */
307 #ifdef ELIMINABLE_REGS
308 for (i
= 0; i
< sizeof eliminables
/ sizeof eliminables
[0]; i
++)
310 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
312 if (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
313 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
))
314 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
316 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
317 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
319 SET_HARD_REG_BIT (no_global_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
323 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
325 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
328 /* Track which registers have already been used. Start with registers
329 explicitly in the rtl, then registers allocated by local register
332 CLEAR_HARD_REG_SET (regs_used_so_far
);
333 #ifdef LEAF_REGISTERS
334 /* If we are doing the leaf function optimization, and this is a leaf
335 function, it means that the registers that take work to save are those
336 that need a register window. So prefer the ones that can be used in
340 static char leaf_regs
[] = LEAF_REGISTERS
;
342 if (only_leaf_regs_used () && leaf_function_p ())
343 cheap_regs
= leaf_regs
;
345 cheap_regs
= call_used_regs
;
346 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
347 if (regs_ever_live
[i
] || cheap_regs
[i
])
348 SET_HARD_REG_BIT (regs_used_so_far
, i
);
351 /* We consider registers that do not have to be saved over calls as if
352 they were already used since there is no cost in using them. */
353 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
354 if (regs_ever_live
[i
] || call_used_regs
[i
])
355 SET_HARD_REG_BIT (regs_used_so_far
, i
);
358 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
359 if (reg_renumber
[i
] >= 0)
360 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
362 /* Establish mappings from register number to allocation number
363 and vice versa. In the process, count the allocnos. */
365 reg_allocno
= (int *) alloca (max_regno
* sizeof (int));
367 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
370 /* Initialize the shared-hard-reg mapping
371 from the list of pairs that may share. */
372 reg_may_share
= (int *) alloca (max_regno
* sizeof (int));
373 bzero ((char *) reg_may_share
, max_regno
* sizeof (int));
374 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
376 int r1
= REGNO (XEXP (x
, 0));
377 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
379 reg_may_share
[r1
] = r2
;
381 reg_may_share
[r2
] = r1
;
384 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
385 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
386 that we are supposed to refrain from putting in a hard reg.
387 -2 means do make an allocno but don't allocate it. */
388 if (reg_n_refs
[i
] != 0 && reg_renumber
[i
] < 0 && reg_live_length
[i
] != -1
389 /* Don't allocate pseudos that cross calls,
390 if this function receives a nonlocal goto. */
391 && (! current_function_has_nonlocal_label
392 || reg_n_calls_crossed
[i
] == 0))
394 if (reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
395 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
397 reg_allocno
[i
] = max_allocno
++;
398 if (reg_live_length
[i
] == 0)
404 allocno_reg
= (int *) alloca (max_allocno
* sizeof (int));
405 allocno_size
= (int *) alloca (max_allocno
* sizeof (int));
406 allocno_calls_crossed
= (int *) alloca (max_allocno
* sizeof (int));
407 allocno_n_refs
= (int *) alloca (max_allocno
* sizeof (int));
408 allocno_live_length
= (int *) alloca (max_allocno
* sizeof (int));
409 bzero ((char *) allocno_size
, max_allocno
* sizeof (int));
410 bzero ((char *) allocno_calls_crossed
, max_allocno
* sizeof (int));
411 bzero ((char *) allocno_n_refs
, max_allocno
* sizeof (int));
412 bzero ((char *) allocno_live_length
, max_allocno
* sizeof (int));
414 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
415 if (reg_allocno
[i
] >= 0)
417 int allocno
= reg_allocno
[i
];
418 allocno_reg
[allocno
] = i
;
419 allocno_size
[allocno
] = PSEUDO_REGNO_SIZE (i
);
420 allocno_calls_crossed
[allocno
] += reg_n_calls_crossed
[i
];
421 allocno_n_refs
[allocno
] += reg_n_refs
[i
];
422 if (allocno_live_length
[allocno
] < reg_live_length
[i
])
423 allocno_live_length
[allocno
] = reg_live_length
[i
];
426 /* Calculate amount of usage of each hard reg by pseudos
427 allocated by local-alloc. This is to see if we want to
429 bzero ((char *) local_reg_live_length
, sizeof local_reg_live_length
);
430 bzero ((char *) local_reg_n_refs
, sizeof local_reg_n_refs
);
431 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
432 if (reg_allocno
[i
] < 0 && reg_renumber
[i
] >= 0)
434 int regno
= reg_renumber
[i
];
435 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (i
));
438 for (j
= regno
; j
< endregno
; j
++)
440 local_reg_n_refs
[j
] += reg_n_refs
[i
];
441 local_reg_live_length
[j
] += reg_live_length
[i
];
445 /* We can't override local-alloc for a reg used not just by local-alloc. */
446 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
447 if (regs_ever_live
[i
])
448 local_reg_n_refs
[i
] = 0;
450 /* Likewise for regs used in a SCRATCH. */
451 for (i
= 0; i
< scratch_list_length
; i
++)
454 int regno
= REGNO (scratch_list
[i
]);
455 int lim
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (scratch_list
[i
]));
458 for (j
= regno
; j
< lim
; j
++)
459 local_reg_n_refs
[j
] = 0;
462 /* Allocate the space for the conflict and preference tables and
466 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
467 bzero ((char *) hard_reg_conflicts
, max_allocno
* sizeof (HARD_REG_SET
));
470 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
471 bzero ((char *) hard_reg_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
473 hard_reg_copy_preferences
474 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
475 bzero ((char *) hard_reg_copy_preferences
,
476 max_allocno
* sizeof (HARD_REG_SET
));
478 hard_reg_full_preferences
479 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
480 bzero ((char *) hard_reg_full_preferences
,
481 max_allocno
* sizeof (HARD_REG_SET
));
484 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
485 bzero ((char *) regs_someone_prefers
, max_allocno
* sizeof (HARD_REG_SET
));
487 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
489 conflicts
= (INT_TYPE
*) alloca (max_allocno
* allocno_row_words
490 * sizeof (INT_TYPE
));
491 bzero ((char *) conflicts
,
492 max_allocno
* allocno_row_words
* sizeof (INT_TYPE
));
494 allocnos_live
= (INT_TYPE
*) alloca (allocno_row_words
* sizeof (INT_TYPE
));
496 /* If there is work to be done (at least one reg to allocate),
497 perform global conflict analysis and allocate the regs. */
501 /* Scan all the insns and compute the conflicts among allocnos
502 and between allocnos and hard regs. */
506 /* Eliminate conflicts between pseudos and eliminable registers. If
507 the register is not eliminated, the pseudo won't really be able to
508 live in the eliminable register, so the conflict doesn't matter.
509 If we do eliminate the register, the conflict will no longer exist.
510 So in either case, we can ignore the conflict. Likewise for
513 for (i
= 0; i
< max_allocno
; i
++)
515 AND_COMPL_HARD_REG_SET (hard_reg_conflicts
[i
], eliminable_regset
);
516 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[i
],
518 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[i
], eliminable_regset
);
521 /* Try to expand the preferences by merging them between allocnos. */
523 expand_preferences ();
525 /* Determine the order to allocate the remaining pseudo registers. */
527 allocno_order
= (int *) alloca (max_allocno
* sizeof (int));
528 for (i
= 0; i
< max_allocno
; i
++)
529 allocno_order
[i
] = i
;
531 /* Default the size to 1, since allocno_compare uses it to divide by.
532 Also convert allocno_live_length of zero to -1. A length of zero
533 can occur when all the registers for that allocno have reg_live_length
534 equal to -2. In this case, we want to make an allocno, but not
535 allocate it. So avoid the divide-by-zero and set it to a low
538 for (i
= 0; i
< max_allocno
; i
++)
540 if (allocno_size
[i
] == 0)
542 if (allocno_live_length
[i
] == 0)
543 allocno_live_length
[i
] = -1;
546 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
548 prune_preferences ();
551 dump_conflicts (file
);
553 /* Try allocating them, one by one, in that order,
554 except for parameters marked with reg_live_length[regno] == -2. */
556 for (i
= 0; i
< max_allocno
; i
++)
557 if (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
], HARD_CONST (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
], HARD_CONST (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)
580 return reload (get_insns (), 1, file
);
583 /* Sort predicate for ordering the allocnos.
584 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
587 allocno_compare (v1p
, v2p
)
588 const GENERIC_PTR v1p
;
589 const GENERIC_PTR v2p
;
591 int v1
= *(int *)v1p
, v2
= *(int *)v2p
;
592 /* Note that the quotient will never be bigger than
593 the value of floor_log2 times the maximum number of
594 times a register can occur in one insn (surely less than 100).
595 Multiplying this by 10000 can't overflow. */
597 = (((double) (floor_log2 (allocno_n_refs
[v1
]) * allocno_n_refs
[v1
])
598 / allocno_live_length
[v1
])
599 * 10000 * allocno_size
[v1
]);
601 = (((double) (floor_log2 (allocno_n_refs
[v2
]) * allocno_n_refs
[v2
])
602 / allocno_live_length
[v2
])
603 * 10000 * allocno_size
[v2
]);
607 /* If regs are equally good, sort by allocno,
608 so that the results of qsort leave nothing to chance. */
612 /* Scan the rtl code and record all conflicts and register preferences in the
613 conflict matrices and preference tables. */
620 short *block_start_allocnos
;
622 /* Make a vector that mark_reg_{store,clobber} will store in. */
623 regs_set
= (rtx
*) alloca (max_parallel
* sizeof (rtx
) * 2);
625 block_start_allocnos
= (short *) alloca (max_allocno
* sizeof (short));
627 for (b
= 0; b
< n_basic_blocks
; b
++)
629 bzero ((char *) allocnos_live
, allocno_row_words
* sizeof (INT_TYPE
));
631 /* Initialize table of registers currently live
632 to the state at the beginning of this basic block.
633 This also marks the conflicts among them.
635 For pseudo-regs, there is only one bit for each one
636 no matter how many hard regs it occupies.
637 This is ok; we know the size from PSEUDO_REGNO_SIZE.
638 For explicit hard regs, we cannot know the size that way
639 since one hard reg can be used with various sizes.
640 Therefore, we must require that all the hard regs
641 implicitly live as part of a multi-word hard reg
642 are explicitly marked in basic_block_live_at_start. */
647 register regset old
= basic_block_live_at_start
[b
];
651 hard_regs_live
= old
[0];
653 COPY_HARD_REG_SET (hard_regs_live
, old
);
655 for (offset
= 0, i
= 0; offset
< regset_size
; offset
++)
656 if (old
[offset
] == 0)
657 i
+= REGSET_ELT_BITS
;
659 for (bit
= 1; bit
; bit
<<= 1, i
++)
663 if (old
[offset
] & bit
)
665 register int a
= reg_allocno
[i
];
668 SET_ALLOCNO_LIVE (a
);
669 block_start_allocnos
[ax
++] = a
;
671 else if ((a
= reg_renumber
[i
]) >= 0)
672 mark_reg_live_nc (a
, PSEUDO_REGNO_MODE (i
));
676 /* Record that each allocno now live conflicts with each other
677 allocno now live, and with each hard reg now live. */
679 record_conflicts (block_start_allocnos
, ax
);
682 insn
= basic_block_head
[b
];
684 /* Scan the code of this basic block, noting which allocnos
685 and hard regs are born or die. When one is born,
686 record a conflict with all others currently live. */
690 register RTX_CODE code
= GET_CODE (insn
);
693 /* Make regs_set an empty set. */
697 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
702 for (link
= REG_NOTES (insn
);
703 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
704 link
= XEXP (link
, 1))
705 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
707 no_conflict_pairs
[i
].allocno1
708 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
709 no_conflict_pairs
[i
].allocno2
710 = reg_allocno
[REGNO (XEXP (link
, 0))];
715 /* Mark any registers clobbered by INSN as live,
716 so they conflict with the inputs. */
718 note_stores (PATTERN (insn
), mark_reg_clobber
);
720 /* Mark any registers dead after INSN as dead now. */
722 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
723 if (REG_NOTE_KIND (link
) == REG_DEAD
)
724 mark_reg_death (XEXP (link
, 0));
726 /* Mark any registers set in INSN as live,
727 and mark them as conflicting with all other live regs.
728 Clobbers are processed again, so they conflict with
729 the registers that are set. */
731 note_stores (PATTERN (insn
), mark_reg_store
);
734 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
735 if (REG_NOTE_KIND (link
) == REG_INC
)
736 mark_reg_store (XEXP (link
, 0), NULL_RTX
);
739 /* If INSN has multiple outputs, then any reg that dies here
740 and is used inside of an output
741 must conflict with the other outputs. */
743 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& !single_set (insn
))
744 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
745 if (REG_NOTE_KIND (link
) == REG_DEAD
)
747 int used_in_output
= 0;
749 rtx reg
= XEXP (link
, 0);
751 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
753 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
754 if (GET_CODE (set
) == SET
755 && GET_CODE (SET_DEST (set
)) != REG
756 && !rtx_equal_p (reg
, SET_DEST (set
))
757 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
761 mark_reg_conflicts (reg
);
764 /* Mark any registers set in INSN and then never used. */
766 while (n_regs_set
> 0)
767 if (find_regno_note (insn
, REG_UNUSED
,
768 REGNO (regs_set
[--n_regs_set
])))
769 mark_reg_death (regs_set
[n_regs_set
]);
772 if (insn
== basic_block_end
[b
])
774 insn
= NEXT_INSN (insn
);
778 /* Expand the preference information by looking for cases where one allocno
779 dies in an insn that sets an allocno. If those two allocnos don't conflict,
780 merge any preferences between those allocnos. */
783 expand_preferences ()
789 /* We only try to handle the most common cases here. Most of the cases
790 where this wins are reg-reg copies. */
792 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
793 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
794 && (set
= single_set (insn
)) != 0
795 && GET_CODE (SET_DEST (set
)) == REG
796 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
797 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
798 if (REG_NOTE_KIND (link
) == REG_DEAD
799 && GET_CODE (XEXP (link
, 0)) == REG
800 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
801 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
802 reg_allocno
[REGNO (XEXP (link
, 0))])
803 && ! CONFLICTP (reg_allocno
[REGNO (XEXP (link
, 0))],
804 reg_allocno
[REGNO (SET_DEST (set
))]))
806 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
807 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
809 if (XEXP (link
, 0) == SET_SRC (set
))
811 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a1
],
812 hard_reg_copy_preferences
[a2
]);
813 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a2
],
814 hard_reg_copy_preferences
[a1
]);
817 IOR_HARD_REG_SET (hard_reg_preferences
[a1
],
818 hard_reg_preferences
[a2
]);
819 IOR_HARD_REG_SET (hard_reg_preferences
[a2
],
820 hard_reg_preferences
[a1
]);
821 IOR_HARD_REG_SET (hard_reg_full_preferences
[a1
],
822 hard_reg_full_preferences
[a2
]);
823 IOR_HARD_REG_SET (hard_reg_full_preferences
[a2
],
824 hard_reg_full_preferences
[a1
]);
828 /* Prune the preferences for global registers to exclude registers that cannot
831 Compute `regs_someone_prefers', which is a bitmask of the hard registers
832 that are preferred by conflicting registers of lower priority. If possible,
833 we will avoid using these registers. */
841 /* Scan least most important to most important.
842 For each allocno, remove from preferences registers that cannot be used,
843 either because of conflicts or register type. Then compute all registers
844 preferred by each lower-priority register that conflicts. */
846 for (i
= max_allocno
- 1; i
>= 0; i
--)
850 allocno
= allocno_order
[i
];
851 COPY_HARD_REG_SET (temp
, hard_reg_conflicts
[allocno
]);
853 if (allocno_calls_crossed
[allocno
] == 0)
854 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
856 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
858 IOR_COMPL_HARD_REG_SET
860 reg_class_contents
[(int) reg_preferred_class (allocno_reg
[allocno
])]);
862 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], temp
);
863 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], temp
);
864 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences
[allocno
], temp
);
866 CLEAR_HARD_REG_SET (regs_someone_prefers
[allocno
]);
868 /* Merge in the preferences of lower-priority registers (they have
869 already been pruned). If we also prefer some of those registers,
870 don't exclude them unless we are of a smaller size (in which case
871 we want to give the lower-priority allocno the first chance for
873 for (j
= i
+ 1; j
< max_allocno
; j
++)
874 if (CONFLICTP (allocno
, allocno_order
[j
]))
876 COPY_HARD_REG_SET (temp
,
877 hard_reg_full_preferences
[allocno_order
[j
]]);
878 if (allocno_size
[allocno_order
[j
]] <= allocno_size
[allocno
])
879 AND_COMPL_HARD_REG_SET (temp
,
880 hard_reg_full_preferences
[allocno
]);
882 IOR_HARD_REG_SET (regs_someone_prefers
[allocno
], temp
);
887 /* Assign a hard register to ALLOCNO; look for one that is the beginning
888 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
889 The registers marked in PREFREGS are tried first.
891 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
892 be used for this allocation.
894 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
895 Otherwise ignore that preferred class and use the alternate class.
897 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
898 will have to be saved and restored at calls.
900 RETRYING is nonzero if this is called from retry_global_alloc.
902 If we find one, record it in reg_renumber.
903 If not, do nothing. */
906 find_reg (allocno
, losers
, alt_regs_p
, accept_call_clobbered
, retrying
)
910 int accept_call_clobbered
;
913 register int i
, best_reg
, pass
;
915 register /* Declare it register if it's a scalar. */
917 HARD_REG_SET used
, used1
, used2
;
919 enum reg_class
class = (alt_regs_p
920 ? reg_alternate_class (allocno_reg
[allocno
])
921 : reg_preferred_class (allocno_reg
[allocno
]));
922 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno_reg
[allocno
]);
924 if (accept_call_clobbered
)
925 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
926 else if (allocno_calls_crossed
[allocno
] == 0)
927 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
929 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
931 /* Some registers should not be allocated in global-alloc. */
932 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
934 IOR_HARD_REG_SET (used1
, losers
);
936 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
937 COPY_HARD_REG_SET (used2
, used1
);
939 IOR_HARD_REG_SET (used1
, hard_reg_conflicts
[allocno
]);
941 #ifdef CLASS_CANNOT_CHANGE_SIZE
942 if (reg_changes_size
[allocno_reg
[allocno
]])
943 IOR_HARD_REG_SET (used1
,
944 reg_class_contents
[(int) CLASS_CANNOT_CHANGE_SIZE
]);
947 /* Try each hard reg to see if it fits. Do this in two passes.
948 In the first pass, skip registers that are preferred by some other pseudo
949 to give it a better chance of getting one of those registers. Only if
950 we can't get a register when excluding those do we take one of them.
951 However, we never allocate a register for the first time in pass 0. */
953 COPY_HARD_REG_SET (used
, used1
);
954 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
955 IOR_HARD_REG_SET (used
, regs_someone_prefers
[allocno
]);
958 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
959 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
963 COPY_HARD_REG_SET (used
, used1
);
964 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
966 #ifdef REG_ALLOC_ORDER
967 int regno
= reg_alloc_order
[i
];
971 if (! TEST_HARD_REG_BIT (used
, regno
)
972 && HARD_REGNO_MODE_OK (regno
, mode
))
975 register int lim
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
978 && ! TEST_HARD_REG_BIT (used
, j
));
985 #ifndef REG_ALLOC_ORDER
986 i
= j
; /* Skip starting points we know will lose */
992 /* See if there is a preferred register with the same class as the register
993 we allocated above. Making this restriction prevents register
994 preferencing from creating worse register allocation.
996 Remove from the preferred registers and conflicting registers. Note that
997 additional conflicts may have been added after `prune_preferences' was
1000 First do this for those register with copy preferences, then all
1001 preferred registers. */
1003 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], used
);
1004 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences
[allocno
],
1005 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
1009 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1010 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences
[allocno
], i
)
1011 && HARD_REGNO_MODE_OK (i
, mode
)
1012 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1013 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1014 REGNO_REG_CLASS (best_reg
))
1015 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1016 REGNO_REG_CLASS (i
))))
1019 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1022 && ! TEST_HARD_REG_BIT (used
, j
)
1023 && (REGNO_REG_CLASS (j
)
1024 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1025 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1026 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1027 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1028 REGNO_REG_CLASS (j
))));
1039 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], used
);
1040 GO_IF_HARD_REG_SUBSET (hard_reg_preferences
[allocno
],
1041 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1045 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1046 if (TEST_HARD_REG_BIT (hard_reg_preferences
[allocno
], i
)
1047 && HARD_REGNO_MODE_OK (i
, mode
)
1048 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1049 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1050 REGNO_REG_CLASS (best_reg
))
1051 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1052 REGNO_REG_CLASS (i
))))
1055 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1058 && ! TEST_HARD_REG_BIT (used
, j
)
1059 && (REGNO_REG_CLASS (j
)
1060 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1061 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1062 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1063 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1064 REGNO_REG_CLASS (j
))));
1075 /* If we haven't succeeded yet, try with caller-saves.
1076 We need not check to see if the current function has nonlocal
1077 labels because we don't put any pseudos that are live over calls in
1078 registers in that case. */
1080 if (flag_caller_saves
&& best_reg
< 0)
1082 /* Did not find a register. If it would be profitable to
1083 allocate a call-clobbered register and save and restore it
1084 around calls, do that. */
1085 if (! accept_call_clobbered
1086 && allocno_calls_crossed
[allocno
] != 0
1087 && CALLER_SAVE_PROFITABLE (allocno_n_refs
[allocno
],
1088 allocno_calls_crossed
[allocno
]))
1090 HARD_REG_SET new_losers
;
1092 CLEAR_HARD_REG_SET (new_losers
);
1094 COPY_HARD_REG_SET (new_losers
, losers
);
1096 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1097 find_reg (allocno
, new_losers
, alt_regs_p
, 1, retrying
);
1098 if (reg_renumber
[allocno_reg
[allocno
]] >= 0)
1100 caller_save_needed
= 1;
1106 /* If we haven't succeeded yet,
1107 see if some hard reg that conflicts with us
1108 was utilized poorly by local-alloc.
1109 If so, kick out the regs that were put there by local-alloc
1110 so we can use it instead. */
1111 if (best_reg
< 0 && !retrying
1112 /* Let's not bother with multi-reg allocnos. */
1113 && allocno_size
[allocno
] == 1)
1115 /* Count from the end, to find the least-used ones first. */
1116 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1118 #ifdef REG_ALLOC_ORDER
1119 int regno
= reg_alloc_order
[i
];
1124 if (local_reg_n_refs
[regno
] != 0
1125 /* Don't use a reg no good for this pseudo. */
1126 && ! TEST_HARD_REG_BIT (used2
, regno
)
1127 && HARD_REGNO_MODE_OK (regno
, mode
)
1128 #ifdef CLASS_CANNOT_CHANGE_SIZE
1129 && ! (reg_changes_size
[allocno_reg
[allocno
]]
1130 && (TEST_HARD_REG_BIT
1131 (reg_class_contents
[(int) CLASS_CANNOT_CHANGE_SIZE
],
1136 /* We explicitly evaluate the divide results into temporary
1137 variables so as to avoid excess precision problems that occur
1138 on a i386-unknown-sysv4.2 (unixware) host. */
1140 double tmp1
= ((double) local_reg_n_refs
[regno
]
1141 / local_reg_live_length
[regno
]);
1142 double tmp2
= ((double) allocno_n_refs
[allocno
]
1143 / allocno_live_length
[allocno
]);
1147 /* Hard reg REGNO was used less in total by local regs
1148 than it would be used by this one allocno! */
1150 for (k
= 0; k
< max_regno
; k
++)
1151 if (reg_renumber
[k
] >= 0)
1153 int r
= reg_renumber
[k
];
1155 = r
+ HARD_REGNO_NREGS (r
, PSEUDO_REGNO_MODE (k
));
1157 if (regno
>= r
&& regno
< endregno
)
1158 reg_renumber
[k
] = -1;
1168 /* Did we find a register? */
1172 register int lim
, j
;
1173 HARD_REG_SET this_reg
;
1175 /* Yes. Record it as the hard register of this pseudo-reg. */
1176 reg_renumber
[allocno_reg
[allocno
]] = best_reg
;
1177 /* Also of any pseudo-regs that share with it. */
1178 if (reg_may_share
[allocno_reg
[allocno
]])
1179 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1180 if (reg_allocno
[j
] == allocno
)
1181 reg_renumber
[j
] = best_reg
;
1183 /* Make a set of the hard regs being allocated. */
1184 CLEAR_HARD_REG_SET (this_reg
);
1185 lim
= best_reg
+ HARD_REGNO_NREGS (best_reg
, mode
);
1186 for (j
= best_reg
; j
< lim
; j
++)
1188 SET_HARD_REG_BIT (this_reg
, j
);
1189 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1190 /* This is no longer a reg used just by local regs. */
1191 local_reg_n_refs
[j
] = 0;
1193 /* For each other pseudo-reg conflicting with this one,
1194 mark it as conflicting with the hard regs this one occupies. */
1196 for (j
= 0; j
< max_allocno
; j
++)
1197 if (CONFLICTP (lim
, j
) || CONFLICTP (j
, lim
))
1199 IOR_HARD_REG_SET (hard_reg_conflicts
[j
], this_reg
);
1204 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1205 Perhaps it had previously seemed not worth a hard reg,
1206 or perhaps its old hard reg has been commandeered for reloads.
1207 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1208 they do not appear to be allocated.
1209 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1212 retry_global_alloc (regno
, forbidden_regs
)
1214 HARD_REG_SET forbidden_regs
;
1216 int allocno
= reg_allocno
[regno
];
1219 /* If we have more than one register class,
1220 first try allocating in the class that is cheapest
1221 for this pseudo-reg. If that fails, try any reg. */
1222 if (N_REG_CLASSES
> 1)
1223 find_reg (allocno
, forbidden_regs
, 0, 0, 1);
1224 if (reg_renumber
[regno
] < 0
1225 && reg_alternate_class (regno
) != NO_REGS
)
1226 find_reg (allocno
, forbidden_regs
, 1, 0, 1);
1228 /* If we found a register, modify the RTL for the register to
1229 show the hard register, and mark that register live. */
1230 if (reg_renumber
[regno
] >= 0)
1232 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1233 mark_home_live (regno
);
1238 /* Record a conflict between register REGNO
1239 and everything currently live.
1240 REGNO must not be a pseudo reg that was allocated
1241 by local_alloc; such numbers must be translated through
1242 reg_renumber before calling here. */
1245 record_one_conflict (regno
)
1250 if (regno
< FIRST_PSEUDO_REGISTER
)
1251 /* When a hard register becomes live,
1252 record conflicts with live pseudo regs. */
1253 for (j
= 0; j
< max_allocno
; j
++)
1255 if (ALLOCNO_LIVE_P (j
))
1256 SET_HARD_REG_BIT (hard_reg_conflicts
[j
], regno
);
1259 /* When a pseudo-register becomes live,
1260 record conflicts first with hard regs,
1261 then with other pseudo regs. */
1263 register int ialloc
= reg_allocno
[regno
];
1264 register int ialloc_prod
= ialloc
* allocno_row_words
;
1265 IOR_HARD_REG_SET (hard_reg_conflicts
[ialloc
], hard_regs_live
);
1266 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1270 for (k
= 0; k
< n_no_conflict_pairs
; k
++)
1271 if (! ((j
== no_conflict_pairs
[k
].allocno1
1272 && ialloc
== no_conflict_pairs
[k
].allocno2
)
1274 (j
== no_conflict_pairs
[k
].allocno2
1275 && ialloc
== no_conflict_pairs
[k
].allocno1
)))
1277 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1282 /* Record all allocnos currently live as conflicting
1283 with each other and with all hard regs currently live.
1284 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1285 are currently live. Their bits are also flagged in allocnos_live. */
1288 record_conflicts (allocno_vec
, len
)
1289 register short *allocno_vec
;
1292 register int allocno
;
1294 register int ialloc_prod
;
1298 allocno
= allocno_vec
[len
];
1299 ialloc_prod
= allocno
* allocno_row_words
;
1300 IOR_HARD_REG_SET (hard_reg_conflicts
[allocno
], hard_regs_live
);
1301 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1302 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1306 /* Handle the case where REG is set by the insn being scanned,
1307 during the forward scan to accumulate conflicts.
1308 Store a 1 in regs_live or allocnos_live for this register, record how many
1309 consecutive hardware registers it actually needs,
1310 and record a conflict with all other registers already live.
1312 Note that even if REG does not remain alive after this insn,
1313 we must mark it here as live, to ensure a conflict between
1314 REG and any other regs set in this insn that really do live.
1315 This is because those other regs could be considered after this.
1317 REG might actually be something other than a register;
1318 if so, we do nothing.
1320 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1321 a REG_INC note was found for it).
1323 CLOBBERs are processed here by calling mark_reg_clobber. */
1326 mark_reg_store (orig_reg
, setter
)
1327 rtx orig_reg
, setter
;
1330 register rtx reg
= orig_reg
;
1332 /* WORD is which word of a multi-register group is being stored.
1333 For the case where the store is actually into a SUBREG of REG.
1334 Except we don't use it; I believe the entire REG needs to be
1338 if (GET_CODE (reg
) == SUBREG
)
1340 word
= SUBREG_WORD (reg
);
1341 reg
= SUBREG_REG (reg
);
1344 if (GET_CODE (reg
) != REG
)
1347 if (setter
&& GET_CODE (setter
) == CLOBBER
)
1349 /* A clobber of a register should be processed here too. */
1350 mark_reg_clobber (orig_reg
, setter
);
1354 regs_set
[n_regs_set
++] = reg
;
1357 set_preference (reg
, SET_SRC (setter
));
1359 regno
= REGNO (reg
);
1361 if (reg_renumber
[regno
] >= 0)
1362 regno
= reg_renumber
[regno
] /* + word */;
1364 /* Either this is one of the max_allocno pseudo regs not allocated,
1365 or it is or has a hardware reg. First handle the pseudo-regs. */
1366 if (regno
>= FIRST_PSEUDO_REGISTER
)
1368 if (reg_allocno
[regno
] >= 0)
1370 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1371 record_one_conflict (regno
);
1374 /* Handle hardware regs (and pseudos allocated to hard regs). */
1375 else if (! fixed_regs
[regno
])
1377 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1378 while (regno
< last
)
1380 record_one_conflict (regno
);
1381 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1387 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1390 mark_reg_clobber (reg
, setter
)
1395 /* WORD is which word of a multi-register group is being stored.
1396 For the case where the store is actually into a SUBREG of REG.
1397 Except we don't use it; I believe the entire REG needs to be
1401 if (GET_CODE (setter
) != CLOBBER
)
1404 if (GET_CODE (reg
) == SUBREG
)
1406 word
= SUBREG_WORD (reg
);
1407 reg
= SUBREG_REG (reg
);
1410 if (GET_CODE (reg
) != REG
)
1413 regs_set
[n_regs_set
++] = reg
;
1415 regno
= REGNO (reg
);
1417 if (reg_renumber
[regno
] >= 0)
1418 regno
= reg_renumber
[regno
] /* + word */;
1420 /* Either this is one of the max_allocno pseudo regs not allocated,
1421 or it is or has a hardware reg. First handle the pseudo-regs. */
1422 if (regno
>= FIRST_PSEUDO_REGISTER
)
1424 if (reg_allocno
[regno
] >= 0)
1426 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1427 record_one_conflict (regno
);
1430 /* Handle hardware regs (and pseudos allocated to hard regs). */
1431 else if (! fixed_regs
[regno
])
1433 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1434 while (regno
< last
)
1436 record_one_conflict (regno
);
1437 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1443 /* Record that REG has conflicts with all the regs currently live.
1444 Do not mark REG itself as live. */
1447 mark_reg_conflicts (reg
)
1452 if (GET_CODE (reg
) == SUBREG
)
1453 reg
= SUBREG_REG (reg
);
1455 if (GET_CODE (reg
) != REG
)
1458 regno
= REGNO (reg
);
1460 if (reg_renumber
[regno
] >= 0)
1461 regno
= reg_renumber
[regno
];
1463 /* Either this is one of the max_allocno pseudo regs not allocated,
1464 or it is or has a hardware reg. First handle the pseudo-regs. */
1465 if (regno
>= FIRST_PSEUDO_REGISTER
)
1467 if (reg_allocno
[regno
] >= 0)
1468 record_one_conflict (regno
);
1470 /* Handle hardware regs (and pseudos allocated to hard regs). */
1471 else if (! fixed_regs
[regno
])
1473 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1474 while (regno
< last
)
1476 record_one_conflict (regno
);
1482 /* Mark REG as being dead (following the insn being scanned now).
1483 Store a 0 in regs_live or allocnos_live for this register. */
1486 mark_reg_death (reg
)
1489 register int regno
= REGNO (reg
);
1491 /* For pseudo reg, see if it has been assigned a hardware reg. */
1492 if (reg_renumber
[regno
] >= 0)
1493 regno
= reg_renumber
[regno
];
1495 /* Either this is one of the max_allocno pseudo regs not allocated,
1496 or it is a hardware reg. First handle the pseudo-regs. */
1497 if (regno
>= FIRST_PSEUDO_REGISTER
)
1499 if (reg_allocno
[regno
] >= 0)
1500 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1502 /* Handle hardware regs (and pseudos allocated to hard regs). */
1503 else if (! fixed_regs
[regno
])
1505 /* Pseudo regs already assigned hardware regs are treated
1506 almost the same as explicit hardware regs. */
1507 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1508 while (regno
< last
)
1510 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1516 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1517 for the value stored in it. MODE determines how many consecutive
1518 registers are actually in use. Do not record conflicts;
1519 it is assumed that the caller will do that. */
1522 mark_reg_live_nc (regno
, mode
)
1524 enum machine_mode mode
;
1526 register int last
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1527 while (regno
< last
)
1529 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1534 /* Try to set a preference for an allocno to a hard register.
1535 We are passed DEST and SRC which are the operands of a SET. It is known
1536 that SRC is a register. If SRC or the first operand of SRC is a register,
1537 try to set a preference. If one of the two is a hard register and the other
1538 is a pseudo-register, mark the preference.
1540 Note that we are not as aggressive as local-alloc in trying to tie a
1541 pseudo-register to a hard register. */
1544 set_preference (dest
, src
)
1547 int src_regno
, dest_regno
;
1548 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1549 to compensate for subregs in SRC or DEST. */
1554 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1555 src
= XEXP (src
, 0), copy
= 0;
1557 /* Get the reg number for both SRC and DEST.
1558 If neither is a reg, give up. */
1560 if (GET_CODE (src
) == REG
)
1561 src_regno
= REGNO (src
);
1562 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1564 src_regno
= REGNO (SUBREG_REG (src
));
1565 offset
+= SUBREG_WORD (src
);
1570 if (GET_CODE (dest
) == REG
)
1571 dest_regno
= REGNO (dest
);
1572 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1574 dest_regno
= REGNO (SUBREG_REG (dest
));
1575 offset
-= SUBREG_WORD (dest
);
1580 /* Convert either or both to hard reg numbers. */
1582 if (reg_renumber
[src_regno
] >= 0)
1583 src_regno
= reg_renumber
[src_regno
];
1585 if (reg_renumber
[dest_regno
] >= 0)
1586 dest_regno
= reg_renumber
[dest_regno
];
1588 /* Now if one is a hard reg and the other is a global pseudo
1589 then give the other a preference. */
1591 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1592 && reg_allocno
[src_regno
] >= 0)
1594 dest_regno
-= offset
;
1595 if (dest_regno
>= 0 && dest_regno
< FIRST_PSEUDO_REGISTER
)
1598 SET_REGBIT (hard_reg_copy_preferences
,
1599 reg_allocno
[src_regno
], dest_regno
);
1601 SET_REGBIT (hard_reg_preferences
,
1602 reg_allocno
[src_regno
], dest_regno
);
1603 for (i
= dest_regno
;
1604 i
< dest_regno
+ HARD_REGNO_NREGS (dest_regno
, GET_MODE (dest
));
1606 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1610 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1611 && reg_allocno
[dest_regno
] >= 0)
1613 src_regno
+= offset
;
1614 if (src_regno
>= 0 && src_regno
< FIRST_PSEUDO_REGISTER
)
1617 SET_REGBIT (hard_reg_copy_preferences
,
1618 reg_allocno
[dest_regno
], src_regno
);
1620 SET_REGBIT (hard_reg_preferences
,
1621 reg_allocno
[dest_regno
], src_regno
);
1623 i
< src_regno
+ HARD_REGNO_NREGS (src_regno
, GET_MODE (src
));
1625 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1630 /* Indicate that hard register number FROM was eliminated and replaced with
1631 an offset from hard register number TO. The status of hard registers live
1632 at the start of a basic block is updated by replacing a use of FROM with
1636 mark_elimination (from
, to
)
1641 for (i
= 0; i
< n_basic_blocks
; i
++)
1642 if ((basic_block_live_at_start
[i
][from
/ REGSET_ELT_BITS
]
1643 & ((REGSET_ELT_TYPE
) 1 << (from
% REGSET_ELT_BITS
))) != 0)
1645 basic_block_live_at_start
[i
][from
/ REGSET_ELT_BITS
]
1646 &= ~ ((REGSET_ELT_TYPE
) 1 << (from
% REGSET_ELT_BITS
));
1647 basic_block_live_at_start
[i
][to
/ REGSET_ELT_BITS
]
1648 |= ((REGSET_ELT_TYPE
) 1 << (to
% REGSET_ELT_BITS
));
1652 /* Print debugging trace information if -greg switch is given,
1653 showing the information on which the allocation decisions are based. */
1656 dump_conflicts (file
)
1660 register int has_preferences
;
1661 fprintf (file
, ";; %d regs to allocate:", max_allocno
);
1662 for (i
= 0; i
< max_allocno
; i
++)
1665 fprintf (file
, " %d", allocno_reg
[allocno_order
[i
]]);
1666 for (j
= 0; j
< max_regno
; j
++)
1667 if (reg_allocno
[j
] == allocno_order
[i
]
1668 && j
!= allocno_reg
[allocno_order
[i
]])
1669 fprintf (file
, "+%d", j
);
1670 if (allocno_size
[allocno_order
[i
]] != 1)
1671 fprintf (file
, " (%d)", allocno_size
[allocno_order
[i
]]);
1673 fprintf (file
, "\n");
1675 for (i
= 0; i
< max_allocno
; i
++)
1678 fprintf (file
, ";; %d conflicts:", allocno_reg
[i
]);
1679 for (j
= 0; j
< max_allocno
; j
++)
1680 if (CONFLICTP (i
, j
) || CONFLICTP (j
, i
))
1681 fprintf (file
, " %d", allocno_reg
[j
]);
1682 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1683 if (TEST_HARD_REG_BIT (hard_reg_conflicts
[i
], j
))
1684 fprintf (file
, " %d", j
);
1685 fprintf (file
, "\n");
1687 has_preferences
= 0;
1688 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1689 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1690 has_preferences
= 1;
1692 if (! has_preferences
)
1694 fprintf (file
, ";; %d preferences:", allocno_reg
[i
]);
1695 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1696 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1697 fprintf (file
, " %d", j
);
1698 fprintf (file
, "\n");
1700 fprintf (file
, "\n");
1704 dump_global_regs (file
)
1709 fprintf (file
, ";; Register dispositions:\n");
1710 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1711 if (reg_renumber
[i
] >= 0)
1713 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1715 fprintf (file
, "\n");
1718 fprintf (file
, "\n\n;; Hard regs used: ");
1719 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1720 if (regs_ever_live
[i
])
1721 fprintf (file
, " %d", i
);
1722 fprintf (file
, "\n\n");