1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 1988, 1991 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, 675 Mass Ave, Cambridge, MA 02139, USA. */
25 #include "basic-block.h"
26 #include "hard-reg-set.h"
28 #include "insn-config.h"
31 /* This pass of the compiler performs global register allocation.
32 It assigns hard register numbers to all the pseudo registers
33 that were not handled in local_alloc. Assignments are recorded
34 in the vector reg_renumber, not by changing the rtl code.
35 (Such changes are made by final). The entry point is
36 the function global_alloc.
38 After allocation is complete, the reload pass is run as a subroutine
39 of this pass, so that when a pseudo reg loses its hard reg due to
40 spilling it is possible to make a second attempt to find a hard
41 reg for it. The reload pass is independent in other respects
42 and it is run even when stupid register allocation is in use.
44 1. count the pseudo-registers still needing allocation
45 and assign allocation-numbers (allocnos) to them.
46 Set up tables reg_allocno and allocno_reg to map
47 reg numbers to allocnos and vice versa.
48 max_allocno gets the number of allocnos in use.
50 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
51 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
52 for conflicts between allocnos and explicit hard register use
53 (which includes use of pseudo-registers allocated by local_alloc).
55 3. for each basic block
56 walk forward through the block, recording which
57 unallocated registers and which hardware registers are live.
58 Build the conflict matrix between the unallocated registers
59 and another of unallocated registers versus hardware registers.
60 Also record the preferred hardware registers
61 for each unallocated one.
63 4. Sort a table of the allocnos into order of
64 desirability of the variables.
66 5. Allocate the variables in that order; each if possible into
67 a preferred register, else into another register. */
69 /* Number of pseudo-registers still requiring allocation
70 (not allocated by local_allocate). */
72 static int max_allocno
;
74 /* Indexed by (pseudo) reg number, gives the allocno, or -1
75 for pseudo registers already allocated by local_allocate. */
77 static int *reg_allocno
;
79 /* Indexed by allocno, gives the reg number. */
81 static int *allocno_reg
;
83 /* A vector of the integers from 0 to max_allocno-1,
84 sorted in the order of first-to-be-allocated first. */
86 static int *allocno_order
;
88 /* Indexed by an allocno, gives the number of consecutive
89 hard registers needed by that pseudo reg. */
91 static int *allocno_size
;
93 /* Indexed by (pseudo) reg number, gives the number of another
94 lower-numbered pseudo reg which can share a hard reg with this pseudo
95 *even if the two pseudos would otherwise appear to conflict*. */
97 static int *reg_may_share
;
99 /* max_allocno by max_allocno array of bits,
100 recording whether two allocno's conflict (can't go in the same
103 `conflicts' is not symmetric; a conflict between allocno's i and j
104 is recorded either in element i,j or in element j,i. */
106 static int *conflicts
;
108 /* Number of ints require to hold max_allocno bits.
109 This is the length of a row in `conflicts'. */
111 static int allocno_row_words
;
113 /* Two macros to test or store 1 in an element of `conflicts'. */
115 #define CONFLICTP(I, J) \
116 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
117 & (1 << ((J) % INT_BITS)))
119 #define SET_CONFLICT(I, J) \
120 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
121 |= (1 << ((J) % INT_BITS)))
123 /* Set of hard regs currently live (during scan of all insns). */
125 static HARD_REG_SET hard_regs_live
;
127 /* Indexed by N, set of hard regs conflicting with allocno N. */
129 static HARD_REG_SET
*hard_reg_conflicts
;
131 /* Indexed by N, set of hard regs preferred by allocno N.
132 This is used to make allocnos go into regs that are copied to or from them,
133 when possible, to reduce register shuffling. */
135 static HARD_REG_SET
*hard_reg_preferences
;
137 /* Similar, but just counts register preferences made in simple copy
138 operations, rather than arithmetic. These are given priority because
139 we can always eliminate an insn by using these, but using a register
140 in the above list won't always eliminate an insn. */
142 static HARD_REG_SET
*hard_reg_copy_preferences
;
144 /* Similar to hard_reg_preferences, but includes bits for subsequent
145 registers when an allocno is multi-word. The above variable is used for
146 allocation while this is used to build reg_someone_prefers, below. */
148 static HARD_REG_SET
*hard_reg_full_preferences
;
150 /* Indexed by N, set of hard registers that some later allocno has a
153 static HARD_REG_SET
*regs_someone_prefers
;
155 /* Set of registers that global-alloc isn't supposed to use. */
157 static HARD_REG_SET no_global_alloc_regs
;
159 /* Set of registers used so far. */
161 static HARD_REG_SET regs_used_so_far
;
163 /* Number of calls crossed by each allocno. */
165 static int *allocno_calls_crossed
;
167 /* Number of refs (weighted) to each allocno. */
169 static int *allocno_n_refs
;
171 /* Guess at live length of each allocno.
172 This is actually the max of the live lengths of the regs. */
174 static int *allocno_live_length
;
176 /* Number of refs (weighted) to each hard reg, as used by local alloc.
177 It is zero for a reg that contains global pseudos or is explicitly used. */
179 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
181 /* Guess at live length of each hard reg, as used by local alloc.
182 This is actually the sum of the live lengths of the specific regs. */
184 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
186 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
187 for vector element I, and hard register number J. */
189 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
191 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
193 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
195 /* Bit mask for allocnos live at current point in the scan. */
197 static int *allocnos_live
;
199 #define INT_BITS HOST_BITS_PER_INT
201 /* Test, set or clear bit number I in allocnos_live,
202 a bit vector indexed by allocno. */
204 #define ALLOCNO_LIVE_P(I) \
205 (allocnos_live[(I) / INT_BITS] & (1 << ((I) % INT_BITS)))
207 #define SET_ALLOCNO_LIVE(I) \
208 (allocnos_live[(I) / INT_BITS] |= (1 << ((I) % INT_BITS)))
210 #define CLEAR_ALLOCNO_LIVE(I) \
211 (allocnos_live[(I) / INT_BITS] &= ~(1 << ((I) % INT_BITS)))
213 /* This is turned off because it doesn't work right for DImode.
214 (And it is only used for DImode, so the other cases are worthless.)
215 The problem is that it isn't true that there is NO possibility of conflict;
216 only that there is no conflict if the two pseudos get the exact same regs.
217 If they were allocated with a partial overlap, there would be a conflict.
218 We can't safely turn off the conflict unless we have another way to
219 prevent the partial overlap.
221 Idea: change hard_reg_conflicts so that instead of recording which
222 hard regs the allocno may not overlap, it records where the allocno
223 may not start. Change both where it is used and where it is updated.
224 Then there is a way to record that (reg:DI 108) may start at 10
225 but not at 9 or 11. There is still the question of how to record
226 this semi-conflict between two pseudos. */
228 /* Reg pairs for which conflict after the current insn
229 is inhibited by a REG_NO_CONFLICT note.
230 If the table gets full, we ignore any other notes--that is conservative. */
231 #define NUM_NO_CONFLICT_PAIRS 4
232 /* Number of pairs in use in this insn. */
233 int n_no_conflict_pairs
;
234 static struct { int allocno1
, allocno2
;}
235 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
238 /* Record all regs that are set in any one insn.
239 Communication from mark_reg_{store,clobber} and global_conflicts. */
241 static rtx
*regs_set
;
242 static int n_regs_set
;
244 /* All register that can be eliminated. */
246 static HARD_REG_SET eliminable_regset
;
248 static int allocno_compare ();
249 static void mark_reg_store ();
250 static void mark_reg_clobber ();
251 static void mark_reg_conflicts ();
252 static void mark_reg_live_nc ();
253 static void mark_reg_death ();
254 static void dump_conflicts ();
255 void dump_global_regs ();
256 static void find_reg ();
257 static void global_conflicts ();
258 static void expand_preferences ();
259 static void prune_preferences ();
260 static void record_conflicts ();
261 static void set_preference ();
263 /* Perform allocation of pseudo-registers not allocated by local_alloc.
264 FILE is a file to output debugging information on,
265 or zero if such output is not desired. */
271 #ifdef ELIMINABLE_REGS
272 static struct {int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
279 /* A machine may have certain hard registers that
280 are safe to use only within a basic block. */
282 CLEAR_HARD_REG_SET (no_global_alloc_regs
);
283 #ifdef OVERLAPPING_REGNO_P
284 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
285 if (OVERLAPPING_REGNO_P (i
))
286 SET_HARD_REG_BIT (no_global_alloc_regs
, i
);
289 /* Build the regset of all eliminable registers and show we can't use those
290 that we already know won't be eliminated. */
291 #ifdef ELIMINABLE_REGS
292 for (i
= 0; i
< sizeof eliminables
/ sizeof eliminables
[0]; i
++)
294 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
296 if (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
297 || (eliminables
[i
].from
== FRAME_POINTER_REGNUM
298 && (! flag_omit_frame_pointer
|| FRAME_POINTER_REQUIRED
)))
299 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
302 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
304 /* If we know we will definitely not be eliminating the frame pointer,
305 don't allocate it. */
306 if (! flag_omit_frame_pointer
|| FRAME_POINTER_REQUIRED
)
307 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
310 /* Track which registers have already been used. Start with registers
311 explicitly in the rtl, then registers allocated by local register
314 CLEAR_HARD_REG_SET (regs_used_so_far
);
315 #ifdef LEAF_REGISTERS
316 /* If we are doing the leaf function optimization, and this is a leaf
317 function, it means that the registers that take work to save are those
318 that need a register window. So prefer the ones that can be used in
322 static char leaf_regs
[] = LEAF_REGISTERS
;
324 if (only_leaf_regs_used () && leaf_function_p ())
325 cheap_regs
= leaf_regs
;
327 cheap_regs
= call_used_regs
;
328 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
329 if (regs_ever_live
[i
] || cheap_regs
[i
])
330 SET_HARD_REG_BIT (regs_used_so_far
, i
);
333 /* We consider registers that do not have to be saved over calls as if
334 they were already used since there is no cost in using them. */
335 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
336 if (regs_ever_live
[i
] || call_used_regs
[i
])
337 SET_HARD_REG_BIT (regs_used_so_far
, i
);
340 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
341 if (reg_renumber
[i
] >= 0)
342 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
344 /* Establish mappings from register number to allocation number
345 and vice versa. In the process, count the allocnos. */
347 reg_allocno
= (int *) alloca (max_regno
* sizeof (int));
349 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
352 /* Initialize the shared-hard-reg mapping
353 from the list of pairs that may share. */
354 reg_may_share
= (int *) alloca (max_regno
* sizeof (int));
355 bzero (reg_may_share
, max_regno
* sizeof (int));
356 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
358 int r1
= REGNO (XEXP (x
, 0));
359 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
361 reg_may_share
[r1
] = r2
;
363 reg_may_share
[r2
] = r1
;
366 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
367 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
368 that we are supposed to refrain from putting in a hard reg.
369 -2 means do make an allocno but don't allocate it. */
370 if (reg_n_refs
[i
] != 0 && reg_renumber
[i
] < 0 && reg_live_length
[i
] != -1
371 /* Don't allocate pseudos that cross calls,
372 if this function receives a nonlocal goto. */
373 && (! current_function_has_nonlocal_label
374 || reg_n_calls_crossed
[i
] == 0))
376 if (reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
377 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
379 reg_allocno
[i
] = max_allocno
++;
380 if (reg_live_length
[i
] == 0)
386 allocno_reg
= (int *) alloca (max_allocno
* sizeof (int));
387 allocno_size
= (int *) alloca (max_allocno
* sizeof (int));
388 allocno_calls_crossed
= (int *) alloca (max_allocno
* sizeof (int));
389 allocno_n_refs
= (int *) alloca (max_allocno
* sizeof (int));
390 allocno_live_length
= (int *) alloca (max_allocno
* sizeof (int));
391 bzero (allocno_size
, max_allocno
* sizeof (int));
392 bzero (allocno_calls_crossed
, max_allocno
* sizeof (int));
393 bzero (allocno_n_refs
, max_allocno
* sizeof (int));
394 bzero (allocno_live_length
, max_allocno
* sizeof (int));
396 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
397 if (reg_allocno
[i
] >= 0)
399 int allocno
= reg_allocno
[i
];
400 allocno_reg
[allocno
] = i
;
401 allocno_size
[allocno
] = PSEUDO_REGNO_SIZE (i
);
402 allocno_calls_crossed
[allocno
] += reg_n_calls_crossed
[i
];
403 allocno_n_refs
[allocno
] += reg_n_refs
[i
];
404 if (allocno_live_length
[allocno
] < reg_live_length
[i
])
405 allocno_live_length
[allocno
] = reg_live_length
[i
];
408 /* Calculate amount of usage of each hard reg by pseudos
409 allocated by local-alloc. This is to see if we want to
411 bzero (local_reg_live_length
, sizeof local_reg_live_length
);
412 bzero (local_reg_n_refs
, sizeof local_reg_n_refs
);
413 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
414 if (reg_allocno
[i
] < 0 && reg_renumber
[i
] >= 0)
416 int regno
= reg_renumber
[i
];
417 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (i
));
420 for (j
= regno
; j
< endregno
; j
++)
422 local_reg_n_refs
[j
] += reg_n_refs
[i
];
423 local_reg_live_length
[j
] += reg_live_length
[i
];
427 /* We can't override local-alloc for a reg used not just by local-alloc. */
428 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
429 if (regs_ever_live
[i
])
430 local_reg_n_refs
[i
] = 0;
432 /* Allocate the space for the conflict and preference tables and
436 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
437 bzero (hard_reg_conflicts
, max_allocno
* sizeof (HARD_REG_SET
));
440 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
441 bzero (hard_reg_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
443 hard_reg_copy_preferences
444 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
445 bzero (hard_reg_copy_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
447 hard_reg_full_preferences
448 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
449 bzero (hard_reg_full_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
452 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
453 bzero (regs_someone_prefers
, max_allocno
* sizeof (HARD_REG_SET
));
455 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
457 conflicts
= (int *) alloca (max_allocno
* allocno_row_words
* sizeof (int));
458 bzero (conflicts
, max_allocno
* allocno_row_words
* sizeof (int));
460 allocnos_live
= (int *) alloca (allocno_row_words
* sizeof (int));
462 /* If there is work to be done (at least one reg to allocate),
463 perform global conflict analysis and allocate the regs. */
467 /* Scan all the insns and compute the conflicts among allocnos
468 and between allocnos and hard regs. */
472 /* Eliminate conflicts between pseudos and eliminable registers. If
473 the register is not eliminated, the pseudo won't really be able to
474 live in the eliminable register, so the conflict doesn't matter.
475 If we do eliminate the register, the conflict will no longer exist.
476 So in either case, we can ignore the conflict. Likewise for
479 for (i
= 0; i
< max_allocno
; i
++)
481 AND_COMPL_HARD_REG_SET (hard_reg_conflicts
[i
], eliminable_regset
);
482 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[i
],
484 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[i
], eliminable_regset
);
487 /* Try to expand the preferences by merging them between allocnos. */
489 expand_preferences ();
491 /* Determine the order to allocate the remaining pseudo registers. */
493 allocno_order
= (int *) alloca (max_allocno
* sizeof (int));
494 for (i
= 0; i
< max_allocno
; i
++)
495 allocno_order
[i
] = i
;
497 /* Default the size to 1, since allocno_compare uses it to divide by.
498 Also convert allocno_live_length of zero to -1. A length of zero
499 can occur when all the registers for that allocno have reg_live_length
500 equal to -2. In this case, we want to make an allocno, but not
501 allocate it. So avoid the divide-by-zero and set it to a low
504 for (i
= 0; i
< max_allocno
; i
++)
506 if (allocno_size
[i
] == 0)
508 if (allocno_live_length
[i
] == 0)
509 allocno_live_length
[i
] = -1;
512 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
514 prune_preferences ();
517 dump_conflicts (file
);
519 /* Try allocating them, one by one, in that order,
520 except for parameters marked with reg_live_length[regno] == -2. */
522 for (i
= 0; i
< max_allocno
; i
++)
523 if (reg_live_length
[allocno_reg
[allocno_order
[i
]]] >= 0)
525 /* If we have more than one register class,
526 first try allocating in the class that is cheapest
527 for this pseudo-reg. If that fails, try any reg. */
528 if (N_REG_CLASSES
> 1)
530 find_reg (allocno_order
[i
], HARD_CONST (0), 0, 0, 0);
531 if (reg_renumber
[allocno_reg
[allocno_order
[i
]]] >= 0)
534 if (!reg_preferred_or_nothing (allocno_reg
[allocno_order
[i
]]))
535 find_reg (allocno_order
[i
], HARD_CONST (0), 1, 0, 0);
539 /* Do the reloads now while the allocno data still exist, so that we can
540 try to assign new hard regs to any pseudo regs that are spilled. */
542 #if 0 /* We need to eliminate regs even if there is no rtl code,
543 for the sake of debugging information. */
544 if (n_basic_blocks
> 0)
546 reload (get_insns (), 1, file
);
549 /* Sort predicate for ordering the allocnos.
550 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
553 allocno_compare (v1
, v2
)
556 /* Note that the quotient will never be bigger than
557 the value of floor_log2 times the maximum number of
558 times a register can occur in one insn (surely less than 100).
559 Multiplying this by 10000 can't overflow. */
561 = (((double) (floor_log2 (allocno_n_refs
[*v1
]) * allocno_n_refs
[*v1
])
562 / (allocno_live_length
[*v1
] * allocno_size
[*v1
]))
565 = (((double) (floor_log2 (allocno_n_refs
[*v2
]) * allocno_n_refs
[*v2
])
566 / (allocno_live_length
[*v2
] * allocno_size
[*v2
]))
571 /* If regs are equally good, sort by allocno,
572 so that the results of qsort leave nothing to chance. */
576 /* Scan the rtl code and record all conflicts and register preferences in the
577 conflict matrices and preference tables. */
584 short *block_start_allocnos
;
586 /* Make a vector that mark_reg_{store,clobber} will store in. */
587 regs_set
= (rtx
*) alloca (max_parallel
* sizeof (rtx
) * 2);
589 block_start_allocnos
= (short *) alloca (max_allocno
* sizeof (short));
591 for (b
= 0; b
< n_basic_blocks
; b
++)
593 bzero (allocnos_live
, allocno_row_words
* sizeof (int));
595 /* Initialize table of registers currently live
596 to the state at the beginning of this basic block.
597 This also marks the conflicts among them.
599 For pseudo-regs, there is only one bit for each one
600 no matter how many hard regs it occupies.
601 This is ok; we know the size from PSEUDO_REGNO_SIZE.
602 For explicit hard regs, we cannot know the size that way
603 since one hard reg can be used with various sizes.
604 Therefore, we must require that all the hard regs
605 implicitly live as part of a multi-word hard reg
606 are explicitly marked in basic_block_live_at_start. */
609 register int offset
, bit
;
610 register regset old
= basic_block_live_at_start
[b
];
614 hard_regs_live
= old
[0];
616 COPY_HARD_REG_SET (hard_regs_live
, old
);
618 for (offset
= 0, i
= 0; offset
< regset_size
; offset
++)
619 if (old
[offset
] == 0)
620 i
+= HOST_BITS_PER_INT
;
622 for (bit
= 1; bit
; bit
<<= 1, i
++)
626 if (old
[offset
] & bit
)
628 register int a
= reg_allocno
[i
];
631 SET_ALLOCNO_LIVE (a
);
632 block_start_allocnos
[ax
++] = a
;
634 else if ((a
= reg_renumber
[i
]) >= 0)
635 mark_reg_live_nc (a
, PSEUDO_REGNO_MODE (i
));
639 /* Record that each allocno now live conflicts with each other
640 allocno now live, and with each hard reg now live. */
642 record_conflicts (block_start_allocnos
, ax
);
645 insn
= basic_block_head
[b
];
647 /* Scan the code of this basic block, noting which allocnos
648 and hard regs are born or die. When one is born,
649 record a conflict with all others currently live. */
653 register RTX_CODE code
= GET_CODE (insn
);
656 /* Make regs_set an empty set. */
660 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
665 for (link
= REG_NOTES (insn
);
666 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
667 link
= XEXP (link
, 1))
668 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
670 no_conflict_pairs
[i
].allocno1
671 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
672 no_conflict_pairs
[i
].allocno2
673 = reg_allocno
[REGNO (XEXP (link
, 0))];
678 /* Mark any registers clobbered by INSN as live,
679 so they conflict with the inputs. */
681 note_stores (PATTERN (insn
), mark_reg_clobber
);
683 /* Mark any registers dead after INSN as dead now. */
685 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
686 if (REG_NOTE_KIND (link
) == REG_DEAD
)
687 mark_reg_death (XEXP (link
, 0));
689 /* Mark any registers set in INSN as live,
690 and mark them as conflicting with all other live regs.
691 Clobbers are processed again, so they conflict with
692 the registers that are set. */
694 note_stores (PATTERN (insn
), mark_reg_store
);
697 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
698 if (REG_NOTE_KIND (link
) == REG_INC
)
699 mark_reg_store (XEXP (link
, 0), 0);
702 /* If INSN has multiple outputs, then any reg that dies here
703 and is used inside of an output
704 must conflict with the other outputs. */
706 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& !single_set (insn
))
707 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
708 if (REG_NOTE_KIND (link
) == REG_DEAD
)
710 int used_in_output
= 0;
712 rtx reg
= XEXP (link
, 0);
714 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
716 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
717 if (GET_CODE (set
) == SET
718 && GET_CODE (SET_DEST (set
)) != REG
719 && !rtx_equal_p (reg
, SET_DEST (set
))
720 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
724 mark_reg_conflicts (reg
);
727 /* Mark any registers set in INSN and then never used. */
729 while (n_regs_set
> 0)
730 if (find_regno_note (insn
, REG_UNUSED
,
731 REGNO (regs_set
[--n_regs_set
])))
732 mark_reg_death (regs_set
[n_regs_set
]);
735 if (insn
== basic_block_end
[b
])
737 insn
= NEXT_INSN (insn
);
741 /* Expand the preference information by looking for cases where one allocno
742 dies in an insn that sets an allocno. If those two allocnos don't conflict,
743 merge any preferences between those allocnos. */
746 expand_preferences ()
752 /* We only try to handle the most common cases here. Most of the cases
753 where this wins are reg-reg copies. */
755 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
756 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
757 && (set
= single_set (insn
)) != 0
758 && GET_CODE (SET_DEST (set
)) == REG
759 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
760 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
761 if (REG_NOTE_KIND (link
) == REG_DEAD
762 && GET_CODE (XEXP (link
, 0)) == REG
763 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
764 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
765 reg_allocno
[REGNO (XEXP (link
, 0))])
766 && ! CONFLICTP (reg_allocno
[REGNO (XEXP (link
, 0))],
767 reg_allocno
[REGNO (SET_DEST (set
))]))
769 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
770 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
772 if (XEXP (link
, 0) == SET_SRC (set
))
774 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a1
],
775 hard_reg_copy_preferences
[a2
]);
776 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a2
],
777 hard_reg_copy_preferences
[a1
]);
780 IOR_HARD_REG_SET (hard_reg_preferences
[a1
],
781 hard_reg_preferences
[a2
]);
782 IOR_HARD_REG_SET (hard_reg_preferences
[a2
],
783 hard_reg_preferences
[a1
]);
784 IOR_HARD_REG_SET (hard_reg_full_preferences
[a1
],
785 hard_reg_full_preferences
[a2
]);
786 IOR_HARD_REG_SET (hard_reg_full_preferences
[a2
],
787 hard_reg_full_preferences
[a1
]);
791 /* Prune the preferences for global registers to exclude registers that cannot
794 Compute `regs_someone_prefers', which is a bitmask of the hard registers
795 that are preferred by conflicting registers of lower priority. If possible,
796 we will avoid using these registers. */
804 /* Scan least most important to most important.
805 For each allocno, remove from preferences registers that cannot be used,
806 either because of conflicts or register type. Then compute all registers
807 preferred by each lower-priority register that conflicts. */
809 for (i
= max_allocno
- 1; i
>= 0; i
--)
813 allocno
= allocno_order
[i
];
814 COPY_HARD_REG_SET (temp
, hard_reg_conflicts
[allocno
]);
816 if (allocno_calls_crossed
[allocno
] == 0)
817 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
819 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
821 IOR_COMPL_HARD_REG_SET
823 reg_class_contents
[(int) reg_preferred_class (allocno_reg
[allocno
])]);
825 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], temp
);
826 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], temp
);
827 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences
[allocno
], temp
);
829 CLEAR_HARD_REG_SET (regs_someone_prefers
[allocno
]);
831 /* Merge in the preferences of lower-priority registers (they have
832 already been pruned). If we also prefer some of those registers,
833 don't exclude them unless we are of a smaller size (in which case
834 we want to give the lower-priority allocno the first chance for
836 for (j
= i
+ 1; j
< max_allocno
; j
++)
837 if (CONFLICTP (allocno
, allocno_order
[j
]))
839 COPY_HARD_REG_SET (temp
,
840 hard_reg_full_preferences
[allocno_order
[j
]]);
841 if (allocno_size
[allocno_order
[j
]] <= allocno_size
[allocno
])
842 AND_COMPL_HARD_REG_SET (temp
,
843 hard_reg_full_preferences
[allocno
]);
845 IOR_HARD_REG_SET (regs_someone_prefers
[allocno
], temp
);
850 /* Assign a hard register to ALLOCNO; look for one that is the beginning
851 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
852 The registers marked in PREFREGS are tried first.
854 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
855 be used for this allocation.
857 If ALL_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
858 Otherwise ignore that preferred class.
860 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
861 will have to be saved and restored at calls.
863 RETRYING is nonzero if this is called from retry_global_alloc.
865 If we find one, record it in reg_renumber.
866 If not, do nothing. */
869 find_reg (allocno
, losers
, all_regs_p
, accept_call_clobbered
, retrying
)
873 int accept_call_clobbered
;
876 register int i
, best_reg
, pass
;
878 register /* Declare it register if it's a scalar. */
880 HARD_REG_SET used
, used1
, used2
;
883 = all_regs_p
? ALL_REGS
: reg_preferred_class (allocno_reg
[allocno
]);
884 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno_reg
[allocno
]);
886 if (accept_call_clobbered
)
887 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
888 else if (allocno_calls_crossed
[allocno
] == 0)
889 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
891 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
893 /* Some registers should not be allocated in global-alloc. */
894 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
896 IOR_HARD_REG_SET (used1
, losers
);
898 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
899 COPY_HARD_REG_SET (used2
, used1
);
901 IOR_HARD_REG_SET (used1
, hard_reg_conflicts
[allocno
]);
903 /* Try each hard reg to see if it fits. Do this in two passes.
904 In the first pass, skip registers that are preferred by some other pseudo
905 to give it a better chance of getting one of those registers. Only if
906 we can't get a register when excluding those do we take one of them.
907 However, we never allocate a register for the first time in pass 0. */
909 COPY_HARD_REG_SET (used
, used1
);
910 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
911 IOR_HARD_REG_SET (used
, regs_someone_prefers
[allocno
]);
914 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
915 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
919 COPY_HARD_REG_SET (used
, used1
);
920 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
922 #ifdef REG_ALLOC_ORDER
923 int regno
= reg_alloc_order
[i
];
927 if (! TEST_HARD_REG_BIT (used
, regno
)
928 && HARD_REGNO_MODE_OK (regno
, mode
))
931 register int lim
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
934 && ! TEST_HARD_REG_BIT (used
, j
));
941 #ifndef REG_ALLOC_ORDER
942 i
= j
; /* Skip starting points we know will lose */
948 /* See if there is a preferred register with the same class as the register
949 we allocated above. Making this restriction prevents register
950 preferencing from creating worse register allocation.
952 Remove from the preferred registers and conflicting registers. Note that
953 additional conflicts may have been added after `prune_preferences' was
956 First do this for those register with copy preferences, then all
957 preferred registers. */
959 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], used
);
960 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences
[allocno
],
961 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
965 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
966 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences
[allocno
], i
)
967 && HARD_REGNO_MODE_OK (i
, mode
)
968 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
969 || reg_class_subset_p (REGNO_REG_CLASS (i
),
970 REGNO_REG_CLASS (best_reg
))
971 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
972 REGNO_REG_CLASS (i
))))
975 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
978 && ! TEST_HARD_REG_BIT (used
, j
)
979 && (REGNO_REG_CLASS (j
)
980 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
981 || reg_class_subset_p (REGNO_REG_CLASS (j
),
982 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
983 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
984 REGNO_REG_CLASS (j
))));
995 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], used
);
996 GO_IF_HARD_REG_SUBSET (hard_reg_preferences
[allocno
],
997 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1001 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1002 if (TEST_HARD_REG_BIT (hard_reg_preferences
[allocno
], i
)
1003 && HARD_REGNO_MODE_OK (i
, mode
)
1004 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1005 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1006 REGNO_REG_CLASS (best_reg
))
1007 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1008 REGNO_REG_CLASS (i
))))
1011 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1014 && ! TEST_HARD_REG_BIT (used
, j
)
1015 && (REGNO_REG_CLASS (j
)
1016 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1017 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1018 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1019 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1020 REGNO_REG_CLASS (j
))));
1031 /* If we haven't succeeded yet, try with caller-saves. */
1032 if (flag_caller_saves
&& best_reg
< 0)
1034 /* Did not find a register. If it would be profitable to
1035 allocate a call-clobbered register and save and restore it
1036 around calls, do that. */
1037 if (! accept_call_clobbered
1038 && allocno_calls_crossed
[allocno
] != 0
1039 && CALLER_SAVE_PROFITABLE (allocno_n_refs
[allocno
],
1040 allocno_calls_crossed
[allocno
]))
1042 find_reg (allocno
, losers
, all_regs_p
, 1, retrying
);
1043 if (reg_renumber
[allocno_reg
[allocno
]] >= 0)
1045 caller_save_needed
= 1;
1051 /* If we haven't succeeded yet,
1052 see if some hard reg that conflicts with us
1053 was utilized poorly by local-alloc.
1054 If so, kick out the regs that were put there by local-alloc
1055 so we can use it instead. */
1056 if (best_reg
< 0 && !retrying
1057 /* Let's not bother with multi-reg allocnos. */
1058 && allocno_size
[allocno
] == 1)
1060 /* Count from the end, to find the least-used ones first. */
1061 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1062 if (local_reg_n_refs
[i
] != 0
1063 /* Don't use a reg no good for this pseudo. */
1064 && ! TEST_HARD_REG_BIT (used2
, i
)
1065 && HARD_REGNO_MODE_OK (i
, mode
)
1066 && ((double) local_reg_n_refs
[i
] / local_reg_live_length
[i
]
1067 < ((double) allocno_n_refs
[allocno
]
1068 / allocno_live_length
[allocno
])))
1070 /* Hard reg I was used less in total by local regs
1071 than it would be used by this one allocno! */
1073 for (k
= 0; k
< max_regno
; k
++)
1074 if (reg_renumber
[k
] >= 0)
1076 int regno
= reg_renumber
[k
];
1078 = regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (k
));
1080 if (i
>= regno
&& i
< endregno
)
1081 reg_renumber
[k
] = -1;
1089 /* Did we find a register? */
1093 register int lim
, j
;
1094 HARD_REG_SET this_reg
;
1096 /* Yes. Record it as the hard register of this pseudo-reg. */
1097 reg_renumber
[allocno_reg
[allocno
]] = best_reg
;
1098 /* Also of any pseudo-regs that share with it. */
1099 if (reg_may_share
[allocno_reg
[allocno
]])
1100 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1101 if (reg_allocno
[j
] == allocno
)
1102 reg_renumber
[j
] = best_reg
;
1104 /* Make a set of the hard regs being allocated. */
1105 CLEAR_HARD_REG_SET (this_reg
);
1106 lim
= best_reg
+ HARD_REGNO_NREGS (best_reg
, mode
);
1107 for (j
= best_reg
; j
< lim
; j
++)
1109 SET_HARD_REG_BIT (this_reg
, j
);
1110 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1111 /* This is no longer a reg used just by local regs. */
1112 local_reg_n_refs
[j
] = 0;
1114 /* For each other pseudo-reg conflicting with this one,
1115 mark it as conflicting with the hard regs this one occupies. */
1117 for (j
= 0; j
< max_allocno
; j
++)
1118 if (CONFLICTP (lim
, j
) || CONFLICTP (j
, lim
))
1120 IOR_HARD_REG_SET (hard_reg_conflicts
[j
], this_reg
);
1125 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1126 Perhaps it had previously seemed not worth a hard reg,
1127 or perhaps its old hard reg has been commandeered for reloads.
1128 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1129 they do not appear to be allocated.
1130 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1133 retry_global_alloc (regno
, forbidden_regs
)
1135 HARD_REG_SET forbidden_regs
;
1137 int allocno
= reg_allocno
[regno
];
1140 /* If we have more than one register class,
1141 first try allocating in the class that is cheapest
1142 for this pseudo-reg. If that fails, try any reg. */
1143 if (N_REG_CLASSES
> 1)
1144 find_reg (allocno
, forbidden_regs
, 0, 0, 1);
1145 if (reg_renumber
[regno
] < 0
1146 && !reg_preferred_or_nothing (regno
))
1147 find_reg (allocno
, forbidden_regs
, 1, 0, 1);
1149 /* If we found a register, modify the RTL for the register to
1150 show the hard register, and mark that register live. */
1151 if (reg_renumber
[regno
] >= 0)
1153 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1154 mark_home_live (regno
);
1159 /* Record a conflict between register REGNO
1160 and everything currently live.
1161 REGNO must not be a pseudo reg that was allocated
1162 by local_alloc; such numbers must be translated through
1163 reg_renumber before calling here. */
1166 record_one_conflict (regno
)
1171 if (regno
< FIRST_PSEUDO_REGISTER
)
1172 /* When a hard register becomes live,
1173 record conflicts with live pseudo regs. */
1174 for (j
= 0; j
< max_allocno
; j
++)
1176 if (ALLOCNO_LIVE_P (j
))
1177 SET_HARD_REG_BIT (hard_reg_conflicts
[j
], regno
);
1180 /* When a pseudo-register becomes live,
1181 record conflicts first with hard regs,
1182 then with other pseudo regs. */
1184 register int ialloc
= reg_allocno
[regno
];
1185 register int ialloc_prod
= ialloc
* allocno_row_words
;
1186 IOR_HARD_REG_SET (hard_reg_conflicts
[ialloc
], hard_regs_live
);
1187 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1191 for (k
= 0; k
< n_no_conflict_pairs
; k
++)
1192 if (! ((j
== no_conflict_pairs
[k
].allocno1
1193 && ialloc
== no_conflict_pairs
[k
].allocno2
)
1195 (j
== no_conflict_pairs
[k
].allocno2
1196 && ialloc
== no_conflict_pairs
[k
].allocno1
)))
1198 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1203 /* Record all allocnos currently live as conflicting
1204 with each other and with all hard regs currently live.
1205 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1206 are currently live. Their bits are also flagged in allocnos_live. */
1209 record_conflicts (allocno_vec
, len
)
1210 register short *allocno_vec
;
1213 register int allocno
;
1215 register int ialloc_prod
;
1219 allocno
= allocno_vec
[len
];
1220 ialloc_prod
= allocno
* allocno_row_words
;
1221 IOR_HARD_REG_SET (hard_reg_conflicts
[allocno
], hard_regs_live
);
1222 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1223 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1227 /* Handle the case where REG is set by the insn being scanned,
1228 during the forward scan to accumulate conflicts.
1229 Store a 1 in regs_live or allocnos_live for this register, record how many
1230 consecutive hardware registers it actually needs,
1231 and record a conflict with all other registers already live.
1233 Note that even if REG does not remain alive after this insn,
1234 we must mark it here as live, to ensure a conflict between
1235 REG and any other regs set in this insn that really do live.
1236 This is because those other regs could be considered after this.
1238 REG might actually be something other than a register;
1239 if so, we do nothing.
1241 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1242 a REG_INC note was found for it).
1244 CLOBBERs are processed here by calling mark_reg_clobber. */
1247 mark_reg_store (orig_reg
, setter
)
1248 rtx orig_reg
, setter
;
1251 register rtx reg
= orig_reg
;
1253 /* WORD is which word of a multi-register group is being stored.
1254 For the case where the store is actually into a SUBREG of REG.
1255 Except we don't use it; I believe the entire REG needs to be
1259 if (GET_CODE (reg
) == SUBREG
)
1261 word
= SUBREG_WORD (reg
);
1262 reg
= SUBREG_REG (reg
);
1265 if (GET_CODE (reg
) != REG
)
1268 if (setter
&& GET_CODE (setter
) == CLOBBER
)
1270 /* A clobber of a register should be processed here too. */
1271 mark_reg_clobber (orig_reg
, setter
);
1275 regs_set
[n_regs_set
++] = reg
;
1278 set_preference (reg
, SET_SRC (setter
));
1280 regno
= REGNO (reg
);
1282 if (reg_renumber
[regno
] >= 0)
1283 regno
= reg_renumber
[regno
] /* + word */;
1285 /* Either this is one of the max_allocno pseudo regs not allocated,
1286 or it is or has a hardware reg. First handle the pseudo-regs. */
1287 if (regno
>= FIRST_PSEUDO_REGISTER
)
1289 if (reg_allocno
[regno
] >= 0)
1291 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1292 record_one_conflict (regno
);
1295 /* Handle hardware regs (and pseudos allocated to hard regs). */
1296 else if (! fixed_regs
[regno
])
1298 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1299 while (regno
< last
)
1301 record_one_conflict (regno
);
1302 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1308 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1311 mark_reg_clobber (reg
, setter
)
1316 /* WORD is which word of a multi-register group is being stored.
1317 For the case where the store is actually into a SUBREG of REG.
1318 Except we don't use it; I believe the entire REG needs to be
1322 if (GET_CODE (setter
) != CLOBBER
)
1325 if (GET_CODE (reg
) == SUBREG
)
1327 word
= SUBREG_WORD (reg
);
1328 reg
= SUBREG_REG (reg
);
1331 if (GET_CODE (reg
) != REG
)
1334 regs_set
[n_regs_set
++] = reg
;
1336 regno
= REGNO (reg
);
1338 if (reg_renumber
[regno
] >= 0)
1339 regno
= reg_renumber
[regno
] /* + word */;
1341 /* Either this is one of the max_allocno pseudo regs not allocated,
1342 or it is or has a hardware reg. First handle the pseudo-regs. */
1343 if (regno
>= FIRST_PSEUDO_REGISTER
)
1345 if (reg_allocno
[regno
] >= 0)
1347 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1348 record_one_conflict (regno
);
1351 /* Handle hardware regs (and pseudos allocated to hard regs). */
1352 else if (! fixed_regs
[regno
])
1354 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1355 while (regno
< last
)
1357 record_one_conflict (regno
);
1358 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1364 /* Record that REG has conflicts with all the regs currently live.
1365 Do not mark REG itself as live. */
1368 mark_reg_conflicts (reg
)
1373 if (GET_CODE (reg
) == SUBREG
)
1374 reg
= SUBREG_REG (reg
);
1376 if (GET_CODE (reg
) != REG
)
1379 regno
= REGNO (reg
);
1381 if (reg_renumber
[regno
] >= 0)
1382 regno
= reg_renumber
[regno
];
1384 /* Either this is one of the max_allocno pseudo regs not allocated,
1385 or it is or has a hardware reg. First handle the pseudo-regs. */
1386 if (regno
>= FIRST_PSEUDO_REGISTER
)
1388 if (reg_allocno
[regno
] >= 0)
1389 record_one_conflict (regno
);
1391 /* Handle hardware regs (and pseudos allocated to hard regs). */
1392 else if (! fixed_regs
[regno
])
1394 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1395 while (regno
< last
)
1397 record_one_conflict (regno
);
1403 /* Mark REG as being dead (following the insn being scanned now).
1404 Store a 0 in regs_live or allocnos_live for this register. */
1407 mark_reg_death (reg
)
1410 register int regno
= REGNO (reg
);
1412 /* For pseudo reg, see if it has been assigned a hardware reg. */
1413 if (reg_renumber
[regno
] >= 0)
1414 regno
= reg_renumber
[regno
];
1416 /* Either this is one of the max_allocno pseudo regs not allocated,
1417 or it is a hardware reg. First handle the pseudo-regs. */
1418 if (regno
>= FIRST_PSEUDO_REGISTER
)
1420 if (reg_allocno
[regno
] >= 0)
1421 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1423 /* Handle hardware regs (and pseudos allocated to hard regs). */
1424 else if (! fixed_regs
[regno
])
1426 /* Pseudo regs already assigned hardware regs are treated
1427 almost the same as explicit hardware regs. */
1428 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1429 while (regno
< last
)
1431 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1437 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1438 for the value stored in it. MODE determines how many consecutive
1439 registers are actually in use. Do not record conflicts;
1440 it is assumed that the caller will do that. */
1443 mark_reg_live_nc (regno
, mode
)
1445 enum machine_mode mode
;
1447 register int last
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1448 while (regno
< last
)
1450 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1455 /* Try to set a preference for an allocno to a hard register.
1456 We are passed DEST and SRC which are the operands of a SET. It is known
1457 that SRC is a register. If SRC or the first operand of SRC is a register,
1458 try to set a preference. If one of the two is a hard register and the other
1459 is a pseudo-register, mark the preference.
1461 Note that we are not as aggressive as local-alloc in trying to tie a
1462 pseudo-register to a hard register. */
1465 set_preference (dest
, src
)
1468 int src_regno
, dest_regno
;
1469 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1470 to compensate for subregs in SRC or DEST. */
1475 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1476 src
= XEXP (src
, 0), copy
= 0;
1478 /* Get the reg number for both SRC and DEST.
1479 If neither is a reg, give up. */
1481 if (GET_CODE (src
) == REG
)
1482 src_regno
= REGNO (src
);
1483 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1485 src_regno
= REGNO (SUBREG_REG (src
));
1486 offset
+= SUBREG_WORD (src
);
1491 if (GET_CODE (dest
) == REG
)
1492 dest_regno
= REGNO (dest
);
1493 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1495 dest_regno
= REGNO (SUBREG_REG (dest
));
1496 offset
-= SUBREG_WORD (dest
);
1501 /* Convert either or both to hard reg numbers. */
1503 if (reg_renumber
[src_regno
] >= 0)
1504 src_regno
= reg_renumber
[src_regno
];
1506 if (reg_renumber
[dest_regno
] >= 0)
1507 dest_regno
= reg_renumber
[dest_regno
];
1509 /* Now if one is a hard reg and the other is a global pseudo
1510 then give the other a preference. */
1512 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1513 && reg_allocno
[src_regno
] >= 0)
1515 dest_regno
-= offset
;
1516 if (dest_regno
>= 0 && dest_regno
< FIRST_PSEUDO_REGISTER
)
1519 SET_REGBIT (hard_reg_copy_preferences
,
1520 reg_allocno
[src_regno
], dest_regno
);
1522 SET_REGBIT (hard_reg_preferences
,
1523 reg_allocno
[src_regno
], dest_regno
);
1524 for (i
= dest_regno
;
1525 i
< dest_regno
+ HARD_REGNO_NREGS (dest_regno
, GET_MODE (dest
));
1527 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1531 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1532 && reg_allocno
[dest_regno
] >= 0)
1534 src_regno
+= offset
;
1535 if (src_regno
>= 0 && src_regno
< FIRST_PSEUDO_REGISTER
)
1538 SET_REGBIT (hard_reg_copy_preferences
,
1539 reg_allocno
[dest_regno
], src_regno
);
1541 SET_REGBIT (hard_reg_preferences
,
1542 reg_allocno
[dest_regno
], src_regno
);
1544 i
< src_regno
+ HARD_REGNO_NREGS (src_regno
, GET_MODE (src
));
1546 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1551 /* Indicate that hard register number FROM was eliminated and replaced with
1552 an offset from hard register number TO. The status of hard registers live
1553 at the start of a basic block is updated by replacing a use of FROM with
1557 mark_elimination (from
, to
)
1562 for (i
= 0; i
< n_basic_blocks
; i
++)
1563 if ((basic_block_live_at_start
[i
][from
/ HOST_BITS_PER_INT
]
1564 & (1 << (from
% HOST_BITS_PER_INT
))) != 0)
1566 basic_block_live_at_start
[i
][from
/ HOST_BITS_PER_INT
]
1567 &= ~ (1 << (from
% HOST_BITS_PER_INT
));
1568 basic_block_live_at_start
[i
][to
/ HOST_BITS_PER_INT
]
1569 |= (1 << (to
% HOST_BITS_PER_INT
));
1573 /* Print debugging trace information if -greg switch is given,
1574 showing the information on which the allocation decisions are based. */
1577 dump_conflicts (file
)
1581 register int has_preferences
;
1582 fprintf (file
, ";; %d regs to allocate:", max_allocno
);
1583 for (i
= 0; i
< max_allocno
; i
++)
1586 fprintf (file
, " %d", allocno_reg
[allocno_order
[i
]]);
1587 for (j
= 0; j
< max_regno
; j
++)
1588 if (reg_allocno
[j
] == allocno_order
[i
]
1589 && j
!= allocno_reg
[allocno_order
[i
]])
1590 fprintf (file
, "+%d", j
);
1591 if (allocno_size
[allocno_order
[i
]] != 1)
1592 fprintf (file
, " (%d)", allocno_size
[allocno_order
[i
]]);
1594 fprintf (file
, "\n");
1596 for (i
= 0; i
< max_allocno
; i
++)
1599 fprintf (file
, ";; %d conflicts:", allocno_reg
[i
]);
1600 for (j
= 0; j
< max_allocno
; j
++)
1601 if (CONFLICTP (i
, j
) || CONFLICTP (j
, i
))
1602 fprintf (file
, " %d", allocno_reg
[j
]);
1603 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1604 if (TEST_HARD_REG_BIT (hard_reg_conflicts
[i
], j
))
1605 fprintf (file
, " %d", j
);
1606 fprintf (file
, "\n");
1608 has_preferences
= 0;
1609 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1610 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1611 has_preferences
= 1;
1613 if (! has_preferences
)
1615 fprintf (file
, ";; %d preferences:", allocno_reg
[i
]);
1616 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1617 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1618 fprintf (file
, " %d", j
);
1619 fprintf (file
, "\n");
1621 fprintf (file
, "\n");
1625 dump_global_regs (file
)
1630 fprintf (file
, ";; Register dispositions:\n");
1631 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1632 if (reg_renumber
[i
] >= 0)
1634 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1636 fprintf (file
, "\n");
1639 fprintf (file
, "\n\n;; Hard regs used: ");
1640 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1641 if (regs_ever_live
[i
])
1642 fprintf (file
, " %d", i
);
1643 fprintf (file
, "\n\n");