1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 88, 91, 94, 96, 1997 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
27 #include "basic-block.h"
28 #include "hard-reg-set.h"
30 #include "insn-config.h"
33 /* This pass of the compiler performs global register allocation.
34 It assigns hard register numbers to all the pseudo registers
35 that were not handled in local_alloc. Assignments are recorded
36 in the vector reg_renumber, not by changing the rtl code.
37 (Such changes are made by final). The entry point is
38 the function global_alloc.
40 After allocation is complete, the reload pass is run as a subroutine
41 of this pass, so that when a pseudo reg loses its hard reg due to
42 spilling it is possible to make a second attempt to find a hard
43 reg for it. The reload pass is independent in other respects
44 and it is run even when stupid register allocation is in use.
46 1. count the pseudo-registers still needing allocation
47 and assign allocation-numbers (allocnos) to them.
48 Set up tables reg_allocno and allocno_reg to map
49 reg numbers to allocnos and vice versa.
50 max_allocno gets the number of allocnos in use.
52 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
53 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
54 for conflicts between allocnos and explicit hard register use
55 (which includes use of pseudo-registers allocated by local_alloc).
57 3. for each basic block
58 walk forward through the block, recording which
59 unallocated registers and which hardware registers are live.
60 Build the conflict matrix between the unallocated registers
61 and another of unallocated registers versus hardware registers.
62 Also record the preferred hardware registers
63 for each unallocated one.
65 4. Sort a table of the allocnos into order of
66 desirability of the variables.
68 5. Allocate the variables in that order; each if possible into
69 a preferred register, else into another register. */
71 /* Number of pseudo-registers still requiring allocation
72 (not allocated by local_allocate). */
74 static int max_allocno
;
76 /* Indexed by (pseudo) reg number, gives the allocno, or -1
77 for pseudo registers already allocated by local_allocate. */
81 /* Indexed by allocno, gives the reg number. */
83 static int *allocno_reg
;
85 /* A vector of the integers from 0 to max_allocno-1,
86 sorted in the order of first-to-be-allocated first. */
88 static int *allocno_order
;
90 /* Indexed by an allocno, gives the number of consecutive
91 hard registers needed by that pseudo reg. */
93 static int *allocno_size
;
95 /* Indexed by (pseudo) reg number, gives the number of another
96 lower-numbered pseudo reg which can share a hard reg with this pseudo
97 *even if the two pseudos would otherwise appear to conflict*. */
99 static int *reg_may_share
;
101 /* Define the number of bits in each element of `conflicts' and what
102 type that element has. We use the largest integer format on the
105 #define INT_BITS HOST_BITS_PER_WIDE_INT
106 #define INT_TYPE HOST_WIDE_INT
108 /* max_allocno by max_allocno array of bits,
109 recording whether two allocno's conflict (can't go in the same
112 `conflicts' is not symmetric; a conflict between allocno's i and j
113 is recorded either in element i,j or in element j,i. */
115 static INT_TYPE
*conflicts
;
117 /* Number of ints require to hold max_allocno bits.
118 This is the length of a row in `conflicts'. */
120 static int allocno_row_words
;
122 /* Two macros to test or store 1 in an element of `conflicts'. */
124 #define CONFLICTP(I, J) \
125 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
126 & ((INT_TYPE) 1 << ((J) % INT_BITS)))
128 #define SET_CONFLICT(I, J) \
129 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
130 |= ((INT_TYPE) 1 << ((J) % INT_BITS)))
132 /* Set of hard regs currently live (during scan of all insns). */
134 static HARD_REG_SET hard_regs_live
;
136 /* Indexed by N, set of hard regs conflicting with allocno N. */
138 static HARD_REG_SET
*hard_reg_conflicts
;
140 /* Indexed by N, set of hard regs preferred by allocno N.
141 This is used to make allocnos go into regs that are copied to or from them,
142 when possible, to reduce register shuffling. */
144 static HARD_REG_SET
*hard_reg_preferences
;
146 /* Similar, but just counts register preferences made in simple copy
147 operations, rather than arithmetic. These are given priority because
148 we can always eliminate an insn by using these, but using a register
149 in the above list won't always eliminate an insn. */
151 static HARD_REG_SET
*hard_reg_copy_preferences
;
153 /* Similar to hard_reg_preferences, but includes bits for subsequent
154 registers when an allocno is multi-word. The above variable is used for
155 allocation while this is used to build reg_someone_prefers, below. */
157 static HARD_REG_SET
*hard_reg_full_preferences
;
159 /* Indexed by N, set of hard registers that some later allocno has a
162 static HARD_REG_SET
*regs_someone_prefers
;
164 /* Set of registers that global-alloc isn't supposed to use. */
166 static HARD_REG_SET no_global_alloc_regs
;
168 /* Set of registers used so far. */
170 static HARD_REG_SET regs_used_so_far
;
172 /* Number of calls crossed by each allocno. */
174 static int *allocno_calls_crossed
;
176 /* Number of refs (weighted) to each allocno. */
178 static int *allocno_n_refs
;
180 /* Guess at live length of each allocno.
181 This is actually the max of the live lengths of the regs. */
183 static int *allocno_live_length
;
185 /* Number of refs (weighted) to each hard reg, as used by local alloc.
186 It is zero for a reg that contains global pseudos or is explicitly used. */
188 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
190 /* Guess at live length of each hard reg, as used by local alloc.
191 This is actually the sum of the live lengths of the specific regs. */
193 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
195 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
196 for vector element I, and hard register number J. */
198 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
200 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
202 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
204 /* Bit mask for allocnos live at current point in the scan. */
206 static INT_TYPE
*allocnos_live
;
208 /* Test, set or clear bit number I in allocnos_live,
209 a bit vector indexed by allocno. */
211 #define ALLOCNO_LIVE_P(I) \
212 (allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS)))
214 #define SET_ALLOCNO_LIVE(I) \
215 (allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS)))
217 #define CLEAR_ALLOCNO_LIVE(I) \
218 (allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((I) % INT_BITS)))
220 /* This is turned off because it doesn't work right for DImode.
221 (And it is only used for DImode, so the other cases are worthless.)
222 The problem is that it isn't true that there is NO possibility of conflict;
223 only that there is no conflict if the two pseudos get the exact same regs.
224 If they were allocated with a partial overlap, there would be a conflict.
225 We can't safely turn off the conflict unless we have another way to
226 prevent the partial overlap.
228 Idea: change hard_reg_conflicts so that instead of recording which
229 hard regs the allocno may not overlap, it records where the allocno
230 may not start. Change both where it is used and where it is updated.
231 Then there is a way to record that (reg:DI 108) may start at 10
232 but not at 9 or 11. There is still the question of how to record
233 this semi-conflict between two pseudos. */
235 /* Reg pairs for which conflict after the current insn
236 is inhibited by a REG_NO_CONFLICT note.
237 If the table gets full, we ignore any other notes--that is conservative. */
238 #define NUM_NO_CONFLICT_PAIRS 4
239 /* Number of pairs in use in this insn. */
240 int n_no_conflict_pairs
;
241 static struct { int allocno1
, allocno2
;}
242 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
245 /* Record all regs that are set in any one insn.
246 Communication from mark_reg_{store,clobber} and global_conflicts. */
248 static rtx
*regs_set
;
249 static int n_regs_set
;
251 /* All registers that can be eliminated. */
253 static HARD_REG_SET eliminable_regset
;
255 static int allocno_compare
PROTO((const GENERIC_PTR
, const GENERIC_PTR
));
256 static void global_conflicts
PROTO((void));
257 static void expand_preferences
PROTO((void));
258 static void prune_preferences
PROTO((void));
259 static void find_reg
PROTO((int, HARD_REG_SET
, int, int, int));
260 static void record_one_conflict
PROTO((int));
261 static void record_conflicts
PROTO((short *, int));
262 static void mark_reg_store
PROTO((rtx
, rtx
));
263 static void mark_reg_clobber
PROTO((rtx
, rtx
));
264 static void mark_reg_conflicts
PROTO((rtx
));
265 static void mark_reg_death
PROTO((rtx
));
266 static void mark_reg_live_nc
PROTO((int, enum machine_mode
));
267 static void set_preference
PROTO((rtx
, rtx
));
268 static void dump_conflicts
PROTO((FILE *));
270 /* Perform allocation of pseudo-registers not allocated by local_alloc.
271 FILE is a file to output debugging information on,
272 or zero if such output is not desired.
274 Return value is nonzero if reload failed
275 and we must not do any more for this function. */
282 #ifdef ELIMINABLE_REGS
283 static struct {int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
286 = (! flag_omit_frame_pointer
287 #ifdef EXIT_IGNORE_STACK
288 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
290 || FRAME_POINTER_REQUIRED
);
297 /* A machine may have certain hard registers that
298 are safe to use only within a basic block. */
300 CLEAR_HARD_REG_SET (no_global_alloc_regs
);
301 #ifdef OVERLAPPING_REGNO_P
302 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
303 if (OVERLAPPING_REGNO_P (i
))
304 SET_HARD_REG_BIT (no_global_alloc_regs
, i
);
307 /* Build the regset of all eliminable registers and show we can't use those
308 that we already know won't be eliminated. */
309 #ifdef ELIMINABLE_REGS
310 for (i
= 0; i
< sizeof eliminables
/ sizeof eliminables
[0]; i
++)
312 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
314 if (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
315 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
))
316 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
318 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
319 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
321 SET_HARD_REG_BIT (no_global_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
325 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
327 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
330 /* Track which registers have already been used. Start with registers
331 explicitly in the rtl, then registers allocated by local register
334 CLEAR_HARD_REG_SET (regs_used_so_far
);
335 #ifdef LEAF_REGISTERS
336 /* If we are doing the leaf function optimization, and this is a leaf
337 function, it means that the registers that take work to save are those
338 that need a register window. So prefer the ones that can be used in
342 static char leaf_regs
[] = LEAF_REGISTERS
;
344 if (only_leaf_regs_used () && leaf_function_p ())
345 cheap_regs
= leaf_regs
;
347 cheap_regs
= call_used_regs
;
348 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
349 if (regs_ever_live
[i
] || cheap_regs
[i
])
350 SET_HARD_REG_BIT (regs_used_so_far
, i
);
353 /* We consider registers that do not have to be saved over calls as if
354 they were already used since there is no cost in using them. */
355 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
356 if (regs_ever_live
[i
] || call_used_regs
[i
])
357 SET_HARD_REG_BIT (regs_used_so_far
, i
);
360 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
361 if (reg_renumber
[i
] >= 0)
362 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
364 /* Establish mappings from register number to allocation number
365 and vice versa. In the process, count the allocnos. */
367 reg_allocno
= (int *) alloca (max_regno
* sizeof (int));
369 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
372 /* Initialize the shared-hard-reg mapping
373 from the list of pairs that may share. */
374 reg_may_share
= (int *) alloca (max_regno
* sizeof (int));
375 bzero ((char *) reg_may_share
, max_regno
* sizeof (int));
376 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
378 int r1
= REGNO (XEXP (x
, 0));
379 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
381 reg_may_share
[r1
] = r2
;
383 reg_may_share
[r2
] = r1
;
386 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
387 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
388 that we are supposed to refrain from putting in a hard reg.
389 -2 means do make an allocno but don't allocate it. */
390 if (REG_N_REFS (i
) != 0 && reg_renumber
[i
] < 0 && REG_LIVE_LENGTH (i
) != -1
391 /* Don't allocate pseudos that cross calls,
392 if this function receives a nonlocal goto. */
393 && (! current_function_has_nonlocal_label
394 || REG_N_CALLS_CROSSED (i
) == 0))
396 if (reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
397 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
399 reg_allocno
[i
] = max_allocno
++;
400 if (REG_LIVE_LENGTH (i
) == 0)
406 allocno_reg
= (int *) alloca (max_allocno
* sizeof (int));
407 allocno_size
= (int *) alloca (max_allocno
* sizeof (int));
408 allocno_calls_crossed
= (int *) alloca (max_allocno
* sizeof (int));
409 allocno_n_refs
= (int *) alloca (max_allocno
* sizeof (int));
410 allocno_live_length
= (int *) alloca (max_allocno
* sizeof (int));
411 bzero ((char *) allocno_size
, max_allocno
* sizeof (int));
412 bzero ((char *) allocno_calls_crossed
, max_allocno
* sizeof (int));
413 bzero ((char *) allocno_n_refs
, max_allocno
* sizeof (int));
414 bzero ((char *) allocno_live_length
, max_allocno
* sizeof (int));
416 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
417 if (reg_allocno
[i
] >= 0)
419 int allocno
= reg_allocno
[i
];
420 allocno_reg
[allocno
] = i
;
421 allocno_size
[allocno
] = PSEUDO_REGNO_SIZE (i
);
422 allocno_calls_crossed
[allocno
] += REG_N_CALLS_CROSSED (i
);
423 allocno_n_refs
[allocno
] += REG_N_REFS (i
);
424 if (allocno_live_length
[allocno
] < REG_LIVE_LENGTH (i
))
425 allocno_live_length
[allocno
] = REG_LIVE_LENGTH (i
);
428 /* Calculate amount of usage of each hard reg by pseudos
429 allocated by local-alloc. This is to see if we want to
431 bzero ((char *) local_reg_live_length
, sizeof local_reg_live_length
);
432 bzero ((char *) local_reg_n_refs
, sizeof local_reg_n_refs
);
433 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
434 if (reg_allocno
[i
] < 0 && reg_renumber
[i
] >= 0)
436 int regno
= reg_renumber
[i
];
437 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (i
));
440 for (j
= regno
; j
< endregno
; j
++)
442 local_reg_n_refs
[j
] += REG_N_REFS (i
);
443 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
447 /* We can't override local-alloc for a reg used not just by local-alloc. */
448 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
449 if (regs_ever_live
[i
])
450 local_reg_n_refs
[i
] = 0;
452 /* Likewise for regs used in a SCRATCH. */
453 for (i
= 0; i
< scratch_list_length
; i
++)
456 int regno
= REGNO (scratch_list
[i
]);
457 int lim
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (scratch_list
[i
]));
460 for (j
= regno
; j
< lim
; j
++)
461 local_reg_n_refs
[j
] = 0;
464 /* Allocate the space for the conflict and preference tables and
468 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
469 bzero ((char *) hard_reg_conflicts
, max_allocno
* sizeof (HARD_REG_SET
));
472 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
473 bzero ((char *) hard_reg_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
475 hard_reg_copy_preferences
476 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
477 bzero ((char *) hard_reg_copy_preferences
,
478 max_allocno
* sizeof (HARD_REG_SET
));
480 hard_reg_full_preferences
481 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
482 bzero ((char *) hard_reg_full_preferences
,
483 max_allocno
* sizeof (HARD_REG_SET
));
486 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
487 bzero ((char *) regs_someone_prefers
, max_allocno
* sizeof (HARD_REG_SET
));
489 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
491 /* We used to use alloca here, but the size of what it would try to
492 allocate would occasionally cause it to exceed the stack limit and
493 cause unpredictable core dumps. Some examples were > 2Mb in size. */
494 conflicts
= (INT_TYPE
*) xmalloc (max_allocno
* allocno_row_words
495 * sizeof (INT_TYPE
));
496 bzero ((char *) conflicts
,
497 max_allocno
* allocno_row_words
* sizeof (INT_TYPE
));
499 allocnos_live
= (INT_TYPE
*) alloca (allocno_row_words
* sizeof (INT_TYPE
));
501 /* If there is work to be done (at least one reg to allocate),
502 perform global conflict analysis and allocate the regs. */
506 /* Scan all the insns and compute the conflicts among allocnos
507 and between allocnos and hard regs. */
511 /* Eliminate conflicts between pseudos and eliminable registers. If
512 the register is not eliminated, the pseudo won't really be able to
513 live in the eliminable register, so the conflict doesn't matter.
514 If we do eliminate the register, the conflict will no longer exist.
515 So in either case, we can ignore the conflict. Likewise for
518 for (i
= 0; i
< max_allocno
; i
++)
520 AND_COMPL_HARD_REG_SET (hard_reg_conflicts
[i
], eliminable_regset
);
521 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[i
],
523 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[i
], eliminable_regset
);
526 /* Try to expand the preferences by merging them between allocnos. */
528 expand_preferences ();
530 /* Determine the order to allocate the remaining pseudo registers. */
532 allocno_order
= (int *) alloca (max_allocno
* sizeof (int));
533 for (i
= 0; i
< max_allocno
; i
++)
534 allocno_order
[i
] = i
;
536 /* Default the size to 1, since allocno_compare uses it to divide by.
537 Also convert allocno_live_length of zero to -1. A length of zero
538 can occur when all the registers for that allocno have reg_live_length
539 equal to -2. In this case, we want to make an allocno, but not
540 allocate it. So avoid the divide-by-zero and set it to a low
543 for (i
= 0; i
< max_allocno
; i
++)
545 if (allocno_size
[i
] == 0)
547 if (allocno_live_length
[i
] == 0)
548 allocno_live_length
[i
] = -1;
551 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
553 prune_preferences ();
556 dump_conflicts (file
);
558 /* Try allocating them, one by one, in that order,
559 except for parameters marked with reg_live_length[regno] == -2. */
561 for (i
= 0; i
< max_allocno
; i
++)
562 if (REG_LIVE_LENGTH (allocno_reg
[allocno_order
[i
]]) >= 0)
564 /* If we have more than one register class,
565 first try allocating in the class that is cheapest
566 for this pseudo-reg. If that fails, try any reg. */
567 if (N_REG_CLASSES
> 1)
569 find_reg (allocno_order
[i
], HARD_CONST (0), 0, 0, 0);
570 if (reg_renumber
[allocno_reg
[allocno_order
[i
]]] >= 0)
573 if (reg_alternate_class (allocno_reg
[allocno_order
[i
]]) != NO_REGS
)
574 find_reg (allocno_order
[i
], HARD_CONST (0), 1, 0, 0);
578 /* Do the reloads now while the allocno data still exist, so that we can
579 try to assign new hard regs to any pseudo regs that are spilled. */
581 #if 0 /* We need to eliminate regs even if there is no rtl code,
582 for the sake of debugging information. */
583 if (n_basic_blocks
> 0)
585 retval
= reload (get_insns (), 1, file
);
591 /* Sort predicate for ordering the allocnos.
592 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
595 allocno_compare (v1p
, v2p
)
596 const GENERIC_PTR v1p
;
597 const GENERIC_PTR v2p
;
599 int v1
= *(int *)v1p
, v2
= *(int *)v2p
;
600 /* Note that the quotient will never be bigger than
601 the value of floor_log2 times the maximum number of
602 times a register can occur in one insn (surely less than 100).
603 Multiplying this by 10000 can't overflow. */
605 = (((double) (floor_log2 (allocno_n_refs
[v1
]) * allocno_n_refs
[v1
])
606 / allocno_live_length
[v1
])
607 * 10000 * allocno_size
[v1
]);
609 = (((double) (floor_log2 (allocno_n_refs
[v2
]) * allocno_n_refs
[v2
])
610 / allocno_live_length
[v2
])
611 * 10000 * allocno_size
[v2
]);
615 /* If regs are equally good, sort by allocno,
616 so that the results of qsort leave nothing to chance. */
620 /* Scan the rtl code and record all conflicts and register preferences in the
621 conflict matrices and preference tables. */
628 short *block_start_allocnos
;
630 /* Make a vector that mark_reg_{store,clobber} will store in. */
631 regs_set
= (rtx
*) alloca (max_parallel
* sizeof (rtx
) * 2);
633 block_start_allocnos
= (short *) alloca (max_allocno
* sizeof (short));
635 for (b
= 0; b
< n_basic_blocks
; b
++)
637 bzero ((char *) allocnos_live
, allocno_row_words
* sizeof (INT_TYPE
));
639 /* Initialize table of registers currently live
640 to the state at the beginning of this basic block.
641 This also marks the conflicts among them.
643 For pseudo-regs, there is only one bit for each one
644 no matter how many hard regs it occupies.
645 This is ok; we know the size from PSEUDO_REGNO_SIZE.
646 For explicit hard regs, we cannot know the size that way
647 since one hard reg can be used with various sizes.
648 Therefore, we must require that all the hard regs
649 implicitly live as part of a multi-word hard reg
650 are explicitly marked in basic_block_live_at_start. */
653 register regset old
= basic_block_live_at_start
[b
];
656 REG_SET_TO_HARD_REG_SET (hard_regs_live
, old
);
657 EXECUTE_IF_SET_IN_REG_SET (old
, FIRST_PSEUDO_REGISTER
, i
,
659 register int a
= reg_allocno
[i
];
662 SET_ALLOCNO_LIVE (a
);
663 block_start_allocnos
[ax
++] = a
;
665 else if ((a
= reg_renumber
[i
]) >= 0)
667 (a
, PSEUDO_REGNO_MODE (i
));
670 /* Record that each allocno now live conflicts with each other
671 allocno now live, and with each hard reg now live. */
673 record_conflicts (block_start_allocnos
, ax
);
676 insn
= basic_block_head
[b
];
678 /* Scan the code of this basic block, noting which allocnos
679 and hard regs are born or die. When one is born,
680 record a conflict with all others currently live. */
684 register RTX_CODE code
= GET_CODE (insn
);
687 /* Make regs_set an empty set. */
691 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
696 for (link
= REG_NOTES (insn
);
697 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
698 link
= XEXP (link
, 1))
699 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
701 no_conflict_pairs
[i
].allocno1
702 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
703 no_conflict_pairs
[i
].allocno2
704 = reg_allocno
[REGNO (XEXP (link
, 0))];
709 /* Mark any registers clobbered by INSN as live,
710 so they conflict with the inputs. */
712 note_stores (PATTERN (insn
), mark_reg_clobber
);
714 /* Mark any registers dead after INSN as dead now. */
716 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
717 if (REG_NOTE_KIND (link
) == REG_DEAD
)
718 mark_reg_death (XEXP (link
, 0));
720 /* Mark any registers set in INSN as live,
721 and mark them as conflicting with all other live regs.
722 Clobbers are processed again, so they conflict with
723 the registers that are set. */
725 note_stores (PATTERN (insn
), mark_reg_store
);
728 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
729 if (REG_NOTE_KIND (link
) == REG_INC
)
730 mark_reg_store (XEXP (link
, 0), NULL_RTX
);
733 /* If INSN has multiple outputs, then any reg that dies here
734 and is used inside of an output
735 must conflict with the other outputs. */
737 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& !single_set (insn
))
738 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
739 if (REG_NOTE_KIND (link
) == REG_DEAD
)
741 int used_in_output
= 0;
743 rtx reg
= XEXP (link
, 0);
745 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
747 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
748 if (GET_CODE (set
) == SET
749 && GET_CODE (SET_DEST (set
)) != REG
750 && !rtx_equal_p (reg
, SET_DEST (set
))
751 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
755 mark_reg_conflicts (reg
);
758 /* Mark any registers set in INSN and then never used. */
760 while (n_regs_set
> 0)
761 if (find_regno_note (insn
, REG_UNUSED
,
762 REGNO (regs_set
[--n_regs_set
])))
763 mark_reg_death (regs_set
[n_regs_set
]);
766 if (insn
== basic_block_end
[b
])
768 insn
= NEXT_INSN (insn
);
772 /* Expand the preference information by looking for cases where one allocno
773 dies in an insn that sets an allocno. If those two allocnos don't conflict,
774 merge any preferences between those allocnos. */
777 expand_preferences ()
783 /* We only try to handle the most common cases here. Most of the cases
784 where this wins are reg-reg copies. */
786 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
787 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
788 && (set
= single_set (insn
)) != 0
789 && GET_CODE (SET_DEST (set
)) == REG
790 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
791 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
792 if (REG_NOTE_KIND (link
) == REG_DEAD
793 && GET_CODE (XEXP (link
, 0)) == REG
794 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
795 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
796 reg_allocno
[REGNO (XEXP (link
, 0))])
797 && ! CONFLICTP (reg_allocno
[REGNO (XEXP (link
, 0))],
798 reg_allocno
[REGNO (SET_DEST (set
))]))
800 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
801 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
803 if (XEXP (link
, 0) == SET_SRC (set
))
805 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a1
],
806 hard_reg_copy_preferences
[a2
]);
807 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a2
],
808 hard_reg_copy_preferences
[a1
]);
811 IOR_HARD_REG_SET (hard_reg_preferences
[a1
],
812 hard_reg_preferences
[a2
]);
813 IOR_HARD_REG_SET (hard_reg_preferences
[a2
],
814 hard_reg_preferences
[a1
]);
815 IOR_HARD_REG_SET (hard_reg_full_preferences
[a1
],
816 hard_reg_full_preferences
[a2
]);
817 IOR_HARD_REG_SET (hard_reg_full_preferences
[a2
],
818 hard_reg_full_preferences
[a1
]);
822 /* Prune the preferences for global registers to exclude registers that cannot
825 Compute `regs_someone_prefers', which is a bitmask of the hard registers
826 that are preferred by conflicting registers of lower priority. If possible,
827 we will avoid using these registers. */
835 /* Scan least most important to most important.
836 For each allocno, remove from preferences registers that cannot be used,
837 either because of conflicts or register type. Then compute all registers
838 preferred by each lower-priority register that conflicts. */
840 for (i
= max_allocno
- 1; i
>= 0; i
--)
844 allocno
= allocno_order
[i
];
845 COPY_HARD_REG_SET (temp
, hard_reg_conflicts
[allocno
]);
847 if (allocno_calls_crossed
[allocno
] == 0)
848 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
850 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
852 IOR_COMPL_HARD_REG_SET
854 reg_class_contents
[(int) reg_preferred_class (allocno_reg
[allocno
])]);
856 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], temp
);
857 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], temp
);
858 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences
[allocno
], temp
);
860 CLEAR_HARD_REG_SET (regs_someone_prefers
[allocno
]);
862 /* Merge in the preferences of lower-priority registers (they have
863 already been pruned). If we also prefer some of those registers,
864 don't exclude them unless we are of a smaller size (in which case
865 we want to give the lower-priority allocno the first chance for
867 for (j
= i
+ 1; j
< max_allocno
; j
++)
868 if (CONFLICTP (allocno
, allocno_order
[j
])
869 || CONFLICTP (allocno_order
[j
], allocno
))
871 COPY_HARD_REG_SET (temp
,
872 hard_reg_full_preferences
[allocno_order
[j
]]);
873 if (allocno_size
[allocno_order
[j
]] <= allocno_size
[allocno
])
874 AND_COMPL_HARD_REG_SET (temp
,
875 hard_reg_full_preferences
[allocno
]);
877 IOR_HARD_REG_SET (regs_someone_prefers
[allocno
], temp
);
882 /* Assign a hard register to ALLOCNO; look for one that is the beginning
883 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
884 The registers marked in PREFREGS are tried first.
886 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
887 be used for this allocation.
889 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
890 Otherwise ignore that preferred class and use the alternate class.
892 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
893 will have to be saved and restored at calls.
895 RETRYING is nonzero if this is called from retry_global_alloc.
897 If we find one, record it in reg_renumber.
898 If not, do nothing. */
901 find_reg (allocno
, losers
, alt_regs_p
, accept_call_clobbered
, retrying
)
905 int accept_call_clobbered
;
908 register int i
, best_reg
, pass
;
910 register /* Declare it register if it's a scalar. */
912 HARD_REG_SET used
, used1
, used2
;
914 enum reg_class
class = (alt_regs_p
915 ? reg_alternate_class (allocno_reg
[allocno
])
916 : reg_preferred_class (allocno_reg
[allocno
]));
917 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno_reg
[allocno
]);
919 if (accept_call_clobbered
)
920 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
921 else if (allocno_calls_crossed
[allocno
] == 0)
922 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
924 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
926 /* Some registers should not be allocated in global-alloc. */
927 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
929 IOR_HARD_REG_SET (used1
, losers
);
931 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
932 COPY_HARD_REG_SET (used2
, used1
);
934 IOR_HARD_REG_SET (used1
, hard_reg_conflicts
[allocno
]);
936 #ifdef CLASS_CANNOT_CHANGE_SIZE
937 if (REG_CHANGES_SIZE (allocno_reg
[allocno
]))
938 IOR_HARD_REG_SET (used1
,
939 reg_class_contents
[(int) CLASS_CANNOT_CHANGE_SIZE
]);
942 /* Try each hard reg to see if it fits. Do this in two passes.
943 In the first pass, skip registers that are preferred by some other pseudo
944 to give it a better chance of getting one of those registers. Only if
945 we can't get a register when excluding those do we take one of them.
946 However, we never allocate a register for the first time in pass 0. */
948 COPY_HARD_REG_SET (used
, used1
);
949 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
950 IOR_HARD_REG_SET (used
, regs_someone_prefers
[allocno
]);
953 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
954 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
958 COPY_HARD_REG_SET (used
, used1
);
959 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
961 #ifdef REG_ALLOC_ORDER
962 int regno
= reg_alloc_order
[i
];
966 if (! TEST_HARD_REG_BIT (used
, regno
)
967 && HARD_REGNO_MODE_OK (regno
, mode
))
970 register int lim
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
973 && ! TEST_HARD_REG_BIT (used
, j
));
980 #ifndef REG_ALLOC_ORDER
981 i
= j
; /* Skip starting points we know will lose */
987 /* See if there is a preferred register with the same class as the register
988 we allocated above. Making this restriction prevents register
989 preferencing from creating worse register allocation.
991 Remove from the preferred registers and conflicting registers. Note that
992 additional conflicts may have been added after `prune_preferences' was
995 First do this for those register with copy preferences, then all
996 preferred registers. */
998 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], used
);
999 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences
[allocno
],
1000 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
1004 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1005 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences
[allocno
], i
)
1006 && HARD_REGNO_MODE_OK (i
, mode
)
1007 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1008 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1009 REGNO_REG_CLASS (best_reg
))
1010 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1011 REGNO_REG_CLASS (i
))))
1014 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1017 && ! TEST_HARD_REG_BIT (used
, j
)
1018 && (REGNO_REG_CLASS (j
)
1019 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1020 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1021 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1022 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1023 REGNO_REG_CLASS (j
))));
1034 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], used
);
1035 GO_IF_HARD_REG_SUBSET (hard_reg_preferences
[allocno
],
1036 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1040 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1041 if (TEST_HARD_REG_BIT (hard_reg_preferences
[allocno
], i
)
1042 && HARD_REGNO_MODE_OK (i
, mode
)
1043 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1044 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1045 REGNO_REG_CLASS (best_reg
))
1046 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1047 REGNO_REG_CLASS (i
))))
1050 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1053 && ! TEST_HARD_REG_BIT (used
, j
)
1054 && (REGNO_REG_CLASS (j
)
1055 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1056 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1057 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1058 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1059 REGNO_REG_CLASS (j
))));
1070 /* If we haven't succeeded yet, try with caller-saves.
1071 We need not check to see if the current function has nonlocal
1072 labels because we don't put any pseudos that are live over calls in
1073 registers in that case. */
1075 if (flag_caller_saves
&& best_reg
< 0)
1077 /* Did not find a register. If it would be profitable to
1078 allocate a call-clobbered register and save and restore it
1079 around calls, do that. */
1080 if (! accept_call_clobbered
1081 && allocno_calls_crossed
[allocno
] != 0
1082 && CALLER_SAVE_PROFITABLE (allocno_n_refs
[allocno
],
1083 allocno_calls_crossed
[allocno
]))
1085 HARD_REG_SET new_losers
;
1087 CLEAR_HARD_REG_SET (new_losers
);
1089 COPY_HARD_REG_SET (new_losers
, losers
);
1091 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1092 find_reg (allocno
, new_losers
, alt_regs_p
, 1, retrying
);
1093 if (reg_renumber
[allocno_reg
[allocno
]] >= 0)
1095 caller_save_needed
= 1;
1101 /* If we haven't succeeded yet,
1102 see if some hard reg that conflicts with us
1103 was utilized poorly by local-alloc.
1104 If so, kick out the regs that were put there by local-alloc
1105 so we can use it instead. */
1106 if (best_reg
< 0 && !retrying
1107 /* Let's not bother with multi-reg allocnos. */
1108 && allocno_size
[allocno
] == 1)
1110 /* Count from the end, to find the least-used ones first. */
1111 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1113 #ifdef REG_ALLOC_ORDER
1114 int regno
= reg_alloc_order
[i
];
1119 if (local_reg_n_refs
[regno
] != 0
1120 /* Don't use a reg no good for this pseudo. */
1121 && ! TEST_HARD_REG_BIT (used2
, regno
)
1122 && HARD_REGNO_MODE_OK (regno
, mode
)
1123 #ifdef CLASS_CANNOT_CHANGE_SIZE
1124 && ! (REG_CHANGES_SIZE (allocno_reg
[allocno
])
1125 && (TEST_HARD_REG_BIT
1126 (reg_class_contents
[(int) CLASS_CANNOT_CHANGE_SIZE
],
1131 /* We explicitly evaluate the divide results into temporary
1132 variables so as to avoid excess precision problems that occur
1133 on a i386-unknown-sysv4.2 (unixware) host. */
1135 double tmp1
= ((double) local_reg_n_refs
[regno
]
1136 / local_reg_live_length
[regno
]);
1137 double tmp2
= ((double) allocno_n_refs
[allocno
]
1138 / allocno_live_length
[allocno
]);
1142 /* Hard reg REGNO was used less in total by local regs
1143 than it would be used by this one allocno! */
1145 for (k
= 0; k
< max_regno
; k
++)
1146 if (reg_renumber
[k
] >= 0)
1148 int r
= reg_renumber
[k
];
1150 = r
+ HARD_REGNO_NREGS (r
, PSEUDO_REGNO_MODE (k
));
1152 if (regno
>= r
&& regno
< endregno
)
1153 reg_renumber
[k
] = -1;
1163 /* Did we find a register? */
1167 register int lim
, j
;
1168 HARD_REG_SET this_reg
;
1170 /* Yes. Record it as the hard register of this pseudo-reg. */
1171 reg_renumber
[allocno_reg
[allocno
]] = best_reg
;
1172 /* Also of any pseudo-regs that share with it. */
1173 if (reg_may_share
[allocno_reg
[allocno
]])
1174 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1175 if (reg_allocno
[j
] == allocno
)
1176 reg_renumber
[j
] = best_reg
;
1178 /* Make a set of the hard regs being allocated. */
1179 CLEAR_HARD_REG_SET (this_reg
);
1180 lim
= best_reg
+ HARD_REGNO_NREGS (best_reg
, mode
);
1181 for (j
= best_reg
; j
< lim
; j
++)
1183 SET_HARD_REG_BIT (this_reg
, j
);
1184 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1185 /* This is no longer a reg used just by local regs. */
1186 local_reg_n_refs
[j
] = 0;
1188 /* For each other pseudo-reg conflicting with this one,
1189 mark it as conflicting with the hard regs this one occupies. */
1191 for (j
= 0; j
< max_allocno
; j
++)
1192 if (CONFLICTP (lim
, j
) || CONFLICTP (j
, lim
))
1194 IOR_HARD_REG_SET (hard_reg_conflicts
[j
], this_reg
);
1199 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1200 Perhaps it had previously seemed not worth a hard reg,
1201 or perhaps its old hard reg has been commandeered for reloads.
1202 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1203 they do not appear to be allocated.
1204 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1207 retry_global_alloc (regno
, forbidden_regs
)
1209 HARD_REG_SET forbidden_regs
;
1211 int allocno
= reg_allocno
[regno
];
1214 /* If we have more than one register class,
1215 first try allocating in the class that is cheapest
1216 for this pseudo-reg. If that fails, try any reg. */
1217 if (N_REG_CLASSES
> 1)
1218 find_reg (allocno
, forbidden_regs
, 0, 0, 1);
1219 if (reg_renumber
[regno
] < 0
1220 && reg_alternate_class (regno
) != NO_REGS
)
1221 find_reg (allocno
, forbidden_regs
, 1, 0, 1);
1223 /* If we found a register, modify the RTL for the register to
1224 show the hard register, and mark that register live. */
1225 if (reg_renumber
[regno
] >= 0)
1227 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1228 mark_home_live (regno
);
1233 /* Record a conflict between register REGNO
1234 and everything currently live.
1235 REGNO must not be a pseudo reg that was allocated
1236 by local_alloc; such numbers must be translated through
1237 reg_renumber before calling here. */
1240 record_one_conflict (regno
)
1245 if (regno
< FIRST_PSEUDO_REGISTER
)
1246 /* When a hard register becomes live,
1247 record conflicts with live pseudo regs. */
1248 for (j
= 0; j
< max_allocno
; j
++)
1250 if (ALLOCNO_LIVE_P (j
))
1251 SET_HARD_REG_BIT (hard_reg_conflicts
[j
], regno
);
1254 /* When a pseudo-register becomes live,
1255 record conflicts first with hard regs,
1256 then with other pseudo regs. */
1258 register int ialloc
= reg_allocno
[regno
];
1259 register int ialloc_prod
= ialloc
* allocno_row_words
;
1260 IOR_HARD_REG_SET (hard_reg_conflicts
[ialloc
], hard_regs_live
);
1261 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1265 for (k
= 0; k
< n_no_conflict_pairs
; k
++)
1266 if (! ((j
== no_conflict_pairs
[k
].allocno1
1267 && ialloc
== no_conflict_pairs
[k
].allocno2
)
1269 (j
== no_conflict_pairs
[k
].allocno2
1270 && ialloc
== no_conflict_pairs
[k
].allocno1
)))
1272 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1277 /* Record all allocnos currently live as conflicting
1278 with each other and with all hard regs currently live.
1279 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1280 are currently live. Their bits are also flagged in allocnos_live. */
1283 record_conflicts (allocno_vec
, len
)
1284 register short *allocno_vec
;
1287 register int allocno
;
1289 register int ialloc_prod
;
1293 allocno
= allocno_vec
[len
];
1294 ialloc_prod
= allocno
* allocno_row_words
;
1295 IOR_HARD_REG_SET (hard_reg_conflicts
[allocno
], hard_regs_live
);
1296 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1297 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1301 /* Handle the case where REG is set by the insn being scanned,
1302 during the forward scan to accumulate conflicts.
1303 Store a 1 in regs_live or allocnos_live for this register, record how many
1304 consecutive hardware registers it actually needs,
1305 and record a conflict with all other registers already live.
1307 Note that even if REG does not remain alive after this insn,
1308 we must mark it here as live, to ensure a conflict between
1309 REG and any other regs set in this insn that really do live.
1310 This is because those other regs could be considered after this.
1312 REG might actually be something other than a register;
1313 if so, we do nothing.
1315 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1316 a REG_INC note was found for it).
1318 CLOBBERs are processed here by calling mark_reg_clobber. */
1321 mark_reg_store (orig_reg
, setter
)
1322 rtx orig_reg
, setter
;
1325 register rtx reg
= orig_reg
;
1327 /* WORD is which word of a multi-register group is being stored.
1328 For the case where the store is actually into a SUBREG of REG.
1329 Except we don't use it; I believe the entire REG needs to be
1333 if (GET_CODE (reg
) == SUBREG
)
1335 word
= SUBREG_WORD (reg
);
1336 reg
= SUBREG_REG (reg
);
1339 if (GET_CODE (reg
) != REG
)
1342 if (setter
&& GET_CODE (setter
) == CLOBBER
)
1344 /* A clobber of a register should be processed here too. */
1345 mark_reg_clobber (orig_reg
, setter
);
1349 regs_set
[n_regs_set
++] = reg
;
1352 set_preference (reg
, SET_SRC (setter
));
1354 regno
= REGNO (reg
);
1356 if (reg_renumber
[regno
] >= 0)
1357 regno
= reg_renumber
[regno
] /* + word */;
1359 /* Either this is one of the max_allocno pseudo regs not allocated,
1360 or it is or has a hardware reg. First handle the pseudo-regs. */
1361 if (regno
>= FIRST_PSEUDO_REGISTER
)
1363 if (reg_allocno
[regno
] >= 0)
1365 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1366 record_one_conflict (regno
);
1369 /* Handle hardware regs (and pseudos allocated to hard regs). */
1370 else if (! fixed_regs
[regno
])
1372 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1373 while (regno
< last
)
1375 record_one_conflict (regno
);
1376 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1382 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1385 mark_reg_clobber (reg
, setter
)
1390 /* WORD is which word of a multi-register group is being stored.
1391 For the case where the store is actually into a SUBREG of REG.
1392 Except we don't use it; I believe the entire REG needs to be
1396 if (GET_CODE (setter
) != CLOBBER
)
1399 if (GET_CODE (reg
) == SUBREG
)
1401 word
= SUBREG_WORD (reg
);
1402 reg
= SUBREG_REG (reg
);
1405 if (GET_CODE (reg
) != REG
)
1408 regs_set
[n_regs_set
++] = reg
;
1410 regno
= REGNO (reg
);
1412 if (reg_renumber
[regno
] >= 0)
1413 regno
= reg_renumber
[regno
] /* + word */;
1415 /* Either this is one of the max_allocno pseudo regs not allocated,
1416 or it is or has a hardware reg. First handle the pseudo-regs. */
1417 if (regno
>= FIRST_PSEUDO_REGISTER
)
1419 if (reg_allocno
[regno
] >= 0)
1421 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1422 record_one_conflict (regno
);
1425 /* Handle hardware regs (and pseudos allocated to hard regs). */
1426 else if (! fixed_regs
[regno
])
1428 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1429 while (regno
< last
)
1431 record_one_conflict (regno
);
1432 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1438 /* Record that REG has conflicts with all the regs currently live.
1439 Do not mark REG itself as live. */
1442 mark_reg_conflicts (reg
)
1447 if (GET_CODE (reg
) == SUBREG
)
1448 reg
= SUBREG_REG (reg
);
1450 if (GET_CODE (reg
) != REG
)
1453 regno
= REGNO (reg
);
1455 if (reg_renumber
[regno
] >= 0)
1456 regno
= reg_renumber
[regno
];
1458 /* Either this is one of the max_allocno pseudo regs not allocated,
1459 or it is or has a hardware reg. First handle the pseudo-regs. */
1460 if (regno
>= FIRST_PSEUDO_REGISTER
)
1462 if (reg_allocno
[regno
] >= 0)
1463 record_one_conflict (regno
);
1465 /* Handle hardware regs (and pseudos allocated to hard regs). */
1466 else if (! fixed_regs
[regno
])
1468 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1469 while (regno
< last
)
1471 record_one_conflict (regno
);
1477 /* Mark REG as being dead (following the insn being scanned now).
1478 Store a 0 in regs_live or allocnos_live for this register. */
1481 mark_reg_death (reg
)
1484 register int regno
= REGNO (reg
);
1486 /* For pseudo reg, see if it has been assigned a hardware reg. */
1487 if (reg_renumber
[regno
] >= 0)
1488 regno
= reg_renumber
[regno
];
1490 /* Either this is one of the max_allocno pseudo regs not allocated,
1491 or it is a hardware reg. First handle the pseudo-regs. */
1492 if (regno
>= FIRST_PSEUDO_REGISTER
)
1494 if (reg_allocno
[regno
] >= 0)
1495 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1497 /* Handle hardware regs (and pseudos allocated to hard regs). */
1498 else if (! fixed_regs
[regno
])
1500 /* Pseudo regs already assigned hardware regs are treated
1501 almost the same as explicit hardware regs. */
1502 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1503 while (regno
< last
)
1505 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1511 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1512 for the value stored in it. MODE determines how many consecutive
1513 registers are actually in use. Do not record conflicts;
1514 it is assumed that the caller will do that. */
1517 mark_reg_live_nc (regno
, mode
)
1519 enum machine_mode mode
;
1521 register int last
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1522 while (regno
< last
)
1524 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1529 /* Try to set a preference for an allocno to a hard register.
1530 We are passed DEST and SRC which are the operands of a SET. It is known
1531 that SRC is a register. If SRC or the first operand of SRC is a register,
1532 try to set a preference. If one of the two is a hard register and the other
1533 is a pseudo-register, mark the preference.
1535 Note that we are not as aggressive as local-alloc in trying to tie a
1536 pseudo-register to a hard register. */
1539 set_preference (dest
, src
)
1542 int src_regno
, dest_regno
;
1543 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1544 to compensate for subregs in SRC or DEST. */
1549 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1550 src
= XEXP (src
, 0), copy
= 0;
1552 /* Get the reg number for both SRC and DEST.
1553 If neither is a reg, give up. */
1555 if (GET_CODE (src
) == REG
)
1556 src_regno
= REGNO (src
);
1557 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1559 src_regno
= REGNO (SUBREG_REG (src
));
1560 offset
+= SUBREG_WORD (src
);
1565 if (GET_CODE (dest
) == REG
)
1566 dest_regno
= REGNO (dest
);
1567 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1569 dest_regno
= REGNO (SUBREG_REG (dest
));
1570 offset
-= SUBREG_WORD (dest
);
1575 /* Convert either or both to hard reg numbers. */
1577 if (reg_renumber
[src_regno
] >= 0)
1578 src_regno
= reg_renumber
[src_regno
];
1580 if (reg_renumber
[dest_regno
] >= 0)
1581 dest_regno
= reg_renumber
[dest_regno
];
1583 /* Now if one is a hard reg and the other is a global pseudo
1584 then give the other a preference. */
1586 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1587 && reg_allocno
[src_regno
] >= 0)
1589 dest_regno
-= offset
;
1590 if (dest_regno
>= 0 && dest_regno
< FIRST_PSEUDO_REGISTER
)
1593 SET_REGBIT (hard_reg_copy_preferences
,
1594 reg_allocno
[src_regno
], dest_regno
);
1596 SET_REGBIT (hard_reg_preferences
,
1597 reg_allocno
[src_regno
], dest_regno
);
1598 for (i
= dest_regno
;
1599 i
< dest_regno
+ HARD_REGNO_NREGS (dest_regno
, GET_MODE (dest
));
1601 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1605 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1606 && reg_allocno
[dest_regno
] >= 0)
1608 src_regno
+= offset
;
1609 if (src_regno
>= 0 && src_regno
< FIRST_PSEUDO_REGISTER
)
1612 SET_REGBIT (hard_reg_copy_preferences
,
1613 reg_allocno
[dest_regno
], src_regno
);
1615 SET_REGBIT (hard_reg_preferences
,
1616 reg_allocno
[dest_regno
], src_regno
);
1618 i
< src_regno
+ HARD_REGNO_NREGS (src_regno
, GET_MODE (src
));
1620 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1625 /* Indicate that hard register number FROM was eliminated and replaced with
1626 an offset from hard register number TO. The status of hard registers live
1627 at the start of a basic block is updated by replacing a use of FROM with
1631 mark_elimination (from
, to
)
1636 for (i
= 0; i
< n_basic_blocks
; i
++)
1637 if (REGNO_REG_SET_P (basic_block_live_at_start
[i
], from
))
1639 CLEAR_REGNO_REG_SET (basic_block_live_at_start
[i
], from
);
1640 SET_REGNO_REG_SET (basic_block_live_at_start
[i
], to
);
1644 /* Print debugging trace information if -greg switch is given,
1645 showing the information on which the allocation decisions are based. */
1648 dump_conflicts (file
)
1652 register int has_preferences
;
1653 fprintf (file
, ";; %d regs to allocate:", max_allocno
);
1654 for (i
= 0; i
< max_allocno
; i
++)
1657 fprintf (file
, " %d", allocno_reg
[allocno_order
[i
]]);
1658 for (j
= 0; j
< max_regno
; j
++)
1659 if (reg_allocno
[j
] == allocno_order
[i
]
1660 && j
!= allocno_reg
[allocno_order
[i
]])
1661 fprintf (file
, "+%d", j
);
1662 if (allocno_size
[allocno_order
[i
]] != 1)
1663 fprintf (file
, " (%d)", allocno_size
[allocno_order
[i
]]);
1665 fprintf (file
, "\n");
1667 for (i
= 0; i
< max_allocno
; i
++)
1670 fprintf (file
, ";; %d conflicts:", allocno_reg
[i
]);
1671 for (j
= 0; j
< max_allocno
; j
++)
1672 if (CONFLICTP (i
, j
) || CONFLICTP (j
, i
))
1673 fprintf (file
, " %d", allocno_reg
[j
]);
1674 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1675 if (TEST_HARD_REG_BIT (hard_reg_conflicts
[i
], j
))
1676 fprintf (file
, " %d", j
);
1677 fprintf (file
, "\n");
1679 has_preferences
= 0;
1680 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1681 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1682 has_preferences
= 1;
1684 if (! has_preferences
)
1686 fprintf (file
, ";; %d preferences:", allocno_reg
[i
]);
1687 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1688 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1689 fprintf (file
, " %d", j
);
1690 fprintf (file
, "\n");
1692 fprintf (file
, "\n");
1696 dump_global_regs (file
)
1701 fprintf (file
, ";; Register dispositions:\n");
1702 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1703 if (reg_renumber
[i
] >= 0)
1705 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1707 fprintf (file
, "\n");
1710 fprintf (file
, "\n\n;; Hard regs used: ");
1711 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1712 if (regs_ever_live
[i
])
1713 fprintf (file
, " %d", i
);
1714 fprintf (file
, "\n\n");