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 peudo
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_live_nc ();
252 static void mark_reg_death ();
253 static void dump_conflicts ();
254 void dump_global_regs ();
255 static void find_reg ();
256 static void global_conflicts ();
257 static void expand_preferences ();
258 static void prune_preferences ();
259 static void record_conflicts ();
260 static void set_preference ();
262 /* Perform allocation of pseudo-registers not allocated by local_alloc.
263 FILE is a file to output debugging information on,
264 or zero if such output is not desired. */
270 #ifdef ELIMINABLE_REGS
271 static struct {int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
278 /* A machine may have certain hard registers that
279 are safe to use only within a basic block. */
281 CLEAR_HARD_REG_SET (no_global_alloc_regs
);
282 #ifdef OVERLAPPING_REGNO_P
283 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
284 if (OVERLAPPING_REGNO_P (i
))
285 SET_HARD_REG_BIT (no_global_alloc_regs
, i
);
288 /* Build the regset of all eliminable registers and show we can't use those
289 that we already know won't be eliminated. */
290 #ifdef ELIMINABLE_REGS
291 for (i
= 0; i
< sizeof eliminables
/ sizeof eliminables
[0]; i
++)
293 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
295 if (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
296 || (eliminables
[i
].from
== FRAME_POINTER_REGNUM
297 && (! flag_omit_frame_pointer
|| FRAME_POINTER_REQUIRED
)))
298 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
301 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
303 /* If we know we will definitely not be eliminating the frame pointer,
304 don't allocate it. */
305 if (! flag_omit_frame_pointer
|| FRAME_POINTER_REQUIRED
)
306 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
309 /* Track which registers have already been used. Start with registers
310 explicitly in the rtl, then registers allocated by local register
313 CLEAR_HARD_REG_SET (regs_used_so_far
);
314 #ifdef LEAF_REGISTERS
315 /* If we are doing the leaf function optimization, and this is a leaf
316 function, it means that the registers that take work to save are those
317 that need a register window. So prefer the ones that can be used in
321 static char leaf_regs
[] = LEAF_REGISTERS
;
323 if (only_leaf_regs_used () && leaf_function_p ())
324 cheap_regs
= leaf_regs
;
326 cheap_regs
= call_used_regs
;
327 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
328 if (regs_ever_live
[i
] || cheap_regs
[i
])
329 SET_HARD_REG_BIT (regs_used_so_far
, i
);
332 /* We consider registers that do not have to be saved over calls as if
333 they were already used since there is no cost in using them. */
334 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
335 if (regs_ever_live
[i
] || call_used_regs
[i
])
336 SET_HARD_REG_BIT (regs_used_so_far
, i
);
339 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
340 if (reg_renumber
[i
] >= 0)
341 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
343 /* Establish mappings from register number to allocation number
344 and vice versa. In the process, count the allocnos. */
346 reg_allocno
= (int *) alloca (max_regno
* sizeof (int));
348 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
351 /* Initialize the shared-hard-reg mapping
352 from the list of pairs that may share. */
353 reg_may_share
= (int *) alloca (max_regno
* sizeof (int));
354 bzero (reg_may_share
, max_regno
* sizeof (int));
355 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
357 int r1
= REGNO (XEXP (x
, 0));
358 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
360 reg_may_share
[r1
] = r2
;
362 reg_may_share
[r2
] = r1
;
365 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
366 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
367 that we are supposed to refrain from putting in a hard reg.
368 -2 means do make an allocno but don't allocate it. */
369 if (reg_n_refs
[i
] != 0 && reg_renumber
[i
] < 0 && reg_live_length
[i
] != -1
370 /* Don't allocate pseudos that cross calls,
371 if this function receives a nonlocal goto. */
372 && (! current_function_has_nonlocal_label
373 || reg_n_calls_crossed
[i
] == 0))
375 if (reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
376 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
378 reg_allocno
[i
] = max_allocno
++;
379 if (reg_live_length
[i
] == 0)
385 allocno_reg
= (int *) alloca (max_allocno
* sizeof (int));
386 allocno_size
= (int *) alloca (max_allocno
* sizeof (int));
387 allocno_calls_crossed
= (int *) alloca (max_allocno
* sizeof (int));
388 allocno_n_refs
= (int *) alloca (max_allocno
* sizeof (int));
389 allocno_live_length
= (int *) alloca (max_allocno
* sizeof (int));
390 bzero (allocno_size
, max_allocno
* sizeof (int));
391 bzero (allocno_calls_crossed
, max_allocno
* sizeof (int));
392 bzero (allocno_n_refs
, max_allocno
* sizeof (int));
393 bzero (allocno_live_length
, max_allocno
* sizeof (int));
395 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
396 if (reg_allocno
[i
] >= 0)
398 int allocno
= reg_allocno
[i
];
399 allocno_reg
[allocno
] = i
;
400 allocno_size
[allocno
] = PSEUDO_REGNO_SIZE (i
);
401 allocno_calls_crossed
[allocno
] += reg_n_calls_crossed
[i
];
402 allocno_n_refs
[allocno
] += reg_n_refs
[i
];
403 if (allocno_live_length
[allocno
] < reg_live_length
[i
])
404 allocno_live_length
[allocno
] = reg_live_length
[i
];
407 /* Calculate amount of usage of each hard reg by pseudos
408 allocated by local-alloc. This is to see if we want to
410 bzero (local_reg_live_length
, sizeof local_reg_live_length
);
411 bzero (local_reg_n_refs
, sizeof local_reg_n_refs
);
412 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
413 if (reg_allocno
[i
] < 0 && reg_renumber
[i
] >= 0)
415 int regno
= reg_renumber
[i
];
416 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (i
));
419 for (j
= regno
; j
< endregno
; j
++)
421 local_reg_n_refs
[j
] += reg_n_refs
[i
];
422 local_reg_live_length
[j
] += reg_live_length
[i
];
426 /* We can't override local-alloc for a reg used not just by local-alloc. */
427 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
428 if (regs_ever_live
[i
])
429 local_reg_n_refs
[i
] = 0;
431 /* Allocate the space for the conflict and preference tables and
435 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
436 bzero (hard_reg_conflicts
, max_allocno
* sizeof (HARD_REG_SET
));
439 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
440 bzero (hard_reg_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
442 hard_reg_copy_preferences
443 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
444 bzero (hard_reg_copy_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
446 hard_reg_full_preferences
447 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
448 bzero (hard_reg_full_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
451 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
452 bzero (regs_someone_prefers
, max_allocno
* sizeof (HARD_REG_SET
));
454 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
456 conflicts
= (int *) alloca (max_allocno
* allocno_row_words
* sizeof (int));
457 bzero (conflicts
, max_allocno
* allocno_row_words
* sizeof (int));
459 allocnos_live
= (int *) alloca (allocno_row_words
* sizeof (int));
461 /* If there is work to be done (at least one reg to allocate),
462 perform global conflict analysis and allocate the regs. */
466 /* Scan all the insns and compute the conflicts among allocnos
467 and between allocnos and hard regs. */
471 /* Eliminate conflicts between pseudos and eliminable registers. If
472 the register is not eliminated, the pseudo won't really be able to
473 live in the eliminable register, so the conflict doesn't matter.
474 If we do eliminate the register, the conflict will no longer exist.
475 So in either case, we can ignore the conflict. Likewise for
478 for (i
= 0; i
< max_allocno
; i
++)
480 AND_COMPL_HARD_REG_SET (hard_reg_conflicts
[i
], eliminable_regset
);
481 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[i
],
483 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[i
], eliminable_regset
);
486 /* Try to expand the preferences by merging them between allocnos. */
488 expand_preferences ();
490 /* Determine the order to allocate the remaining pseudo registers. */
492 allocno_order
= (int *) alloca (max_allocno
* sizeof (int));
493 for (i
= 0; i
< max_allocno
; i
++)
494 allocno_order
[i
] = i
;
496 /* Default the size to 1, since allocno_compare uses it to divide by.
497 Also convert allocno_live_length of zero to -1. A length of zero
498 can occur when all the registers for that allocno have reg_live_length
499 equal to -2. In this case, we want to make an allocno, but not
500 allocate it. So avoid the divide-by-zero and set it to a low
503 for (i
= 0; i
< max_allocno
; i
++)
505 if (allocno_size
[i
] == 0)
507 if (allocno_live_length
[i
] == 0)
508 allocno_live_length
[i
] = -1;
511 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
513 prune_preferences ();
516 dump_conflicts (file
);
518 /* Try allocating them, one by one, in that order,
519 except for parameters marked with reg_live_length[regno] == -2. */
521 for (i
= 0; i
< max_allocno
; i
++)
522 if (reg_live_length
[allocno_reg
[allocno_order
[i
]]] >= 0)
524 /* If we have more than one register class,
525 first try allocating in the class that is cheapest
526 for this pseudo-reg. If that fails, try any reg. */
527 if (N_REG_CLASSES
> 1)
529 find_reg (allocno_order
[i
], HARD_CONST (0), 0, 0, 0);
530 if (reg_renumber
[allocno_reg
[allocno_order
[i
]]] >= 0)
533 if (!reg_preferred_or_nothing (allocno_reg
[allocno_order
[i
]]))
534 find_reg (allocno_order
[i
], HARD_CONST (0), 1, 0, 0);
538 /* Do the reloads now while the allocno data still exist, so that we can
539 try to assign new hard regs to any pseudo regs that are spilled. */
541 #if 0 /* We need to eliminate regs even if there is no rtl code,
542 for the sake of debugging information. */
543 if (n_basic_blocks
> 0)
545 reload (basic_block_head
[0], 1, file
);
548 /* Sort predicate for ordering the allocnos.
549 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
552 allocno_compare (v1
, v2
)
555 /* Note that the quotient will never be bigger than
556 the value of floor_log2 times the maximum number of
557 times a register can occur in one insn (surely less than 100).
558 Multiplying this by 10000 can't overflow. */
560 = (((double) (floor_log2 (allocno_n_refs
[*v1
]) * allocno_n_refs
[*v1
])
561 / (allocno_live_length
[*v1
] * allocno_size
[*v1
]))
564 = (((double) (floor_log2 (allocno_n_refs
[*v2
]) * allocno_n_refs
[*v2
])
565 / (allocno_live_length
[*v2
] * allocno_size
[*v2
]))
570 /* If regs are equally good, sort by allocno,
571 so that the results of qsort leave nothing to chance. */
575 /* Scan the rtl code and record all conflicts and register preferences in the
576 conflict matrices and preference tables. */
583 short *block_start_allocnos
;
585 /* Make a vector that mark_reg_{store,clobber} will store in. */
586 regs_set
= (rtx
*) alloca (max_parallel
* sizeof (rtx
) * 2);
588 block_start_allocnos
= (short *) alloca (max_allocno
* sizeof (short));
590 for (b
= 0; b
< n_basic_blocks
; b
++)
592 bzero (allocnos_live
, allocno_row_words
* sizeof (int));
594 /* Initialize table of registers currently live
595 to the state at the beginning of this basic block.
596 This also marks the conflicts among them.
598 For pseudo-regs, there is only one bit for each one
599 no matter how many hard regs it occupies.
600 This is ok; we know the size from PSEUDO_REGNO_SIZE.
601 For explicit hard regs, we cannot know the size that way
602 since one hard reg can be used with various sizes.
603 Therefore, we must require that all the hard regs
604 implicitly live as part of a multi-word hard reg
605 are explicitly marked in basic_block_live_at_start. */
608 register int offset
, bit
;
609 register regset old
= basic_block_live_at_start
[b
];
613 hard_regs_live
= old
[0];
615 COPY_HARD_REG_SET (hard_regs_live
, old
);
617 for (offset
= 0, i
= 0; offset
< regset_size
; offset
++)
618 if (old
[offset
] == 0)
619 i
+= HOST_BITS_PER_INT
;
621 for (bit
= 1; bit
; bit
<<= 1, i
++)
625 if (old
[offset
] & bit
)
627 register int a
= reg_allocno
[i
];
630 SET_ALLOCNO_LIVE (a
);
631 block_start_allocnos
[ax
++] = a
;
633 else if ((a
= reg_renumber
[i
]) >= 0)
634 mark_reg_live_nc (a
, PSEUDO_REGNO_MODE (i
));
638 /* Record that each allocno now live conflicts with each other
639 allocno now live, and with each hard reg now live. */
641 record_conflicts (block_start_allocnos
, ax
);
644 insn
= basic_block_head
[b
];
646 /* Scan the code of this basic block, noting which allocnos
647 and hard regs are born or die. When one is born,
648 record a conflict with all others currently live. */
652 register RTX_CODE code
= GET_CODE (insn
);
655 /* Make regs_set an empty set. */
659 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
664 for (link
= REG_NOTES (insn
);
665 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
666 link
= XEXP (link
, 1))
667 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
669 no_conflict_pairs
[i
].allocno1
670 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
671 no_conflict_pairs
[i
].allocno2
672 = reg_allocno
[REGNO (XEXP (link
, 0))];
677 /* Mark any registers clobbered by INSN as live,
678 so they conflict with the inputs. */
680 note_stores (PATTERN (insn
), mark_reg_clobber
);
682 /* Mark any registers dead after INSN as dead now. */
684 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
685 if (REG_NOTE_KIND (link
) == REG_DEAD
)
686 mark_reg_death (XEXP (link
, 0));
688 /* Mark any registers set in INSN as live,
689 and mark them as conflicting with all other live regs.
690 Clobbers are processed again, so they conflict with
691 the registers that are set. */
693 note_stores (PATTERN (insn
), mark_reg_store
);
696 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
697 if (REG_NOTE_KIND (link
) == REG_INC
)
698 mark_reg_store (XEXP (link
, 0), 0);
701 /* Mark any registers set in INSN and then never used. */
703 while (n_regs_set
> 0)
704 if (find_regno_note (insn
, REG_UNUSED
,
705 REGNO (regs_set
[--n_regs_set
])))
706 mark_reg_death (regs_set
[n_regs_set
]);
709 if (insn
== basic_block_end
[b
])
711 insn
= NEXT_INSN (insn
);
715 /* Expand the preference information by looking for cases where one allocno
716 dies in an insn that sets an allocno. If those two allocnos don't conflict,
717 merge any preferences between those allocnos. */
720 expand_preferences ()
726 /* We only try to handle the most common cases here. Most of the cases
727 where this wins are reg-reg copies. */
729 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
730 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
731 && (set
= single_set (insn
)) != 0
732 && GET_CODE (SET_DEST (set
)) == REG
733 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
734 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
735 if (REG_NOTE_KIND (link
) == REG_DEAD
736 && GET_CODE (XEXP (link
, 0)) == REG
737 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
738 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
739 reg_allocno
[REGNO (XEXP (link
, 0))])
740 && ! CONFLICTP (reg_allocno
[REGNO (XEXP (link
, 0))],
741 reg_allocno
[REGNO (SET_DEST (set
))]))
743 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
744 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
746 if (XEXP (link
, 0) == SET_SRC (set
))
748 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a1
],
749 hard_reg_copy_preferences
[a2
]);
750 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a2
],
751 hard_reg_copy_preferences
[a1
]);
754 IOR_HARD_REG_SET (hard_reg_preferences
[a1
],
755 hard_reg_preferences
[a2
]);
756 IOR_HARD_REG_SET (hard_reg_preferences
[a2
],
757 hard_reg_preferences
[a1
]);
758 IOR_HARD_REG_SET (hard_reg_full_preferences
[a1
],
759 hard_reg_full_preferences
[a2
]);
760 IOR_HARD_REG_SET (hard_reg_full_preferences
[a2
],
761 hard_reg_full_preferences
[a1
]);
765 /* Prune the preferences for global registers to exclude registers that cannot
768 Compute `regs_someone_prefers', which is a bitmask of the hard registers
769 that are preferred by conflicting registers of lower priority. If possible,
770 we will avoid using these registers. */
778 /* Scan least most important to most important.
779 For each allocno, remove from preferences registers that cannot be used,
780 either because of conflicts or register type. Then compute all registers
781 prefered by each lower-priority register that conflicts. */
783 for (i
= max_allocno
- 1; i
>= 0; i
--)
787 allocno
= allocno_order
[i
];
788 COPY_HARD_REG_SET (temp
, hard_reg_conflicts
[allocno
]);
790 if (allocno_calls_crossed
[allocno
] == 0)
791 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
793 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
795 IOR_COMPL_HARD_REG_SET
797 reg_class_contents
[(int) reg_preferred_class (allocno_reg
[allocno
])]);
799 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], temp
);
800 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], temp
);
801 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences
[allocno
], temp
);
803 CLEAR_HARD_REG_SET (regs_someone_prefers
[allocno
]);
805 /* Merge in the preferences of lower-priority registers (they have
806 already been pruned). If we also prefer some of those registers,
807 don't exclude them unless we are of a smaller size (in which case
808 we want to give the lower-priority allocno the first chance for
810 for (j
= i
+ 1; j
< max_allocno
; j
++)
811 if (CONFLICTP (allocno
, allocno_order
[j
]))
813 COPY_HARD_REG_SET (temp
,
814 hard_reg_full_preferences
[allocno_order
[j
]]);
815 if (allocno_size
[allocno_order
[j
]] <= allocno_size
[allocno
])
816 AND_COMPL_HARD_REG_SET (temp
,
817 hard_reg_full_preferences
[allocno
]);
819 IOR_HARD_REG_SET (regs_someone_prefers
[allocno
], temp
);
824 /* Assign a hard register to ALLOCNO; look for one that is the beginning
825 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
826 The registers marked in PREFREGS are tried first.
828 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
829 be used for this allocation.
831 If ALL_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
832 Otherwise ignore that preferred class.
834 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
835 will have to be saved and restored at calls.
837 RETRYING is nonzero if this is called from retry_global_alloc.
839 If we find one, record it in reg_renumber.
840 If not, do nothing. */
843 find_reg (allocno
, losers
, all_regs_p
, accept_call_clobbered
, retrying
)
847 int accept_call_clobbered
;
850 register int i
, best_reg
, pass
;
852 register /* Declare it register if it's a scalar. */
854 HARD_REG_SET used
, used1
, used2
;
857 = all_regs_p
? ALL_REGS
: reg_preferred_class (allocno_reg
[allocno
]);
858 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno_reg
[allocno
]);
860 if (accept_call_clobbered
)
861 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
862 else if (allocno_calls_crossed
[allocno
] == 0)
863 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
865 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
867 /* Some registers should not be allocated in global-alloc. */
868 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
870 IOR_HARD_REG_SET (used1
, losers
);
872 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
873 COPY_HARD_REG_SET (used2
, used1
);
875 IOR_HARD_REG_SET (used1
, hard_reg_conflicts
[allocno
]);
877 /* Try each hard reg to see if it fits. Do this in two passes.
878 In the first pass, skip registers that are prefered by some other pseudo
879 to give it a better chance of getting one of those registers. Only if
880 we can't get a register when excluding those do we take one of them.
881 However, we never allocate a register for the first time in pass 0. */
883 COPY_HARD_REG_SET (used
, used1
);
884 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
885 IOR_HARD_REG_SET (used
, regs_someone_prefers
[allocno
]);
888 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
889 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
893 COPY_HARD_REG_SET (used
, used1
);
894 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
896 #ifdef REG_ALLOC_ORDER
897 int regno
= reg_alloc_order
[i
];
901 if (! TEST_HARD_REG_BIT (used
, regno
)
902 && HARD_REGNO_MODE_OK (regno
, mode
))
905 register int lim
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
908 && ! TEST_HARD_REG_BIT (used
, j
));
915 #ifndef REG_ALLOC_ORDER
916 i
= j
; /* Skip starting points we know will lose */
922 /* See if there is a preferred register with the same class as the register
923 we allocated above. Making this restriction prevents register
924 preferencing from creating worse register allocation.
926 Remove from the preferred registers and conflicting registers. Note that
927 additional conflicts may have been added after `prune_preferences' was
930 First do this for those register with copy preferences, then all
931 preferred registers. */
933 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], used
);
934 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences
[allocno
],
935 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
939 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
940 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences
[allocno
], i
)
941 && HARD_REGNO_MODE_OK (i
, mode
)
942 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
943 || reg_class_subset_p (REGNO_REG_CLASS (i
),
944 REGNO_REG_CLASS (best_reg
))
945 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
946 REGNO_REG_CLASS (i
))))
949 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
952 && ! TEST_HARD_REG_BIT (used
, j
)
953 && (REGNO_REG_CLASS (j
)
954 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
955 || reg_class_subset_p (REGNO_REG_CLASS (j
),
956 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
957 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
958 REGNO_REG_CLASS (j
))));
969 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], used
);
970 GO_IF_HARD_REG_SUBSET (hard_reg_preferences
[allocno
],
971 reg_class_contents
[(int) NO_REGS
], no_prefs
);
975 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
976 if (TEST_HARD_REG_BIT (hard_reg_preferences
[allocno
], i
)
977 && HARD_REGNO_MODE_OK (i
, mode
)
978 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
979 || reg_class_subset_p (REGNO_REG_CLASS (i
),
980 REGNO_REG_CLASS (best_reg
))
981 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
982 REGNO_REG_CLASS (i
))))
985 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
988 && ! TEST_HARD_REG_BIT (used
, j
)
989 && (REGNO_REG_CLASS (j
)
990 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
991 || reg_class_subset_p (REGNO_REG_CLASS (j
),
992 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
993 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
994 REGNO_REG_CLASS (j
))));
1005 /* If we haven't succeeded yet, try with caller-saves. */
1006 if (flag_caller_saves
&& best_reg
< 0)
1008 /* Did not find a register. If it would be profitable to
1009 allocate a call-clobbered register and save and restore it
1010 around calls, do that. */
1011 if (! accept_call_clobbered
1012 && allocno_calls_crossed
[allocno
] != 0
1013 && CALLER_SAVE_PROFITABLE (allocno_n_refs
[allocno
],
1014 allocno_calls_crossed
[allocno
]))
1016 find_reg (allocno
, losers
, all_regs_p
, 1, retrying
);
1017 if (reg_renumber
[allocno_reg
[allocno
]] >= 0)
1019 caller_save_needed
= 1;
1025 /* If we haven't succeeded yet,
1026 see if some hard reg that conflicts with us
1027 was utilized poorly by local-alloc.
1028 If so, kick out the regs that were put there by local-alloc
1029 so we can use it instead. */
1030 if (best_reg
< 0 && !retrying
1031 /* Let's not bother with multi-reg allocnos. */
1032 && allocno_size
[allocno
] == 1)
1034 /* Count from the end, to find the least-used ones first. */
1035 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1036 if (local_reg_n_refs
[i
] != 0
1037 /* Don't use a reg no good for this pseudo. */
1038 && ! TEST_HARD_REG_BIT (used2
, i
)
1039 && HARD_REGNO_MODE_OK (i
, mode
)
1040 && ((double) local_reg_n_refs
[i
] / local_reg_live_length
[i
]
1041 < ((double) allocno_n_refs
[allocno
]
1042 / allocno_live_length
[allocno
])))
1044 /* Hard reg I was used less in total by local regs
1045 than it would be used by this one allocno! */
1047 for (k
= 0; k
< max_regno
; k
++)
1048 if (reg_renumber
[k
] >= 0)
1050 int regno
= reg_renumber
[k
];
1052 = regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (k
));
1054 if (i
>= regno
&& i
< endregno
)
1055 reg_renumber
[k
] = -1;
1063 /* Did we find a register? */
1067 register int lim
, j
;
1068 HARD_REG_SET this_reg
;
1070 /* Yes. Record it as the hard register of this pseudo-reg. */
1071 reg_renumber
[allocno_reg
[allocno
]] = best_reg
;
1072 /* Also of any pseudo-regs that share with it. */
1073 if (reg_may_share
[allocno_reg
[allocno
]])
1074 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1075 if (reg_allocno
[j
] == allocno
)
1076 reg_renumber
[j
] = best_reg
;
1078 /* Make a set of the hard regs being allocated. */
1079 CLEAR_HARD_REG_SET (this_reg
);
1080 lim
= best_reg
+ HARD_REGNO_NREGS (best_reg
, mode
);
1081 for (j
= best_reg
; j
< lim
; j
++)
1083 SET_HARD_REG_BIT (this_reg
, j
);
1084 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1085 /* This is no longer a reg used just by local regs. */
1086 local_reg_n_refs
[j
] = 0;
1088 /* For each other pseudo-reg conflicting with this one,
1089 mark it as conflicting with the hard regs this one occupies. */
1091 for (j
= 0; j
< max_allocno
; j
++)
1092 if (CONFLICTP (lim
, j
) || CONFLICTP (j
, lim
))
1094 IOR_HARD_REG_SET (hard_reg_conflicts
[j
], this_reg
);
1099 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1100 Perhaps it had previously seemed not worth a hard reg,
1101 or perhaps its old hard reg has been commandeered for reloads.
1102 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1103 they do not appear to be allocated.
1104 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1107 retry_global_alloc (regno
, forbidden_regs
)
1109 HARD_REG_SET forbidden_regs
;
1111 int allocno
= reg_allocno
[regno
];
1114 /* If we have more than one register class,
1115 first try allocating in the class that is cheapest
1116 for this pseudo-reg. If that fails, try any reg. */
1117 if (N_REG_CLASSES
> 1)
1118 find_reg (allocno
, forbidden_regs
, 0, 0, 1);
1119 if (reg_renumber
[regno
] < 0
1120 && !reg_preferred_or_nothing (regno
))
1121 find_reg (allocno
, forbidden_regs
, 1, 0, 1);
1123 /* If we found a register, modify the RTL for the register to
1124 show the hard register, and mark that register live. */
1125 if (reg_renumber
[regno
] >= 0)
1127 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1128 mark_home_live (regno
);
1133 /* Record a conflict between register REGNO
1134 and everything currently live.
1135 REGNO must not be a pseudo reg that was allocated
1136 by local_alloc; such numbers must be translated through
1137 reg_renumber before calling here. */
1140 record_one_conflict (regno
)
1145 if (regno
< FIRST_PSEUDO_REGISTER
)
1146 /* When a hard register becomes live,
1147 record conflicts with live pseudo regs. */
1148 for (j
= 0; j
< max_allocno
; j
++)
1150 if (ALLOCNO_LIVE_P (j
))
1151 SET_HARD_REG_BIT (hard_reg_conflicts
[j
], regno
);
1154 /* When a pseudo-register becomes live,
1155 record conflicts first with hard regs,
1156 then with other pseudo regs. */
1158 register int ialloc
= reg_allocno
[regno
];
1159 register int ialloc_prod
= ialloc
* allocno_row_words
;
1160 IOR_HARD_REG_SET (hard_reg_conflicts
[ialloc
], hard_regs_live
);
1161 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1165 for (k
= 0; k
< n_no_conflict_pairs
; k
++)
1166 if (! ((j
== no_conflict_pairs
[k
].allocno1
1167 && ialloc
== no_conflict_pairs
[k
].allocno2
)
1169 (j
== no_conflict_pairs
[k
].allocno2
1170 && ialloc
== no_conflict_pairs
[k
].allocno1
)))
1172 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1177 /* Record all allocnos currently live as conflicting
1178 with each other and with all hard regs currently live.
1179 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1180 are currently live. Their bits are also flagged in allocnos_live. */
1183 record_conflicts (allocno_vec
, len
)
1184 register short *allocno_vec
;
1187 register int allocno
;
1189 register int ialloc_prod
;
1193 allocno
= allocno_vec
[len
];
1194 ialloc_prod
= allocno
* allocno_row_words
;
1195 IOR_HARD_REG_SET (hard_reg_conflicts
[allocno
], hard_regs_live
);
1196 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1197 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1201 /* Handle the case where REG is set by the insn being scanned,
1202 during the forward scan to accumulate conflicts.
1203 Store a 1 in regs_live or allocnos_live for this register, record how many
1204 consecutive hardware registers it actually needs,
1205 and record a conflict with all other registers already live.
1207 Note that even if REG does not remain alive after this insn,
1208 we must mark it here as live, to ensure a conflict between
1209 REG and any other regs set in this insn that really do live.
1210 This is because those other regs could be considered after this.
1212 REG might actually be something other than a register;
1213 if so, we do nothing.
1215 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1216 a REG_INC note was found for it).
1218 CLOBBERs are processed here by calling mark_reg_clobber. */
1221 mark_reg_store (orig_reg
, setter
)
1222 rtx orig_reg
, setter
;
1225 register rtx reg
= orig_reg
;
1227 /* WORD is which word of a multi-register group is being stored.
1228 For the case where the store is actually into a SUBREG of REG.
1229 Except we don't use it; I believe the entire REG needs to be
1233 if (GET_CODE (reg
) == SUBREG
)
1235 word
= SUBREG_WORD (reg
);
1236 reg
= SUBREG_REG (reg
);
1239 if (GET_CODE (reg
) != REG
)
1242 if (setter
&& GET_CODE (setter
) == CLOBBER
)
1244 /* A clobber of a register should be processed here too. */
1245 mark_reg_clobber (orig_reg
, setter
);
1249 regs_set
[n_regs_set
++] = reg
;
1252 set_preference (reg
, SET_SRC (setter
));
1254 regno
= REGNO (reg
);
1256 if (reg_renumber
[regno
] >= 0)
1257 regno
= reg_renumber
[regno
] /* + word */;
1259 /* Either this is one of the max_allocno pseudo regs not allocated,
1260 or it is or has a hardware reg. First handle the pseudo-regs. */
1261 if (regno
>= FIRST_PSEUDO_REGISTER
)
1263 if (reg_allocno
[regno
] >= 0)
1265 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1266 record_one_conflict (regno
);
1269 /* Handle hardware regs (and pseudos allocated to hard regs). */
1270 else if (! fixed_regs
[regno
])
1272 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1273 while (regno
< last
)
1275 record_one_conflict (regno
);
1276 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1282 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1285 mark_reg_clobber (reg
, setter
)
1290 /* WORD is which word of a multi-register group is being stored.
1291 For the case where the store is actually into a SUBREG of REG.
1292 Except we don't use it; I believe the entire REG needs to be
1296 if (GET_CODE (setter
) != CLOBBER
)
1299 if (GET_CODE (reg
) == SUBREG
)
1301 word
= SUBREG_WORD (reg
);
1302 reg
= SUBREG_REG (reg
);
1305 if (GET_CODE (reg
) != REG
)
1308 regs_set
[n_regs_set
++] = reg
;
1310 regno
= REGNO (reg
);
1312 if (reg_renumber
[regno
] >= 0)
1313 regno
= reg_renumber
[regno
] /* + word */;
1315 /* Either this is one of the max_allocno pseudo regs not allocated,
1316 or it is or has a hardware reg. First handle the pseudo-regs. */
1317 if (regno
>= FIRST_PSEUDO_REGISTER
)
1319 if (reg_allocno
[regno
] >= 0)
1321 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1322 record_one_conflict (regno
);
1325 /* Handle hardware regs (and pseudos allocated to hard regs). */
1326 else if (! fixed_regs
[regno
])
1328 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1329 while (regno
< last
)
1331 record_one_conflict (regno
);
1332 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1338 /* Mark REG as being dead (following the insn being scanned now).
1339 Store a 0 in regs_live or allocnos_live for this register. */
1342 mark_reg_death (reg
)
1345 register int regno
= REGNO (reg
);
1347 /* For pseudo reg, see if it has been assigned a hardware reg. */
1348 if (reg_renumber
[regno
] >= 0)
1349 regno
= reg_renumber
[regno
];
1351 /* Either this is one of the max_allocno pseudo regs not allocated,
1352 or it is a hardware reg. First handle the pseudo-regs. */
1353 if (regno
>= FIRST_PSEUDO_REGISTER
)
1355 if (reg_allocno
[regno
] >= 0)
1356 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1358 /* Handle hardware regs (and pseudos allocated to hard regs). */
1359 else if (! fixed_regs
[regno
])
1361 /* Pseudo regs already assigned hardware regs are treated
1362 almost the same as explicit hardware regs. */
1363 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1364 while (regno
< last
)
1366 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1372 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1373 for the value stored in it. MODE determines how many consecutive
1374 registers are actually in use. Do not record conflicts;
1375 it is assumed that the caller will do that. */
1378 mark_reg_live_nc (regno
, mode
)
1380 enum machine_mode mode
;
1382 register int last
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1383 while (regno
< last
)
1385 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1390 /* Try to set a preference for an allocno to a hard register.
1391 We are passed DEST and SRC which are the operands of a SET. It is known
1392 that SRC is a register. If SRC or the first operand of SRC is a register,
1393 try to set a preference. If one of the two is a hard register and the other
1394 is a pseudo-register, mark the preference.
1396 Note that we are not as agressive as local-alloc in trying to tie a
1397 pseudo-register to a hard register. */
1400 set_preference (dest
, src
)
1403 int src_regno
, dest_regno
;
1404 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1405 to compensate for subregs in SRC or DEST. */
1410 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1411 src
= XEXP (src
, 0), copy
= 0;
1413 /* Get the reg number for both SRC and DEST.
1414 If neither is a reg, give up. */
1416 if (GET_CODE (src
) == REG
)
1417 src_regno
= REGNO (src
);
1418 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1420 src_regno
= REGNO (SUBREG_REG (src
));
1421 offset
+= SUBREG_WORD (src
);
1426 if (GET_CODE (dest
) == REG
)
1427 dest_regno
= REGNO (dest
);
1428 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1430 dest_regno
= REGNO (SUBREG_REG (dest
));
1431 offset
-= SUBREG_WORD (dest
);
1436 /* Convert either or both to hard reg numbers. */
1438 if (reg_renumber
[src_regno
] >= 0)
1439 src_regno
= reg_renumber
[src_regno
];
1441 if (reg_renumber
[dest_regno
] >= 0)
1442 dest_regno
= reg_renumber
[dest_regno
];
1444 /* Now if one is a hard reg and the other is a global pseudo
1445 then give the other a preference. */
1447 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1448 && reg_allocno
[src_regno
] >= 0)
1450 dest_regno
-= offset
;
1451 if (dest_regno
>= 0 && dest_regno
< FIRST_PSEUDO_REGISTER
)
1454 SET_REGBIT (hard_reg_copy_preferences
,
1455 reg_allocno
[src_regno
], dest_regno
);
1457 SET_REGBIT (hard_reg_preferences
,
1458 reg_allocno
[src_regno
], dest_regno
);
1459 for (i
= dest_regno
;
1460 i
< dest_regno
+ HARD_REGNO_NREGS (dest_regno
, GET_MODE (dest
));
1462 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1466 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1467 && reg_allocno
[dest_regno
] >= 0)
1469 src_regno
+= offset
;
1470 if (src_regno
>= 0 && src_regno
< FIRST_PSEUDO_REGISTER
)
1473 SET_REGBIT (hard_reg_copy_preferences
,
1474 reg_allocno
[dest_regno
], src_regno
);
1476 SET_REGBIT (hard_reg_preferences
,
1477 reg_allocno
[dest_regno
], src_regno
);
1479 i
< src_regno
+ HARD_REGNO_NREGS (src_regno
, GET_MODE (src
));
1481 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1486 /* Indicate that hard register number FROM was eliminated and replaced with
1487 an offset from hard register number TO. The status of hard registers live
1488 at the start of a basic block is updated by replacing a use of FROM with
1492 mark_elimination (from
, to
)
1497 for (i
= 0; i
< n_basic_blocks
; i
++)
1498 if ((basic_block_live_at_start
[i
][from
/ HOST_BITS_PER_INT
]
1499 & (1 << (from
% HOST_BITS_PER_INT
))) != 0)
1501 basic_block_live_at_start
[i
][from
/ HOST_BITS_PER_INT
]
1502 &= ~ (1 << (from
% HOST_BITS_PER_INT
));
1503 basic_block_live_at_start
[i
][to
/ HOST_BITS_PER_INT
]
1504 |= (1 << (to
% HOST_BITS_PER_INT
));
1508 /* Print debugging trace information if -greg switch is given,
1509 showing the information on which the allocation decisions are based. */
1512 dump_conflicts (file
)
1516 register int has_preferences
;
1517 fprintf (file
, ";; %d regs to allocate:", max_allocno
);
1518 for (i
= 0; i
< max_allocno
; i
++)
1521 fprintf (file
, " %d", allocno_reg
[allocno_order
[i
]]);
1522 for (j
= 0; j
< max_regno
; j
++)
1523 if (reg_allocno
[j
] == allocno_order
[i
]
1524 && j
!= allocno_reg
[allocno_order
[i
]])
1525 fprintf (file
, "+%d", j
);
1526 if (allocno_size
[allocno_order
[i
]] != 1)
1527 fprintf (file
, " (%d)", allocno_size
[allocno_order
[i
]]);
1529 fprintf (file
, "\n");
1531 for (i
= 0; i
< max_allocno
; i
++)
1534 fprintf (file
, ";; %d conflicts:", allocno_reg
[i
]);
1535 for (j
= 0; j
< max_allocno
; j
++)
1536 if (CONFLICTP (i
, j
) || CONFLICTP (j
, i
))
1537 fprintf (file
, " %d", allocno_reg
[j
]);
1538 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1539 if (TEST_HARD_REG_BIT (hard_reg_conflicts
[i
], j
))
1540 fprintf (file
, " %d", j
);
1541 fprintf (file
, "\n");
1543 has_preferences
= 0;
1544 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1545 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1546 has_preferences
= 1;
1548 if (! has_preferences
)
1550 fprintf (file
, ";; %d preferences:", allocno_reg
[i
]);
1551 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1552 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1553 fprintf (file
, " %d", j
);
1554 fprintf (file
, "\n");
1556 fprintf (file
, "\n");
1560 dump_global_regs (file
)
1565 fprintf (file
, ";; Register dispositions:\n");
1566 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1567 if (reg_renumber
[i
] >= 0)
1569 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1571 fprintf (file
, "\n");
1574 fprintf (file
, "\n\n;; Hard regs used: ");
1575 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1576 if (regs_ever_live
[i
])
1577 fprintf (file
, " %d", i
);
1578 fprintf (file
, "\n\n");