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. */
31 #include "basic-block.h"
32 #include "hard-reg-set.h"
34 #include "insn-config.h"
37 /* This pass of the compiler performs global register allocation.
38 It assigns hard register numbers to all the pseudo registers
39 that were not handled in local_alloc. Assignments are recorded
40 in the vector reg_renumber, not by changing the rtl code.
41 (Such changes are made by final). The entry point is
42 the function global_alloc.
44 After allocation is complete, the reload pass is run as a subroutine
45 of this pass, so that when a pseudo reg loses its hard reg due to
46 spilling it is possible to make a second attempt to find a hard
47 reg for it. The reload pass is independent in other respects
48 and it is run even when stupid register allocation is in use.
50 1. count the pseudo-registers still needing allocation
51 and assign allocation-numbers (allocnos) to them.
52 Set up tables reg_allocno and allocno_reg to map
53 reg numbers to allocnos and vice versa.
54 max_allocno gets the number of allocnos in use.
56 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
57 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
58 for conflicts between allocnos and explicit hard register use
59 (which includes use of pseudo-registers allocated by local_alloc).
61 3. for each basic block
62 walk forward through the block, recording which
63 unallocated registers and which hardware registers are live.
64 Build the conflict matrix between the unallocated registers
65 and another of unallocated registers versus hardware registers.
66 Also record the preferred hardware registers
67 for each unallocated one.
69 4. Sort a table of the allocnos into order of
70 desirability of the variables.
72 5. Allocate the variables in that order; each if possible into
73 a preferred register, else into another register. */
75 /* Number of pseudo-registers still requiring allocation
76 (not allocated by local_allocate). */
78 static int max_allocno
;
80 /* Indexed by (pseudo) reg number, gives the allocno, or -1
81 for pseudo registers already allocated by local_allocate. */
85 /* Indexed by allocno, gives the reg number. */
87 static int *allocno_reg
;
89 /* A vector of the integers from 0 to max_allocno-1,
90 sorted in the order of first-to-be-allocated first. */
92 static int *allocno_order
;
94 /* Indexed by an allocno, gives the number of consecutive
95 hard registers needed by that pseudo reg. */
97 static int *allocno_size
;
99 /* Indexed by (pseudo) reg number, gives the number of another
100 lower-numbered pseudo reg which can share a hard reg with this pseudo
101 *even if the two pseudos would otherwise appear to conflict*. */
103 static int *reg_may_share
;
105 /* Define the number of bits in each element of `conflicts' and what
106 type that element has. We use the largest integer format on the
109 #define INT_BITS HOST_BITS_PER_WIDE_INT
110 #define INT_TYPE HOST_WIDE_INT
112 /* max_allocno by max_allocno array of bits,
113 recording whether two allocno's conflict (can't go in the same
116 `conflicts' is not symmetric; a conflict between allocno's i and j
117 is recorded either in element i,j or in element j,i. */
119 static INT_TYPE
*conflicts
;
121 /* Number of ints require to hold max_allocno bits.
122 This is the length of a row in `conflicts'. */
124 static int allocno_row_words
;
126 /* Two macros to test or store 1 in an element of `conflicts'. */
128 #define CONFLICTP(I, J) \
129 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
130 & ((INT_TYPE) 1 << ((J) % INT_BITS)))
132 #define SET_CONFLICT(I, J) \
133 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
134 |= ((INT_TYPE) 1 << ((J) % INT_BITS)))
136 /* Set of hard regs currently live (during scan of all insns). */
138 static HARD_REG_SET hard_regs_live
;
140 /* Indexed by N, set of hard regs conflicting with allocno N. */
142 static HARD_REG_SET
*hard_reg_conflicts
;
144 /* Indexed by N, set of hard regs preferred by allocno N.
145 This is used to make allocnos go into regs that are copied to or from them,
146 when possible, to reduce register shuffling. */
148 static HARD_REG_SET
*hard_reg_preferences
;
150 /* Similar, but just counts register preferences made in simple copy
151 operations, rather than arithmetic. These are given priority because
152 we can always eliminate an insn by using these, but using a register
153 in the above list won't always eliminate an insn. */
155 static HARD_REG_SET
*hard_reg_copy_preferences
;
157 /* Similar to hard_reg_preferences, but includes bits for subsequent
158 registers when an allocno is multi-word. The above variable is used for
159 allocation while this is used to build reg_someone_prefers, below. */
161 static HARD_REG_SET
*hard_reg_full_preferences
;
163 /* Indexed by N, set of hard registers that some later allocno has a
166 static HARD_REG_SET
*regs_someone_prefers
;
168 /* Set of registers that global-alloc isn't supposed to use. */
170 static HARD_REG_SET no_global_alloc_regs
;
172 /* Set of registers used so far. */
174 static HARD_REG_SET regs_used_so_far
;
176 /* Number of calls crossed by each allocno. */
178 static int *allocno_calls_crossed
;
180 /* Number of refs (weighted) to each allocno. */
182 static int *allocno_n_refs
;
184 /* Guess at live length of each allocno.
185 This is actually the max of the live lengths of the regs. */
187 static int *allocno_live_length
;
189 /* Number of refs (weighted) to each hard reg, as used by local alloc.
190 It is zero for a reg that contains global pseudos or is explicitly used. */
192 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
194 /* Guess at live length of each hard reg, as used by local alloc.
195 This is actually the sum of the live lengths of the specific regs. */
197 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
199 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
200 for vector element I, and hard register number J. */
202 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
204 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
206 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
208 /* Bit mask for allocnos live at current point in the scan. */
210 static INT_TYPE
*allocnos_live
;
212 /* Test, set or clear bit number I in allocnos_live,
213 a bit vector indexed by allocno. */
215 #define ALLOCNO_LIVE_P(I) \
216 (allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS)))
218 #define SET_ALLOCNO_LIVE(I) \
219 (allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS)))
221 #define CLEAR_ALLOCNO_LIVE(I) \
222 (allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((I) % INT_BITS)))
224 /* This is turned off because it doesn't work right for DImode.
225 (And it is only used for DImode, so the other cases are worthless.)
226 The problem is that it isn't true that there is NO possibility of conflict;
227 only that there is no conflict if the two pseudos get the exact same regs.
228 If they were allocated with a partial overlap, there would be a conflict.
229 We can't safely turn off the conflict unless we have another way to
230 prevent the partial overlap.
232 Idea: change hard_reg_conflicts so that instead of recording which
233 hard regs the allocno may not overlap, it records where the allocno
234 may not start. Change both where it is used and where it is updated.
235 Then there is a way to record that (reg:DI 108) may start at 10
236 but not at 9 or 11. There is still the question of how to record
237 this semi-conflict between two pseudos. */
239 /* Reg pairs for which conflict after the current insn
240 is inhibited by a REG_NO_CONFLICT note.
241 If the table gets full, we ignore any other notes--that is conservative. */
242 #define NUM_NO_CONFLICT_PAIRS 4
243 /* Number of pairs in use in this insn. */
244 int n_no_conflict_pairs
;
245 static struct { int allocno1
, allocno2
;}
246 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
249 /* Record all regs that are set in any one insn.
250 Communication from mark_reg_{store,clobber} and global_conflicts. */
252 static rtx
*regs_set
;
253 static int n_regs_set
;
255 /* All registers that can be eliminated. */
257 static HARD_REG_SET eliminable_regset
;
259 static int allocno_compare
PROTO((const GENERIC_PTR
, const GENERIC_PTR
));
260 static void global_conflicts
PROTO((void));
261 static void expand_preferences
PROTO((void));
262 static void prune_preferences
PROTO((void));
263 static void find_reg
PROTO((int, HARD_REG_SET
, int, int, int));
264 static void record_one_conflict
PROTO((int));
265 static void record_conflicts
PROTO((short *, int));
266 static void mark_reg_store
PROTO((rtx
, rtx
));
267 static void mark_reg_clobber
PROTO((rtx
, rtx
));
268 static void mark_reg_conflicts
PROTO((rtx
));
269 static void mark_reg_death
PROTO((rtx
));
270 static void mark_reg_live_nc
PROTO((int, enum machine_mode
));
271 static void set_preference
PROTO((rtx
, rtx
));
272 static void dump_conflicts
PROTO((FILE *));
274 /* Perform allocation of pseudo-registers not allocated by local_alloc.
275 FILE is a file to output debugging information on,
276 or zero if such output is not desired.
278 Return value is nonzero if reload failed
279 and we must not do any more for this function. */
286 #ifdef ELIMINABLE_REGS
287 static struct {int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
290 = (! flag_omit_frame_pointer
291 #ifdef EXIT_IGNORE_STACK
292 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
294 || FRAME_POINTER_REQUIRED
);
301 /* A machine may have certain hard registers that
302 are safe to use only within a basic block. */
304 CLEAR_HARD_REG_SET (no_global_alloc_regs
);
305 #ifdef OVERLAPPING_REGNO_P
306 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
307 if (OVERLAPPING_REGNO_P (i
))
308 SET_HARD_REG_BIT (no_global_alloc_regs
, i
);
311 /* Build the regset of all eliminable registers and show we can't use those
312 that we already know won't be eliminated. */
313 #ifdef ELIMINABLE_REGS
314 for (i
= 0; i
< sizeof eliminables
/ sizeof eliminables
[0]; i
++)
316 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
318 if (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
319 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
))
320 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
322 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
323 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
325 SET_HARD_REG_BIT (no_global_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
329 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
331 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
334 /* Track which registers have already been used. Start with registers
335 explicitly in the rtl, then registers allocated by local register
338 CLEAR_HARD_REG_SET (regs_used_so_far
);
339 #ifdef LEAF_REGISTERS
340 /* If we are doing the leaf function optimization, and this is a leaf
341 function, it means that the registers that take work to save are those
342 that need a register window. So prefer the ones that can be used in
346 static char leaf_regs
[] = LEAF_REGISTERS
;
348 if (only_leaf_regs_used () && leaf_function_p ())
349 cheap_regs
= leaf_regs
;
351 cheap_regs
= call_used_regs
;
352 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
353 if (regs_ever_live
[i
] || cheap_regs
[i
])
354 SET_HARD_REG_BIT (regs_used_so_far
, i
);
357 /* We consider registers that do not have to be saved over calls as if
358 they were already used since there is no cost in using them. */
359 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
360 if (regs_ever_live
[i
] || call_used_regs
[i
])
361 SET_HARD_REG_BIT (regs_used_so_far
, i
);
364 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
365 if (reg_renumber
[i
] >= 0)
366 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
368 /* Establish mappings from register number to allocation number
369 and vice versa. In the process, count the allocnos. */
371 reg_allocno
= (int *) alloca (max_regno
* sizeof (int));
373 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
376 /* Initialize the shared-hard-reg mapping
377 from the list of pairs that may share. */
378 reg_may_share
= (int *) alloca (max_regno
* sizeof (int));
379 bzero ((char *) reg_may_share
, max_regno
* sizeof (int));
380 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
382 int r1
= REGNO (XEXP (x
, 0));
383 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
385 reg_may_share
[r1
] = r2
;
387 reg_may_share
[r2
] = r1
;
390 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
391 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
392 that we are supposed to refrain from putting in a hard reg.
393 -2 means do make an allocno but don't allocate it. */
394 if (REG_N_REFS (i
) != 0 && reg_renumber
[i
] < 0 && REG_LIVE_LENGTH (i
) != -1
395 /* Don't allocate pseudos that cross calls,
396 if this function receives a nonlocal goto. */
397 && (! current_function_has_nonlocal_label
398 || REG_N_CALLS_CROSSED (i
) == 0))
400 if (reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
401 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
403 reg_allocno
[i
] = max_allocno
++;
404 if (REG_LIVE_LENGTH (i
) == 0)
410 allocno_reg
= (int *) alloca (max_allocno
* sizeof (int));
411 allocno_size
= (int *) alloca (max_allocno
* sizeof (int));
412 allocno_calls_crossed
= (int *) alloca (max_allocno
* sizeof (int));
413 allocno_n_refs
= (int *) alloca (max_allocno
* sizeof (int));
414 allocno_live_length
= (int *) alloca (max_allocno
* sizeof (int));
415 bzero ((char *) allocno_size
, max_allocno
* sizeof (int));
416 bzero ((char *) allocno_calls_crossed
, max_allocno
* sizeof (int));
417 bzero ((char *) allocno_n_refs
, max_allocno
* sizeof (int));
418 bzero ((char *) allocno_live_length
, max_allocno
* sizeof (int));
420 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
421 if (reg_allocno
[i
] >= 0)
423 int allocno
= reg_allocno
[i
];
424 allocno_reg
[allocno
] = i
;
425 allocno_size
[allocno
] = PSEUDO_REGNO_SIZE (i
);
426 allocno_calls_crossed
[allocno
] += REG_N_CALLS_CROSSED (i
);
427 allocno_n_refs
[allocno
] += REG_N_REFS (i
);
428 if (allocno_live_length
[allocno
] < REG_LIVE_LENGTH (i
))
429 allocno_live_length
[allocno
] = REG_LIVE_LENGTH (i
);
432 /* Calculate amount of usage of each hard reg by pseudos
433 allocated by local-alloc. This is to see if we want to
435 bzero ((char *) local_reg_live_length
, sizeof local_reg_live_length
);
436 bzero ((char *) local_reg_n_refs
, sizeof local_reg_n_refs
);
437 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
438 if (reg_allocno
[i
] < 0 && reg_renumber
[i
] >= 0)
440 int regno
= reg_renumber
[i
];
441 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (i
));
444 for (j
= regno
; j
< endregno
; j
++)
446 local_reg_n_refs
[j
] += REG_N_REFS (i
);
447 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
451 /* We can't override local-alloc for a reg used not just by local-alloc. */
452 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
453 if (regs_ever_live
[i
])
454 local_reg_n_refs
[i
] = 0;
456 /* Likewise for regs used in a SCRATCH. */
457 for (i
= 0; i
< scratch_list_length
; i
++)
460 int regno
= REGNO (scratch_list
[i
]);
461 int lim
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (scratch_list
[i
]));
464 for (j
= regno
; j
< lim
; j
++)
465 local_reg_n_refs
[j
] = 0;
468 /* Allocate the space for the conflict and preference tables and
472 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
473 bzero ((char *) hard_reg_conflicts
, max_allocno
* sizeof (HARD_REG_SET
));
476 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
477 bzero ((char *) hard_reg_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
479 hard_reg_copy_preferences
480 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
481 bzero ((char *) hard_reg_copy_preferences
,
482 max_allocno
* sizeof (HARD_REG_SET
));
484 hard_reg_full_preferences
485 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
486 bzero ((char *) hard_reg_full_preferences
,
487 max_allocno
* sizeof (HARD_REG_SET
));
490 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
491 bzero ((char *) regs_someone_prefers
, max_allocno
* sizeof (HARD_REG_SET
));
493 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
495 /* We used to use alloca here, but the size of what it would try to
496 allocate would occasionally cause it to exceed the stack limit and
497 cause unpredictable core dumps. Some examples were > 2Mb in size. */
498 conflicts
= (INT_TYPE
*) xmalloc (max_allocno
* allocno_row_words
499 * sizeof (INT_TYPE
));
500 bzero ((char *) conflicts
,
501 max_allocno
* allocno_row_words
* sizeof (INT_TYPE
));
503 allocnos_live
= (INT_TYPE
*) alloca (allocno_row_words
* sizeof (INT_TYPE
));
505 /* If there is work to be done (at least one reg to allocate),
506 perform global conflict analysis and allocate the regs. */
510 /* Scan all the insns and compute the conflicts among allocnos
511 and between allocnos and hard regs. */
515 /* Eliminate conflicts between pseudos and eliminable registers. If
516 the register is not eliminated, the pseudo won't really be able to
517 live in the eliminable register, so the conflict doesn't matter.
518 If we do eliminate the register, the conflict will no longer exist.
519 So in either case, we can ignore the conflict. Likewise for
522 for (i
= 0; i
< max_allocno
; i
++)
524 AND_COMPL_HARD_REG_SET (hard_reg_conflicts
[i
], eliminable_regset
);
525 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[i
],
527 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[i
], eliminable_regset
);
530 /* Try to expand the preferences by merging them between allocnos. */
532 expand_preferences ();
534 /* Determine the order to allocate the remaining pseudo registers. */
536 allocno_order
= (int *) alloca (max_allocno
* sizeof (int));
537 for (i
= 0; i
< max_allocno
; i
++)
538 allocno_order
[i
] = i
;
540 /* Default the size to 1, since allocno_compare uses it to divide by.
541 Also convert allocno_live_length of zero to -1. A length of zero
542 can occur when all the registers for that allocno have reg_live_length
543 equal to -2. In this case, we want to make an allocno, but not
544 allocate it. So avoid the divide-by-zero and set it to a low
547 for (i
= 0; i
< max_allocno
; i
++)
549 if (allocno_size
[i
] == 0)
551 if (allocno_live_length
[i
] == 0)
552 allocno_live_length
[i
] = -1;
555 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
557 prune_preferences ();
560 dump_conflicts (file
);
562 /* Try allocating them, one by one, in that order,
563 except for parameters marked with reg_live_length[regno] == -2. */
565 for (i
= 0; i
< max_allocno
; i
++)
566 if (REG_LIVE_LENGTH (allocno_reg
[allocno_order
[i
]]) >= 0)
568 /* If we have more than one register class,
569 first try allocating in the class that is cheapest
570 for this pseudo-reg. If that fails, try any reg. */
571 if (N_REG_CLASSES
> 1)
573 find_reg (allocno_order
[i
], HARD_CONST (0), 0, 0, 0);
574 if (reg_renumber
[allocno_reg
[allocno_order
[i
]]] >= 0)
577 if (reg_alternate_class (allocno_reg
[allocno_order
[i
]]) != NO_REGS
)
578 find_reg (allocno_order
[i
], HARD_CONST (0), 1, 0, 0);
582 /* Do the reloads now while the allocno data still exist, so that we can
583 try to assign new hard regs to any pseudo regs that are spilled. */
585 #if 0 /* We need to eliminate regs even if there is no rtl code,
586 for the sake of debugging information. */
587 if (n_basic_blocks
> 0)
589 retval
= reload (get_insns (), 1, file
);
595 /* Sort predicate for ordering the allocnos.
596 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
599 allocno_compare (v1p
, v2p
)
600 const GENERIC_PTR v1p
;
601 const GENERIC_PTR v2p
;
603 int v1
= *(int *)v1p
, v2
= *(int *)v2p
;
604 /* Note that the quotient will never be bigger than
605 the value of floor_log2 times the maximum number of
606 times a register can occur in one insn (surely less than 100).
607 Multiplying this by 10000 can't overflow. */
609 = (((double) (floor_log2 (allocno_n_refs
[v1
]) * allocno_n_refs
[v1
])
610 / allocno_live_length
[v1
])
611 * 10000 * allocno_size
[v1
]);
613 = (((double) (floor_log2 (allocno_n_refs
[v2
]) * allocno_n_refs
[v2
])
614 / allocno_live_length
[v2
])
615 * 10000 * allocno_size
[v2
]);
619 /* If regs are equally good, sort by allocno,
620 so that the results of qsort leave nothing to chance. */
624 /* Scan the rtl code and record all conflicts and register preferences in the
625 conflict matrices and preference tables. */
632 short *block_start_allocnos
;
634 /* Make a vector that mark_reg_{store,clobber} will store in. */
635 regs_set
= (rtx
*) alloca (max_parallel
* sizeof (rtx
) * 2);
637 block_start_allocnos
= (short *) alloca (max_allocno
* sizeof (short));
639 for (b
= 0; b
< n_basic_blocks
; b
++)
641 bzero ((char *) allocnos_live
, allocno_row_words
* sizeof (INT_TYPE
));
643 /* Initialize table of registers currently live
644 to the state at the beginning of this basic block.
645 This also marks the conflicts among them.
647 For pseudo-regs, there is only one bit for each one
648 no matter how many hard regs it occupies.
649 This is ok; we know the size from PSEUDO_REGNO_SIZE.
650 For explicit hard regs, we cannot know the size that way
651 since one hard reg can be used with various sizes.
652 Therefore, we must require that all the hard regs
653 implicitly live as part of a multi-word hard reg
654 are explicitly marked in basic_block_live_at_start. */
657 register regset old
= basic_block_live_at_start
[b
];
660 REG_SET_TO_HARD_REG_SET (hard_regs_live
, old
);
661 EXECUTE_IF_SET_IN_REG_SET (old
, FIRST_PSEUDO_REGISTER
, i
,
663 register int a
= reg_allocno
[i
];
666 SET_ALLOCNO_LIVE (a
);
667 block_start_allocnos
[ax
++] = a
;
669 else if ((a
= reg_renumber
[i
]) >= 0)
671 (a
, PSEUDO_REGNO_MODE (i
));
674 /* Record that each allocno now live conflicts with each other
675 allocno now live, and with each hard reg now live. */
677 record_conflicts (block_start_allocnos
, ax
);
680 insn
= basic_block_head
[b
];
682 /* Scan the code of this basic block, noting which allocnos
683 and hard regs are born or die. When one is born,
684 record a conflict with all others currently live. */
688 register RTX_CODE code
= GET_CODE (insn
);
691 /* Make regs_set an empty set. */
695 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
700 for (link
= REG_NOTES (insn
);
701 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
702 link
= XEXP (link
, 1))
703 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
705 no_conflict_pairs
[i
].allocno1
706 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
707 no_conflict_pairs
[i
].allocno2
708 = reg_allocno
[REGNO (XEXP (link
, 0))];
713 /* Mark any registers clobbered by INSN as live,
714 so they conflict with the inputs. */
716 note_stores (PATTERN (insn
), mark_reg_clobber
);
718 /* Mark any registers dead after INSN as dead now. */
720 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
721 if (REG_NOTE_KIND (link
) == REG_DEAD
)
722 mark_reg_death (XEXP (link
, 0));
724 /* Mark any registers set in INSN as live,
725 and mark them as conflicting with all other live regs.
726 Clobbers are processed again, so they conflict with
727 the registers that are set. */
729 note_stores (PATTERN (insn
), mark_reg_store
);
732 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
733 if (REG_NOTE_KIND (link
) == REG_INC
)
734 mark_reg_store (XEXP (link
, 0), NULL_RTX
);
737 /* If INSN has multiple outputs, then any reg that dies here
738 and is used inside of an output
739 must conflict with the other outputs. */
741 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& !single_set (insn
))
742 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
743 if (REG_NOTE_KIND (link
) == REG_DEAD
)
745 int used_in_output
= 0;
747 rtx reg
= XEXP (link
, 0);
749 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
751 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
752 if (GET_CODE (set
) == SET
753 && GET_CODE (SET_DEST (set
)) != REG
754 && !rtx_equal_p (reg
, SET_DEST (set
))
755 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
759 mark_reg_conflicts (reg
);
762 /* Mark any registers set in INSN and then never used. */
764 while (n_regs_set
> 0)
765 if (find_regno_note (insn
, REG_UNUSED
,
766 REGNO (regs_set
[--n_regs_set
])))
767 mark_reg_death (regs_set
[n_regs_set
]);
770 if (insn
== basic_block_end
[b
])
772 insn
= NEXT_INSN (insn
);
776 /* Expand the preference information by looking for cases where one allocno
777 dies in an insn that sets an allocno. If those two allocnos don't conflict,
778 merge any preferences between those allocnos. */
781 expand_preferences ()
787 /* We only try to handle the most common cases here. Most of the cases
788 where this wins are reg-reg copies. */
790 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
791 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
792 && (set
= single_set (insn
)) != 0
793 && GET_CODE (SET_DEST (set
)) == REG
794 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
795 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
796 if (REG_NOTE_KIND (link
) == REG_DEAD
797 && GET_CODE (XEXP (link
, 0)) == REG
798 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
799 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
800 reg_allocno
[REGNO (XEXP (link
, 0))])
801 && ! CONFLICTP (reg_allocno
[REGNO (XEXP (link
, 0))],
802 reg_allocno
[REGNO (SET_DEST (set
))]))
804 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
805 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
807 if (XEXP (link
, 0) == SET_SRC (set
))
809 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a1
],
810 hard_reg_copy_preferences
[a2
]);
811 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a2
],
812 hard_reg_copy_preferences
[a1
]);
815 IOR_HARD_REG_SET (hard_reg_preferences
[a1
],
816 hard_reg_preferences
[a2
]);
817 IOR_HARD_REG_SET (hard_reg_preferences
[a2
],
818 hard_reg_preferences
[a1
]);
819 IOR_HARD_REG_SET (hard_reg_full_preferences
[a1
],
820 hard_reg_full_preferences
[a2
]);
821 IOR_HARD_REG_SET (hard_reg_full_preferences
[a2
],
822 hard_reg_full_preferences
[a1
]);
826 /* Prune the preferences for global registers to exclude registers that cannot
829 Compute `regs_someone_prefers', which is a bitmask of the hard registers
830 that are preferred by conflicting registers of lower priority. If possible,
831 we will avoid using these registers. */
839 /* Scan least most important to most important.
840 For each allocno, remove from preferences registers that cannot be used,
841 either because of conflicts or register type. Then compute all registers
842 preferred by each lower-priority register that conflicts. */
844 for (i
= max_allocno
- 1; i
>= 0; i
--)
848 allocno
= allocno_order
[i
];
849 COPY_HARD_REG_SET (temp
, hard_reg_conflicts
[allocno
]);
851 if (allocno_calls_crossed
[allocno
] == 0)
852 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
854 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
856 IOR_COMPL_HARD_REG_SET
858 reg_class_contents
[(int) reg_preferred_class (allocno_reg
[allocno
])]);
860 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], temp
);
861 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], temp
);
862 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences
[allocno
], temp
);
864 CLEAR_HARD_REG_SET (regs_someone_prefers
[allocno
]);
866 /* Merge in the preferences of lower-priority registers (they have
867 already been pruned). If we also prefer some of those registers,
868 don't exclude them unless we are of a smaller size (in which case
869 we want to give the lower-priority allocno the first chance for
871 for (j
= i
+ 1; j
< max_allocno
; j
++)
872 if (CONFLICTP (allocno
, allocno_order
[j
])
873 || CONFLICTP (allocno_order
[j
], allocno
))
875 COPY_HARD_REG_SET (temp
,
876 hard_reg_full_preferences
[allocno_order
[j
]]);
877 if (allocno_size
[allocno_order
[j
]] <= allocno_size
[allocno
])
878 AND_COMPL_HARD_REG_SET (temp
,
879 hard_reg_full_preferences
[allocno
]);
881 IOR_HARD_REG_SET (regs_someone_prefers
[allocno
], temp
);
886 /* Assign a hard register to ALLOCNO; look for one that is the beginning
887 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
888 The registers marked in PREFREGS are tried first.
890 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
891 be used for this allocation.
893 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
894 Otherwise ignore that preferred class and use the alternate class.
896 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
897 will have to be saved and restored at calls.
899 RETRYING is nonzero if this is called from retry_global_alloc.
901 If we find one, record it in reg_renumber.
902 If not, do nothing. */
905 find_reg (allocno
, losers
, alt_regs_p
, accept_call_clobbered
, retrying
)
909 int accept_call_clobbered
;
912 register int i
, best_reg
, pass
;
914 register /* Declare it register if it's a scalar. */
916 HARD_REG_SET used
, used1
, used2
;
918 enum reg_class
class = (alt_regs_p
919 ? reg_alternate_class (allocno_reg
[allocno
])
920 : reg_preferred_class (allocno_reg
[allocno
]));
921 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno_reg
[allocno
]);
923 if (accept_call_clobbered
)
924 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
925 else if (allocno_calls_crossed
[allocno
] == 0)
926 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
928 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
930 /* Some registers should not be allocated in global-alloc. */
931 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
933 IOR_HARD_REG_SET (used1
, losers
);
935 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
936 COPY_HARD_REG_SET (used2
, used1
);
938 IOR_HARD_REG_SET (used1
, hard_reg_conflicts
[allocno
]);
940 #ifdef CLASS_CANNOT_CHANGE_SIZE
941 if (REG_CHANGES_SIZE (allocno_reg
[allocno
]))
942 IOR_HARD_REG_SET (used1
,
943 reg_class_contents
[(int) CLASS_CANNOT_CHANGE_SIZE
]);
946 /* Try each hard reg to see if it fits. Do this in two passes.
947 In the first pass, skip registers that are preferred by some other pseudo
948 to give it a better chance of getting one of those registers. Only if
949 we can't get a register when excluding those do we take one of them.
950 However, we never allocate a register for the first time in pass 0. */
952 COPY_HARD_REG_SET (used
, used1
);
953 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
954 IOR_HARD_REG_SET (used
, regs_someone_prefers
[allocno
]);
957 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
958 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
962 COPY_HARD_REG_SET (used
, used1
);
963 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
965 #ifdef REG_ALLOC_ORDER
966 int regno
= reg_alloc_order
[i
];
970 if (! TEST_HARD_REG_BIT (used
, regno
)
971 && HARD_REGNO_MODE_OK (regno
, mode
))
974 register int lim
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
977 && ! TEST_HARD_REG_BIT (used
, j
));
984 #ifndef REG_ALLOC_ORDER
985 i
= j
; /* Skip starting points we know will lose */
991 /* See if there is a preferred register with the same class as the register
992 we allocated above. Making this restriction prevents register
993 preferencing from creating worse register allocation.
995 Remove from the preferred registers and conflicting registers. Note that
996 additional conflicts may have been added after `prune_preferences' was
999 First do this for those register with copy preferences, then all
1000 preferred registers. */
1002 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], used
);
1003 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences
[allocno
],
1004 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
1008 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1009 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences
[allocno
], i
)
1010 && HARD_REGNO_MODE_OK (i
, mode
)
1011 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1012 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1013 REGNO_REG_CLASS (best_reg
))
1014 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1015 REGNO_REG_CLASS (i
))))
1018 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1021 && ! TEST_HARD_REG_BIT (used
, j
)
1022 && (REGNO_REG_CLASS (j
)
1023 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1024 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1025 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1026 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1027 REGNO_REG_CLASS (j
))));
1038 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], used
);
1039 GO_IF_HARD_REG_SUBSET (hard_reg_preferences
[allocno
],
1040 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1044 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1045 if (TEST_HARD_REG_BIT (hard_reg_preferences
[allocno
], i
)
1046 && HARD_REGNO_MODE_OK (i
, mode
)
1047 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1048 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1049 REGNO_REG_CLASS (best_reg
))
1050 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1051 REGNO_REG_CLASS (i
))))
1054 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1057 && ! TEST_HARD_REG_BIT (used
, j
)
1058 && (REGNO_REG_CLASS (j
)
1059 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1060 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1061 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1062 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1063 REGNO_REG_CLASS (j
))));
1074 /* If we haven't succeeded yet, try with caller-saves.
1075 We need not check to see if the current function has nonlocal
1076 labels because we don't put any pseudos that are live over calls in
1077 registers in that case. */
1079 if (flag_caller_saves
&& best_reg
< 0)
1081 /* Did not find a register. If it would be profitable to
1082 allocate a call-clobbered register and save and restore it
1083 around calls, do that. */
1084 if (! accept_call_clobbered
1085 && allocno_calls_crossed
[allocno
] != 0
1086 && CALLER_SAVE_PROFITABLE (allocno_n_refs
[allocno
],
1087 allocno_calls_crossed
[allocno
]))
1089 HARD_REG_SET new_losers
;
1091 CLEAR_HARD_REG_SET (new_losers
);
1093 COPY_HARD_REG_SET (new_losers
, losers
);
1095 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1096 find_reg (allocno
, new_losers
, alt_regs_p
, 1, retrying
);
1097 if (reg_renumber
[allocno_reg
[allocno
]] >= 0)
1099 caller_save_needed
= 1;
1105 /* If we haven't succeeded yet,
1106 see if some hard reg that conflicts with us
1107 was utilized poorly by local-alloc.
1108 If so, kick out the regs that were put there by local-alloc
1109 so we can use it instead. */
1110 if (best_reg
< 0 && !retrying
1111 /* Let's not bother with multi-reg allocnos. */
1112 && allocno_size
[allocno
] == 1)
1114 /* Count from the end, to find the least-used ones first. */
1115 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1117 #ifdef REG_ALLOC_ORDER
1118 int regno
= reg_alloc_order
[i
];
1123 if (local_reg_n_refs
[regno
] != 0
1124 /* Don't use a reg no good for this pseudo. */
1125 && ! TEST_HARD_REG_BIT (used2
, regno
)
1126 && HARD_REGNO_MODE_OK (regno
, mode
)
1127 #ifdef CLASS_CANNOT_CHANGE_SIZE
1128 && ! (REG_CHANGES_SIZE (allocno_reg
[allocno
])
1129 && (TEST_HARD_REG_BIT
1130 (reg_class_contents
[(int) CLASS_CANNOT_CHANGE_SIZE
],
1135 /* We explicitly evaluate the divide results into temporary
1136 variables so as to avoid excess precision problems that occur
1137 on a i386-unknown-sysv4.2 (unixware) host. */
1139 double tmp1
= ((double) local_reg_n_refs
[regno
]
1140 / local_reg_live_length
[regno
]);
1141 double tmp2
= ((double) allocno_n_refs
[allocno
]
1142 / allocno_live_length
[allocno
]);
1146 /* Hard reg REGNO was used less in total by local regs
1147 than it would be used by this one allocno! */
1149 for (k
= 0; k
< max_regno
; k
++)
1150 if (reg_renumber
[k
] >= 0)
1152 int r
= reg_renumber
[k
];
1154 = r
+ HARD_REGNO_NREGS (r
, PSEUDO_REGNO_MODE (k
));
1156 if (regno
>= r
&& regno
< endregno
)
1157 reg_renumber
[k
] = -1;
1167 /* Did we find a register? */
1171 register int lim
, j
;
1172 HARD_REG_SET this_reg
;
1174 /* Yes. Record it as the hard register of this pseudo-reg. */
1175 reg_renumber
[allocno_reg
[allocno
]] = best_reg
;
1176 /* Also of any pseudo-regs that share with it. */
1177 if (reg_may_share
[allocno_reg
[allocno
]])
1178 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1179 if (reg_allocno
[j
] == allocno
)
1180 reg_renumber
[j
] = best_reg
;
1182 /* Make a set of the hard regs being allocated. */
1183 CLEAR_HARD_REG_SET (this_reg
);
1184 lim
= best_reg
+ HARD_REGNO_NREGS (best_reg
, mode
);
1185 for (j
= best_reg
; j
< lim
; j
++)
1187 SET_HARD_REG_BIT (this_reg
, j
);
1188 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1189 /* This is no longer a reg used just by local regs. */
1190 local_reg_n_refs
[j
] = 0;
1192 /* For each other pseudo-reg conflicting with this one,
1193 mark it as conflicting with the hard regs this one occupies. */
1195 for (j
= 0; j
< max_allocno
; j
++)
1196 if (CONFLICTP (lim
, j
) || CONFLICTP (j
, lim
))
1198 IOR_HARD_REG_SET (hard_reg_conflicts
[j
], this_reg
);
1203 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1204 Perhaps it had previously seemed not worth a hard reg,
1205 or perhaps its old hard reg has been commandeered for reloads.
1206 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1207 they do not appear to be allocated.
1208 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1211 retry_global_alloc (regno
, forbidden_regs
)
1213 HARD_REG_SET forbidden_regs
;
1215 int allocno
= reg_allocno
[regno
];
1218 /* If we have more than one register class,
1219 first try allocating in the class that is cheapest
1220 for this pseudo-reg. If that fails, try any reg. */
1221 if (N_REG_CLASSES
> 1)
1222 find_reg (allocno
, forbidden_regs
, 0, 0, 1);
1223 if (reg_renumber
[regno
] < 0
1224 && reg_alternate_class (regno
) != NO_REGS
)
1225 find_reg (allocno
, forbidden_regs
, 1, 0, 1);
1227 /* If we found a register, modify the RTL for the register to
1228 show the hard register, and mark that register live. */
1229 if (reg_renumber
[regno
] >= 0)
1231 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1232 mark_home_live (regno
);
1237 /* Record a conflict between register REGNO
1238 and everything currently live.
1239 REGNO must not be a pseudo reg that was allocated
1240 by local_alloc; such numbers must be translated through
1241 reg_renumber before calling here. */
1244 record_one_conflict (regno
)
1249 if (regno
< FIRST_PSEUDO_REGISTER
)
1250 /* When a hard register becomes live,
1251 record conflicts with live pseudo regs. */
1252 for (j
= 0; j
< max_allocno
; j
++)
1254 if (ALLOCNO_LIVE_P (j
))
1255 SET_HARD_REG_BIT (hard_reg_conflicts
[j
], regno
);
1258 /* When a pseudo-register becomes live,
1259 record conflicts first with hard regs,
1260 then with other pseudo regs. */
1262 register int ialloc
= reg_allocno
[regno
];
1263 register int ialloc_prod
= ialloc
* allocno_row_words
;
1264 IOR_HARD_REG_SET (hard_reg_conflicts
[ialloc
], hard_regs_live
);
1265 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1269 for (k
= 0; k
< n_no_conflict_pairs
; k
++)
1270 if (! ((j
== no_conflict_pairs
[k
].allocno1
1271 && ialloc
== no_conflict_pairs
[k
].allocno2
)
1273 (j
== no_conflict_pairs
[k
].allocno2
1274 && ialloc
== no_conflict_pairs
[k
].allocno1
)))
1276 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1281 /* Record all allocnos currently live as conflicting
1282 with each other and with all hard regs currently live.
1283 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1284 are currently live. Their bits are also flagged in allocnos_live. */
1287 record_conflicts (allocno_vec
, len
)
1288 register short *allocno_vec
;
1291 register int allocno
;
1293 register int ialloc_prod
;
1297 allocno
= allocno_vec
[len
];
1298 ialloc_prod
= allocno
* allocno_row_words
;
1299 IOR_HARD_REG_SET (hard_reg_conflicts
[allocno
], hard_regs_live
);
1300 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1301 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1305 /* Handle the case where REG is set by the insn being scanned,
1306 during the forward scan to accumulate conflicts.
1307 Store a 1 in regs_live or allocnos_live for this register, record how many
1308 consecutive hardware registers it actually needs,
1309 and record a conflict with all other registers already live.
1311 Note that even if REG does not remain alive after this insn,
1312 we must mark it here as live, to ensure a conflict between
1313 REG and any other regs set in this insn that really do live.
1314 This is because those other regs could be considered after this.
1316 REG might actually be something other than a register;
1317 if so, we do nothing.
1319 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1320 a REG_INC note was found for it).
1322 CLOBBERs are processed here by calling mark_reg_clobber. */
1325 mark_reg_store (orig_reg
, setter
)
1326 rtx orig_reg
, setter
;
1329 register rtx reg
= orig_reg
;
1331 /* WORD is which word of a multi-register group is being stored.
1332 For the case where the store is actually into a SUBREG of REG.
1333 Except we don't use it; I believe the entire REG needs to be
1337 if (GET_CODE (reg
) == SUBREG
)
1339 word
= SUBREG_WORD (reg
);
1340 reg
= SUBREG_REG (reg
);
1343 if (GET_CODE (reg
) != REG
)
1346 if (setter
&& GET_CODE (setter
) == CLOBBER
)
1348 /* A clobber of a register should be processed here too. */
1349 mark_reg_clobber (orig_reg
, setter
);
1353 regs_set
[n_regs_set
++] = reg
;
1356 set_preference (reg
, SET_SRC (setter
));
1358 regno
= REGNO (reg
);
1360 if (reg_renumber
[regno
] >= 0)
1361 regno
= reg_renumber
[regno
] /* + word */;
1363 /* Either this is one of the max_allocno pseudo regs not allocated,
1364 or it is or has a hardware reg. First handle the pseudo-regs. */
1365 if (regno
>= FIRST_PSEUDO_REGISTER
)
1367 if (reg_allocno
[regno
] >= 0)
1369 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1370 record_one_conflict (regno
);
1373 /* Handle hardware regs (and pseudos allocated to hard regs). */
1374 else if (! fixed_regs
[regno
])
1376 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1377 while (regno
< last
)
1379 record_one_conflict (regno
);
1380 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1386 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1389 mark_reg_clobber (reg
, setter
)
1394 /* WORD is which word of a multi-register group is being stored.
1395 For the case where the store is actually into a SUBREG of REG.
1396 Except we don't use it; I believe the entire REG needs to be
1400 if (GET_CODE (setter
) != CLOBBER
)
1403 if (GET_CODE (reg
) == SUBREG
)
1405 word
= SUBREG_WORD (reg
);
1406 reg
= SUBREG_REG (reg
);
1409 if (GET_CODE (reg
) != REG
)
1412 regs_set
[n_regs_set
++] = reg
;
1414 regno
= REGNO (reg
);
1416 if (reg_renumber
[regno
] >= 0)
1417 regno
= reg_renumber
[regno
] /* + word */;
1419 /* Either this is one of the max_allocno pseudo regs not allocated,
1420 or it is or has a hardware reg. First handle the pseudo-regs. */
1421 if (regno
>= FIRST_PSEUDO_REGISTER
)
1423 if (reg_allocno
[regno
] >= 0)
1425 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1426 record_one_conflict (regno
);
1429 /* Handle hardware regs (and pseudos allocated to hard regs). */
1430 else if (! fixed_regs
[regno
])
1432 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1433 while (regno
< last
)
1435 record_one_conflict (regno
);
1436 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1442 /* Record that REG has conflicts with all the regs currently live.
1443 Do not mark REG itself as live. */
1446 mark_reg_conflicts (reg
)
1451 if (GET_CODE (reg
) == SUBREG
)
1452 reg
= SUBREG_REG (reg
);
1454 if (GET_CODE (reg
) != REG
)
1457 regno
= REGNO (reg
);
1459 if (reg_renumber
[regno
] >= 0)
1460 regno
= reg_renumber
[regno
];
1462 /* Either this is one of the max_allocno pseudo regs not allocated,
1463 or it is or has a hardware reg. First handle the pseudo-regs. */
1464 if (regno
>= FIRST_PSEUDO_REGISTER
)
1466 if (reg_allocno
[regno
] >= 0)
1467 record_one_conflict (regno
);
1469 /* Handle hardware regs (and pseudos allocated to hard regs). */
1470 else if (! fixed_regs
[regno
])
1472 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1473 while (regno
< last
)
1475 record_one_conflict (regno
);
1481 /* Mark REG as being dead (following the insn being scanned now).
1482 Store a 0 in regs_live or allocnos_live for this register. */
1485 mark_reg_death (reg
)
1488 register int regno
= REGNO (reg
);
1490 /* For pseudo reg, see if it has been assigned a hardware reg. */
1491 if (reg_renumber
[regno
] >= 0)
1492 regno
= reg_renumber
[regno
];
1494 /* Either this is one of the max_allocno pseudo regs not allocated,
1495 or it is a hardware reg. First handle the pseudo-regs. */
1496 if (regno
>= FIRST_PSEUDO_REGISTER
)
1498 if (reg_allocno
[regno
] >= 0)
1499 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1501 /* Handle hardware regs (and pseudos allocated to hard regs). */
1502 else if (! fixed_regs
[regno
])
1504 /* Pseudo regs already assigned hardware regs are treated
1505 almost the same as explicit hardware regs. */
1506 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1507 while (regno
< last
)
1509 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1515 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1516 for the value stored in it. MODE determines how many consecutive
1517 registers are actually in use. Do not record conflicts;
1518 it is assumed that the caller will do that. */
1521 mark_reg_live_nc (regno
, mode
)
1523 enum machine_mode mode
;
1525 register int last
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1526 while (regno
< last
)
1528 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1533 /* Try to set a preference for an allocno to a hard register.
1534 We are passed DEST and SRC which are the operands of a SET. It is known
1535 that SRC is a register. If SRC or the first operand of SRC is a register,
1536 try to set a preference. If one of the two is a hard register and the other
1537 is a pseudo-register, mark the preference.
1539 Note that we are not as aggressive as local-alloc in trying to tie a
1540 pseudo-register to a hard register. */
1543 set_preference (dest
, src
)
1546 int src_regno
, dest_regno
;
1547 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1548 to compensate for subregs in SRC or DEST. */
1553 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1554 src
= XEXP (src
, 0), copy
= 0;
1556 /* Get the reg number for both SRC and DEST.
1557 If neither is a reg, give up. */
1559 if (GET_CODE (src
) == REG
)
1560 src_regno
= REGNO (src
);
1561 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1563 src_regno
= REGNO (SUBREG_REG (src
));
1564 offset
+= SUBREG_WORD (src
);
1569 if (GET_CODE (dest
) == REG
)
1570 dest_regno
= REGNO (dest
);
1571 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1573 dest_regno
= REGNO (SUBREG_REG (dest
));
1574 offset
-= SUBREG_WORD (dest
);
1579 /* Convert either or both to hard reg numbers. */
1581 if (reg_renumber
[src_regno
] >= 0)
1582 src_regno
= reg_renumber
[src_regno
];
1584 if (reg_renumber
[dest_regno
] >= 0)
1585 dest_regno
= reg_renumber
[dest_regno
];
1587 /* Now if one is a hard reg and the other is a global pseudo
1588 then give the other a preference. */
1590 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1591 && reg_allocno
[src_regno
] >= 0)
1593 dest_regno
-= offset
;
1594 if (dest_regno
>= 0 && dest_regno
< FIRST_PSEUDO_REGISTER
)
1597 SET_REGBIT (hard_reg_copy_preferences
,
1598 reg_allocno
[src_regno
], dest_regno
);
1600 SET_REGBIT (hard_reg_preferences
,
1601 reg_allocno
[src_regno
], dest_regno
);
1602 for (i
= dest_regno
;
1603 i
< dest_regno
+ HARD_REGNO_NREGS (dest_regno
, GET_MODE (dest
));
1605 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1609 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1610 && reg_allocno
[dest_regno
] >= 0)
1612 src_regno
+= offset
;
1613 if (src_regno
>= 0 && src_regno
< FIRST_PSEUDO_REGISTER
)
1616 SET_REGBIT (hard_reg_copy_preferences
,
1617 reg_allocno
[dest_regno
], src_regno
);
1619 SET_REGBIT (hard_reg_preferences
,
1620 reg_allocno
[dest_regno
], src_regno
);
1622 i
< src_regno
+ HARD_REGNO_NREGS (src_regno
, GET_MODE (src
));
1624 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1629 /* Indicate that hard register number FROM was eliminated and replaced with
1630 an offset from hard register number TO. The status of hard registers live
1631 at the start of a basic block is updated by replacing a use of FROM with
1635 mark_elimination (from
, to
)
1640 for (i
= 0; i
< n_basic_blocks
; i
++)
1641 if (REGNO_REG_SET_P (basic_block_live_at_start
[i
], from
))
1643 CLEAR_REGNO_REG_SET (basic_block_live_at_start
[i
], from
);
1644 SET_REGNO_REG_SET (basic_block_live_at_start
[i
], to
);
1648 /* Print debugging trace information if -greg switch is given,
1649 showing the information on which the allocation decisions are based. */
1652 dump_conflicts (file
)
1656 register int has_preferences
;
1657 fprintf (file
, ";; %d regs to allocate:", max_allocno
);
1658 for (i
= 0; i
< max_allocno
; i
++)
1661 fprintf (file
, " %d", allocno_reg
[allocno_order
[i
]]);
1662 for (j
= 0; j
< max_regno
; j
++)
1663 if (reg_allocno
[j
] == allocno_order
[i
]
1664 && j
!= allocno_reg
[allocno_order
[i
]])
1665 fprintf (file
, "+%d", j
);
1666 if (allocno_size
[allocno_order
[i
]] != 1)
1667 fprintf (file
, " (%d)", allocno_size
[allocno_order
[i
]]);
1669 fprintf (file
, "\n");
1671 for (i
= 0; i
< max_allocno
; i
++)
1674 fprintf (file
, ";; %d conflicts:", allocno_reg
[i
]);
1675 for (j
= 0; j
< max_allocno
; j
++)
1676 if (CONFLICTP (i
, j
) || CONFLICTP (j
, i
))
1677 fprintf (file
, " %d", allocno_reg
[j
]);
1678 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1679 if (TEST_HARD_REG_BIT (hard_reg_conflicts
[i
], j
))
1680 fprintf (file
, " %d", j
);
1681 fprintf (file
, "\n");
1683 has_preferences
= 0;
1684 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1685 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1686 has_preferences
= 1;
1688 if (! has_preferences
)
1690 fprintf (file
, ";; %d preferences:", allocno_reg
[i
]);
1691 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1692 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1693 fprintf (file
, " %d", j
);
1694 fprintf (file
, "\n");
1696 fprintf (file
, "\n");
1700 dump_global_regs (file
)
1705 fprintf (file
, ";; Register dispositions:\n");
1706 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1707 if (reg_renumber
[i
] >= 0)
1709 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1711 fprintf (file
, "\n");
1714 fprintf (file
, "\n\n;; Hard regs used: ");
1715 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1716 if (regs_ever_live
[i
])
1717 fprintf (file
, " %d", i
);
1718 fprintf (file
, "\n\n");