1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 88, 91, 94, 96-99, 2000 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
26 #include "hard-reg-set.h"
30 #include "basic-block.h"
33 #include "insn-config.h"
38 /* This pass of the compiler performs global register allocation.
39 It assigns hard register numbers to all the pseudo registers
40 that were not handled in local_alloc. Assignments are recorded
41 in the vector reg_renumber, not by changing the rtl code.
42 (Such changes are made by final). The entry point is
43 the function global_alloc.
45 After allocation is complete, the reload pass is run as a subroutine
46 of this pass, so that when a pseudo reg loses its hard reg due to
47 spilling it is possible to make a second attempt to find a hard
48 reg for it. The reload pass is independent in other respects
49 and it is run even when stupid register allocation is in use.
51 1. Assign allocation-numbers (allocnos) to the pseudo-registers
52 still needing allocations and to the pseudo-registers currently
53 allocated by local-alloc which may be spilled by reload.
54 Set up tables reg_allocno and allocno_reg to map
55 reg numbers to allocnos and vice versa.
56 max_allocno gets the number of allocnos in use.
58 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
59 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
60 for conflicts between allocnos and explicit hard register use
61 (which includes use of pseudo-registers allocated by local_alloc).
63 3. For each basic block
64 walk forward through the block, recording which
65 pseudo-registers and which hardware registers are live.
66 Build the conflict matrix between the pseudo-registers
67 and another of pseudo-registers versus hardware registers.
68 Also record the preferred hardware registers
69 for each pseudo-register.
71 4. Sort a table of the allocnos into order of
72 desirability of the variables.
74 5. Allocate the variables in that order; each if possible into
75 a preferred register, else into another register. */
77 /* Number of pseudo-registers which are candidates for allocation. */
79 static int max_allocno
;
81 /* Indexed by (pseudo) reg number, gives the allocno, or -1
82 for pseudo registers which are not to be allocated. */
84 static int *reg_allocno
;
89 /* Gives the number of consecutive hard registers needed by that
93 /* Number of calls crossed by each allocno. */
96 /* Number of refs (weighted) to each allocno. */
99 /* Guess at live length of each allocno.
100 This is actually the max of the live lengths of the regs. */
103 /* Set of hard regs conflicting with allocno N. */
105 HARD_REG_SET hard_reg_conflicts
;
107 /* Set of hard regs preferred by allocno N.
108 This is used to make allocnos go into regs that are copied to or from them,
109 when possible, to reduce register shuffling. */
111 HARD_REG_SET hard_reg_preferences
;
113 /* Similar, but just counts register preferences made in simple copy
114 operations, rather than arithmetic. These are given priority because
115 we can always eliminate an insn by using these, but using a register
116 in the above list won't always eliminate an insn. */
118 HARD_REG_SET hard_reg_copy_preferences
;
120 /* Similar to hard_reg_preferences, but includes bits for subsequent
121 registers when an allocno is multi-word. The above variable is used for
122 allocation while this is used to build reg_someone_prefers, below. */
124 HARD_REG_SET hard_reg_full_preferences
;
126 /* Set of hard registers that some later allocno has a preference for. */
128 HARD_REG_SET regs_someone_prefers
;
131 static struct allocno
*allocno
;
133 /* A vector of the integers from 0 to max_allocno-1,
134 sorted in the order of first-to-be-allocated first. */
136 static int *allocno_order
;
138 /* Indexed by (pseudo) reg number, gives the number of another
139 lower-numbered pseudo reg which can share a hard reg with this pseudo
140 *even if the two pseudos would otherwise appear to conflict*. */
142 static int *reg_may_share
;
144 /* Define the number of bits in each element of `conflicts' and what
145 type that element has. We use the largest integer format on the
148 #define INT_BITS HOST_BITS_PER_WIDE_INT
149 #define INT_TYPE HOST_WIDE_INT
151 /* max_allocno by max_allocno array of bits,
152 recording whether two allocno's conflict (can't go in the same
155 `conflicts' is symmetric after the call to mirror_conflicts. */
157 static INT_TYPE
*conflicts
;
159 /* Number of ints require to hold max_allocno bits.
160 This is the length of a row in `conflicts'. */
162 static int allocno_row_words
;
164 /* Two macros to test or store 1 in an element of `conflicts'. */
166 #define CONFLICTP(I, J) \
167 (conflicts[(I) * allocno_row_words + (unsigned)(J) / INT_BITS] \
168 & ((INT_TYPE) 1 << ((unsigned)(J) % INT_BITS)))
170 #define SET_CONFLICT(I, J) \
171 (conflicts[(I) * allocno_row_words + (unsigned)(J) / INT_BITS] \
172 |= ((INT_TYPE) 1 << ((unsigned)(J) % INT_BITS)))
174 /* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
176 #define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
180 INT_TYPE *p_ = (ALLOCNO_SET); \
182 for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
183 i_--, allocno_ += INT_BITS) \
185 unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
187 for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
195 /* This doesn't work for non-GNU C due to the way CODE is macro expanded. */
197 /* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to
198 the conflicting allocno, and execute CODE. This macro assumes that
199 mirror_conflicts has been run. */
200 #define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\
201 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\
205 /* Set of hard regs currently live (during scan of all insns). */
207 static HARD_REG_SET hard_regs_live
;
209 /* Set of registers that global-alloc isn't supposed to use. */
211 static HARD_REG_SET no_global_alloc_regs
;
213 /* Set of registers used so far. */
215 static HARD_REG_SET regs_used_so_far
;
217 /* Number of refs (weighted) to each hard reg, as used by local alloc.
218 It is zero for a reg that contains global pseudos or is explicitly used. */
220 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
222 /* Guess at live length of each hard reg, as used by local alloc.
223 This is actually the sum of the live lengths of the specific regs. */
225 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
227 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
228 for vector element I, and hard register number J. */
230 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (allocno[I].TABLE, J)
232 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
234 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
236 /* Bit mask for allocnos live at current point in the scan. */
238 static INT_TYPE
*allocnos_live
;
240 /* Test, set or clear bit number I in allocnos_live,
241 a bit vector indexed by allocno. */
243 #define ALLOCNO_LIVE_P(I) \
244 (allocnos_live[(unsigned)(I) / INT_BITS] \
245 & ((INT_TYPE) 1 << ((unsigned)(I) % INT_BITS)))
247 #define SET_ALLOCNO_LIVE(I) \
248 (allocnos_live[(unsigned)(I) / INT_BITS] \
249 |= ((INT_TYPE) 1 << ((unsigned)(I) % INT_BITS)))
251 #define CLEAR_ALLOCNO_LIVE(I) \
252 (allocnos_live[(unsigned)(I) / INT_BITS] \
253 &= ~((INT_TYPE) 1 << ((unsigned)(I) % INT_BITS)))
255 /* This is turned off because it doesn't work right for DImode.
256 (And it is only used for DImode, so the other cases are worthless.)
257 The problem is that it isn't true that there is NO possibility of conflict;
258 only that there is no conflict if the two pseudos get the exact same regs.
259 If they were allocated with a partial overlap, there would be a conflict.
260 We can't safely turn off the conflict unless we have another way to
261 prevent the partial overlap.
263 Idea: change hard_reg_conflicts so that instead of recording which
264 hard regs the allocno may not overlap, it records where the allocno
265 may not start. Change both where it is used and where it is updated.
266 Then there is a way to record that (reg:DI 108) may start at 10
267 but not at 9 or 11. There is still the question of how to record
268 this semi-conflict between two pseudos. */
270 /* Reg pairs for which conflict after the current insn
271 is inhibited by a REG_NO_CONFLICT note.
272 If the table gets full, we ignore any other notes--that is conservative. */
273 #define NUM_NO_CONFLICT_PAIRS 4
274 /* Number of pairs in use in this insn. */
275 int n_no_conflict_pairs
;
276 static struct { int allocno1
, allocno2
;}
277 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
280 /* Record all regs that are set in any one insn.
281 Communication from mark_reg_{store,clobber} and global_conflicts. */
283 static rtx
*regs_set
;
284 static int n_regs_set
;
286 /* All registers that can be eliminated. */
288 static HARD_REG_SET eliminable_regset
;
290 static int allocno_compare
PARAMS ((const PTR
, const PTR
));
291 static void global_conflicts
PARAMS ((void));
292 static void mirror_conflicts
PARAMS ((void));
293 static void expand_preferences
PARAMS ((void));
294 static void prune_preferences
PARAMS ((void));
295 static void find_reg
PARAMS ((int, HARD_REG_SET
, int, int, int));
296 static void record_one_conflict
PARAMS ((int));
297 static void record_conflicts
PARAMS ((int *, int));
298 static void mark_reg_store
PARAMS ((rtx
, rtx
, void *));
299 static void mark_reg_clobber
PARAMS ((rtx
, rtx
, void *));
300 static void mark_reg_conflicts
PARAMS ((rtx
));
301 static void mark_reg_death
PARAMS ((rtx
));
302 static void mark_reg_live_nc
PARAMS ((int, enum machine_mode
));
303 static void set_preference
PARAMS ((rtx
, rtx
));
304 static void dump_conflicts
PARAMS ((FILE *));
305 static void reg_becomes_live
PARAMS ((rtx
, rtx
, void *));
306 static void reg_dies
PARAMS ((int, enum machine_mode
,
307 struct insn_chain
*));
309 /* Perform allocation of pseudo-registers not allocated by local_alloc.
310 FILE is a file to output debugging information on,
311 or zero if such output is not desired.
313 Return value is nonzero if reload failed
314 and we must not do any more for this function. */
321 #ifdef ELIMINABLE_REGS
322 static struct {int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
325 = (! flag_omit_frame_pointer
326 #ifdef EXIT_IGNORE_STACK
327 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
329 || FRAME_POINTER_REQUIRED
);
336 /* A machine may have certain hard registers that
337 are safe to use only within a basic block. */
339 CLEAR_HARD_REG_SET (no_global_alloc_regs
);
341 /* Build the regset of all eliminable registers and show we can't use those
342 that we already know won't be eliminated. */
343 #ifdef ELIMINABLE_REGS
344 for (i
= 0; i
< sizeof eliminables
/ sizeof eliminables
[0]; i
++)
346 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
348 if (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
349 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
))
350 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
352 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
353 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
355 SET_HARD_REG_BIT (no_global_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
359 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
361 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
364 /* Track which registers have already been used. Start with registers
365 explicitly in the rtl, then registers allocated by local register
368 CLEAR_HARD_REG_SET (regs_used_so_far
);
369 #ifdef LEAF_REGISTERS
370 /* If we are doing the leaf function optimization, and this is a leaf
371 function, it means that the registers that take work to save are those
372 that need a register window. So prefer the ones that can be used in
376 static char leaf_regs
[] = LEAF_REGISTERS
;
378 if (only_leaf_regs_used () && leaf_function_p ())
379 cheap_regs
= leaf_regs
;
381 cheap_regs
= call_used_regs
;
382 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
383 if (regs_ever_live
[i
] || cheap_regs
[i
])
384 SET_HARD_REG_BIT (regs_used_so_far
, i
);
387 /* We consider registers that do not have to be saved over calls as if
388 they were already used since there is no cost in using them. */
389 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
390 if (regs_ever_live
[i
] || call_used_regs
[i
])
391 SET_HARD_REG_BIT (regs_used_so_far
, i
);
394 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
395 if (reg_renumber
[i
] >= 0)
396 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
398 /* Establish mappings from register number to allocation number
399 and vice versa. In the process, count the allocnos. */
401 reg_allocno
= (int *) xmalloc (max_regno
* sizeof (int));
403 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
406 /* Initialize the shared-hard-reg mapping
407 from the list of pairs that may share. */
408 reg_may_share
= (int *) xcalloc (max_regno
, sizeof (int));
409 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
411 int r1
= REGNO (XEXP (x
, 0));
412 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
414 reg_may_share
[r1
] = r2
;
416 reg_may_share
[r2
] = r1
;
419 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
420 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
421 that we are supposed to refrain from putting in a hard reg.
422 -2 means do make an allocno but don't allocate it. */
423 if (REG_N_REFS (i
) != 0 && REG_LIVE_LENGTH (i
) != -1
424 /* Don't allocate pseudos that cross calls,
425 if this function receives a nonlocal goto. */
426 && (! current_function_has_nonlocal_label
427 || REG_N_CALLS_CROSSED (i
) == 0))
429 if (reg_renumber
[i
] < 0 && reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
430 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
432 reg_allocno
[i
] = max_allocno
++;
433 if (REG_LIVE_LENGTH (i
) == 0)
439 allocno
= (struct allocno
*) xcalloc (max_allocno
, sizeof (struct allocno
));
441 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
442 if (reg_allocno
[i
] >= 0)
444 int num
= reg_allocno
[i
];
445 allocno
[num
].reg
= i
;
446 allocno
[num
].size
= PSEUDO_REGNO_SIZE (i
);
447 allocno
[num
].calls_crossed
+= REG_N_CALLS_CROSSED (i
);
448 allocno
[num
].n_refs
+= REG_N_REFS (i
);
449 if (allocno
[num
].live_length
< REG_LIVE_LENGTH (i
))
450 allocno
[num
].live_length
= REG_LIVE_LENGTH (i
);
453 /* Calculate amount of usage of each hard reg by pseudos
454 allocated by local-alloc. This is to see if we want to
456 bzero ((char *) local_reg_live_length
, sizeof local_reg_live_length
);
457 bzero ((char *) local_reg_n_refs
, sizeof local_reg_n_refs
);
458 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
459 if (reg_renumber
[i
] >= 0)
461 int regno
= reg_renumber
[i
];
462 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (i
));
465 for (j
= regno
; j
< endregno
; j
++)
467 local_reg_n_refs
[j
] += REG_N_REFS (i
);
468 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
472 /* We can't override local-alloc for a reg used not just by local-alloc. */
473 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
474 if (regs_ever_live
[i
])
475 local_reg_n_refs
[i
] = 0;
477 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
479 /* We used to use alloca here, but the size of what it would try to
480 allocate would occasionally cause it to exceed the stack limit and
481 cause unpredictable core dumps. Some examples were > 2Mb in size. */
482 conflicts
= (INT_TYPE
*) xcalloc (max_allocno
* allocno_row_words
,
485 allocnos_live
= (INT_TYPE
*) xmalloc (allocno_row_words
* sizeof (INT_TYPE
));
487 /* If there is work to be done (at least one reg to allocate),
488 perform global conflict analysis and allocate the regs. */
492 /* Scan all the insns and compute the conflicts among allocnos
493 and between allocnos and hard regs. */
499 /* Eliminate conflicts between pseudos and eliminable registers. If
500 the register is not eliminated, the pseudo won't really be able to
501 live in the eliminable register, so the conflict doesn't matter.
502 If we do eliminate the register, the conflict will no longer exist.
503 So in either case, we can ignore the conflict. Likewise for
506 for (i
= 0; i
< (size_t) max_allocno
; i
++)
508 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_conflicts
,
510 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_copy_preferences
,
512 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_preferences
,
516 /* Try to expand the preferences by merging them between allocnos. */
518 expand_preferences ();
520 /* Determine the order to allocate the remaining pseudo registers. */
522 allocno_order
= (int *) xmalloc (max_allocno
* sizeof (int));
523 for (i
= 0; i
< (size_t) max_allocno
; i
++)
524 allocno_order
[i
] = i
;
526 /* Default the size to 1, since allocno_compare uses it to divide by.
527 Also convert allocno_live_length of zero to -1. A length of zero
528 can occur when all the registers for that allocno have reg_live_length
529 equal to -2. In this case, we want to make an allocno, but not
530 allocate it. So avoid the divide-by-zero and set it to a low
533 for (i
= 0; i
< (size_t) max_allocno
; i
++)
535 if (allocno
[i
].size
== 0)
537 if (allocno
[i
].live_length
== 0)
538 allocno
[i
].live_length
= -1;
541 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
543 prune_preferences ();
546 dump_conflicts (file
);
548 /* Try allocating them, one by one, in that order,
549 except for parameters marked with reg_live_length[regno] == -2. */
551 for (i
= 0; i
< (size_t) max_allocno
; i
++)
552 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] < 0
553 && REG_LIVE_LENGTH (allocno
[allocno_order
[i
]].reg
) >= 0)
555 /* If we have more than one register class,
556 first try allocating in the class that is cheapest
557 for this pseudo-reg. If that fails, try any reg. */
558 if (N_REG_CLASSES
> 1)
560 find_reg (allocno_order
[i
], 0, 0, 0, 0);
561 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
564 if (reg_alternate_class (allocno
[allocno_order
[i
]].reg
) != NO_REGS
)
565 find_reg (allocno_order
[i
], 0, 1, 0, 0);
568 free (allocno_order
);
571 /* Do the reloads now while the allocno data still exist, so that we can
572 try to assign new hard regs to any pseudo regs that are spilled. */
574 #if 0 /* We need to eliminate regs even if there is no rtl code,
575 for the sake of debugging information. */
576 if (n_basic_blocks
> 0)
579 build_insn_chain (get_insns ());
580 retval
= reload (get_insns (), 1, file
);
585 free (reg_may_share
);
588 free (allocnos_live
);
593 /* Sort predicate for ordering the allocnos.
594 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
597 allocno_compare (v1p
, v2p
)
601 int v1
= *(const int *)v1p
, v2
= *(const int *)v2p
;
602 /* Note that the quotient will never be bigger than
603 the value of floor_log2 times the maximum number of
604 times a register can occur in one insn (surely less than 100).
605 Multiplying this by 10000 can't overflow. */
607 = (((double) (floor_log2 (allocno
[v1
].n_refs
) * allocno
[v1
].n_refs
)
608 / allocno
[v1
].live_length
)
609 * 10000 * allocno
[v1
].size
);
611 = (((double) (floor_log2 (allocno
[v2
].n_refs
) * allocno
[v2
].n_refs
)
612 / allocno
[v2
].live_length
)
613 * 10000 * allocno
[v2
].size
);
617 /* If regs are equally good, sort by allocno,
618 so that the results of qsort leave nothing to chance. */
622 /* Scan the rtl code and record all conflicts and register preferences in the
623 conflict matrices and preference tables. */
630 int *block_start_allocnos
;
632 /* Make a vector that mark_reg_{store,clobber} will store in. */
633 regs_set
= (rtx
*) xmalloc (max_parallel
* sizeof (rtx
) * 2);
635 block_start_allocnos
= (int *) xmalloc (max_allocno
* sizeof (int));
637 for (b
= 0; b
< n_basic_blocks
; b
++)
639 bzero ((char *) allocnos_live
, allocno_row_words
* sizeof (INT_TYPE
));
641 /* Initialize table of registers currently live
642 to the state at the beginning of this basic block.
643 This also marks the conflicts among hard registers
644 and any allocnos that are live.
646 For pseudo-regs, there is only one bit for each one
647 no matter how many hard regs it occupies.
648 This is ok; we know the size from PSEUDO_REGNO_SIZE.
649 For explicit hard regs, we cannot know the size that way
650 since one hard reg can be used with various sizes.
651 Therefore, we must require that all the hard regs
652 implicitly live as part of a multi-word hard reg
653 are explicitly marked in basic_block_live_at_start. */
656 register regset old
= BASIC_BLOCK (b
)->global_live_at_start
;
659 REG_SET_TO_HARD_REG_SET (hard_regs_live
, old
);
660 EXECUTE_IF_SET_IN_REG_SET (old
, FIRST_PSEUDO_REGISTER
, i
,
662 register int a
= reg_allocno
[i
];
665 SET_ALLOCNO_LIVE (a
);
666 block_start_allocnos
[ax
++] = a
;
668 else if ((a
= reg_renumber
[i
]) >= 0)
670 (a
, PSEUDO_REGNO_MODE (i
));
673 /* Record that each allocno now live conflicts with each hard reg
676 It is not necessary to mark any conflicts between pseudos as
677 this point, even for pseudos which are live at the start of
680 Given two pseudos X and Y and any point in the CFG P.
682 On any path to point P where X and Y are live one of the
683 following conditions must be true:
685 1. X is live at some instruction on the path that
688 2. Y is live at some instruction on the path that
691 3. Either X or Y is not evaluted on the path to P
692 (ie it is used uninitialized) and thus the
693 conflict can be ignored.
695 In cases #1 and #2 the conflict will be recorded when we
696 scan the instruction that makes either X or Y become live. */
697 record_conflicts (block_start_allocnos
, ax
);
701 /* Pseudos can't go in stack regs at the start of a basic block
702 that is reached by an abnormal edge. */
705 for (e
= BASIC_BLOCK (b
)->pred
; e
; e
= e
->pred_next
)
706 if (e
->flags
& EDGE_ABNORMAL
)
709 for (ax
= FIRST_STACK_REG
; ax
<= LAST_STACK_REG
; ax
++)
710 record_one_conflict (ax
);
715 insn
= BLOCK_HEAD (b
);
717 /* Scan the code of this basic block, noting which allocnos
718 and hard regs are born or die. When one is born,
719 record a conflict with all others currently live. */
723 register RTX_CODE code
= GET_CODE (insn
);
726 /* Make regs_set an empty set. */
730 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
735 for (link
= REG_NOTES (insn
);
736 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
737 link
= XEXP (link
, 1))
738 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
740 no_conflict_pairs
[i
].allocno1
741 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
742 no_conflict_pairs
[i
].allocno2
743 = reg_allocno
[REGNO (XEXP (link
, 0))];
748 /* Mark any registers clobbered by INSN as live,
749 so they conflict with the inputs. */
751 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
753 /* Mark any registers dead after INSN as dead now. */
755 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
756 if (REG_NOTE_KIND (link
) == REG_DEAD
)
757 mark_reg_death (XEXP (link
, 0));
759 /* Mark any registers set in INSN as live,
760 and mark them as conflicting with all other live regs.
761 Clobbers are processed again, so they conflict with
762 the registers that are set. */
764 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
767 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
768 if (REG_NOTE_KIND (link
) == REG_INC
)
769 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
772 /* If INSN has multiple outputs, then any reg that dies here
773 and is used inside of an output
774 must conflict with the other outputs.
776 It is unsafe to use !single_set here since it will ignore an
777 unused output. Just because an output is unused does not mean
778 the compiler can assume the side effect will not occur.
779 Consider if REG appears in the address of an output and we
780 reload the output. If we allocate REG to the same hard
781 register as an unused output we could set the hard register
782 before the output reload insn. */
783 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
784 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
785 if (REG_NOTE_KIND (link
) == REG_DEAD
)
787 int used_in_output
= 0;
789 rtx reg
= XEXP (link
, 0);
791 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
793 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
794 if (GET_CODE (set
) == SET
795 && GET_CODE (SET_DEST (set
)) != REG
796 && !rtx_equal_p (reg
, SET_DEST (set
))
797 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
801 mark_reg_conflicts (reg
);
804 /* Mark any registers set in INSN and then never used. */
806 while (n_regs_set
> 0)
807 if (find_regno_note (insn
, REG_UNUSED
,
808 REGNO (regs_set
[--n_regs_set
])))
809 mark_reg_death (regs_set
[n_regs_set
]);
812 if (insn
== BLOCK_END (b
))
814 insn
= NEXT_INSN (insn
);
819 free (block_start_allocnos
);
822 /* Expand the preference information by looking for cases where one allocno
823 dies in an insn that sets an allocno. If those two allocnos don't conflict,
824 merge any preferences between those allocnos. */
827 expand_preferences ()
833 /* We only try to handle the most common cases here. Most of the cases
834 where this wins are reg-reg copies. */
836 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
837 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
838 && (set
= single_set (insn
)) != 0
839 && GET_CODE (SET_DEST (set
)) == REG
840 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
841 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
842 if (REG_NOTE_KIND (link
) == REG_DEAD
843 && GET_CODE (XEXP (link
, 0)) == REG
844 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
845 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
846 reg_allocno
[REGNO (XEXP (link
, 0))]))
848 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
849 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
851 if (XEXP (link
, 0) == SET_SRC (set
))
853 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_copy_preferences
,
854 allocno
[a2
].hard_reg_copy_preferences
);
855 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_copy_preferences
,
856 allocno
[a1
].hard_reg_copy_preferences
);
859 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_preferences
,
860 allocno
[a2
].hard_reg_preferences
);
861 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_preferences
,
862 allocno
[a1
].hard_reg_preferences
);
863 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_full_preferences
,
864 allocno
[a2
].hard_reg_full_preferences
);
865 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_full_preferences
,
866 allocno
[a1
].hard_reg_full_preferences
);
870 /* Prune the preferences for global registers to exclude registers that cannot
873 Compute `regs_someone_prefers', which is a bitmask of the hard registers
874 that are preferred by conflicting registers of lower priority. If possible,
875 we will avoid using these registers. */
882 int *allocno_to_order
= (int *) xmalloc (max_allocno
* sizeof (int));
884 /* Scan least most important to most important.
885 For each allocno, remove from preferences registers that cannot be used,
886 either because of conflicts or register type. Then compute all registers
887 preferred by each lower-priority register that conflicts. */
889 for (i
= max_allocno
- 1; i
>= 0; i
--)
893 num
= allocno_order
[i
];
894 allocno_to_order
[num
] = i
;
895 COPY_HARD_REG_SET (temp
, allocno
[num
].hard_reg_conflicts
);
897 if (allocno
[num
].calls_crossed
== 0)
898 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
900 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
902 IOR_COMPL_HARD_REG_SET
904 reg_class_contents
[(int) reg_preferred_class (allocno
[num
].reg
)]);
906 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, temp
);
907 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, temp
);
908 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_full_preferences
, temp
);
911 for (i
= max_allocno
- 1; i
>= 0; i
--)
913 /* Merge in the preferences of lower-priority registers (they have
914 already been pruned). If we also prefer some of those registers,
915 don't exclude them unless we are of a smaller size (in which case
916 we want to give the lower-priority allocno the first chance for
918 HARD_REG_SET temp
, temp2
;
921 num
= allocno_order
[i
];
923 CLEAR_HARD_REG_SET (temp
);
924 CLEAR_HARD_REG_SET (temp2
);
926 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ num
* allocno_row_words
,
929 if (allocno_to_order
[allocno2
] > i
)
931 if (allocno
[allocno2
].size
<= allocno
[num
].size
)
932 IOR_HARD_REG_SET (temp
,
933 allocno
[allocno2
].hard_reg_full_preferences
);
935 IOR_HARD_REG_SET (temp2
,
936 allocno
[allocno2
].hard_reg_full_preferences
);
940 AND_COMPL_HARD_REG_SET (temp
, allocno
[num
].hard_reg_full_preferences
);
941 IOR_HARD_REG_SET (temp
, temp2
);
942 COPY_HARD_REG_SET (allocno
[num
].regs_someone_prefers
, temp
);
944 free (allocno_to_order
);
947 /* Assign a hard register to allocno NUM; look for one that is the beginning
948 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
949 The registers marked in PREFREGS are tried first.
951 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
952 be used for this allocation.
954 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
955 Otherwise ignore that preferred class and use the alternate class.
957 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
958 will have to be saved and restored at calls.
960 RETRYING is nonzero if this is called from retry_global_alloc.
962 If we find one, record it in reg_renumber.
963 If not, do nothing. */
966 find_reg (num
, losers
, alt_regs_p
, accept_call_clobbered
, retrying
)
970 int accept_call_clobbered
;
973 register int i
, best_reg
, pass
;
975 register /* Declare it register if it's a scalar. */
977 HARD_REG_SET used
, used1
, used2
;
979 enum reg_class
class = (alt_regs_p
980 ? reg_alternate_class (allocno
[num
].reg
)
981 : reg_preferred_class (allocno
[num
].reg
));
982 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno
[num
].reg
);
984 if (accept_call_clobbered
)
985 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
986 else if (allocno
[num
].calls_crossed
== 0)
987 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
989 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
991 /* Some registers should not be allocated in global-alloc. */
992 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
994 IOR_HARD_REG_SET (used1
, losers
);
996 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
997 COPY_HARD_REG_SET (used2
, used1
);
999 IOR_HARD_REG_SET (used1
, allocno
[num
].hard_reg_conflicts
);
1001 #ifdef CLASS_CANNOT_CHANGE_SIZE
1002 if (REG_CHANGES_SIZE (allocno
[num
].reg
))
1003 IOR_HARD_REG_SET (used1
,
1004 reg_class_contents
[(int) CLASS_CANNOT_CHANGE_SIZE
]);
1007 /* Try each hard reg to see if it fits. Do this in two passes.
1008 In the first pass, skip registers that are preferred by some other pseudo
1009 to give it a better chance of getting one of those registers. Only if
1010 we can't get a register when excluding those do we take one of them.
1011 However, we never allocate a register for the first time in pass 0. */
1013 COPY_HARD_REG_SET (used
, used1
);
1014 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
1015 IOR_HARD_REG_SET (used
, allocno
[num
].regs_someone_prefers
);
1018 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
1019 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
1023 COPY_HARD_REG_SET (used
, used1
);
1024 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1026 #ifdef REG_ALLOC_ORDER
1027 int regno
= reg_alloc_order
[i
];
1031 if (! TEST_HARD_REG_BIT (used
, regno
)
1032 && HARD_REGNO_MODE_OK (regno
, mode
)
1033 && (allocno
[num
].calls_crossed
== 0
1034 || accept_call_clobbered
1035 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
)))
1038 register int lim
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1041 && ! TEST_HARD_REG_BIT (used
, j
));
1048 #ifndef REG_ALLOC_ORDER
1049 i
= j
; /* Skip starting points we know will lose */
1055 /* See if there is a preferred register with the same class as the register
1056 we allocated above. Making this restriction prevents register
1057 preferencing from creating worse register allocation.
1059 Remove from the preferred registers and conflicting registers. Note that
1060 additional conflicts may have been added after `prune_preferences' was
1063 First do this for those register with copy preferences, then all
1064 preferred registers. */
1066 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, used
);
1067 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_copy_preferences
,
1068 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
1072 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1073 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_copy_preferences
, i
)
1074 && HARD_REGNO_MODE_OK (i
, mode
)
1075 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1076 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1077 REGNO_REG_CLASS (best_reg
))
1078 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1079 REGNO_REG_CLASS (i
))))
1082 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1085 && ! TEST_HARD_REG_BIT (used
, j
)
1086 && (REGNO_REG_CLASS (j
)
1087 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1088 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1089 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1090 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1091 REGNO_REG_CLASS (j
))));
1102 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, used
);
1103 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_preferences
,
1104 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1108 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1109 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_preferences
, i
)
1110 && HARD_REGNO_MODE_OK (i
, mode
)
1111 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1112 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1113 REGNO_REG_CLASS (best_reg
))
1114 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1115 REGNO_REG_CLASS (i
))))
1118 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1121 && ! TEST_HARD_REG_BIT (used
, j
)
1122 && (REGNO_REG_CLASS (j
)
1123 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1124 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1125 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1126 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1127 REGNO_REG_CLASS (j
))));
1138 /* If we haven't succeeded yet, try with caller-saves.
1139 We need not check to see if the current function has nonlocal
1140 labels because we don't put any pseudos that are live over calls in
1141 registers in that case. */
1143 if (flag_caller_saves
&& best_reg
< 0)
1145 /* Did not find a register. If it would be profitable to
1146 allocate a call-clobbered register and save and restore it
1147 around calls, do that. */
1148 if (! accept_call_clobbered
1149 && allocno
[num
].calls_crossed
!= 0
1150 && CALLER_SAVE_PROFITABLE (allocno
[num
].n_refs
,
1151 allocno
[num
].calls_crossed
))
1153 HARD_REG_SET new_losers
;
1155 CLEAR_HARD_REG_SET (new_losers
);
1157 COPY_HARD_REG_SET (new_losers
, losers
);
1159 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1160 find_reg (num
, new_losers
, alt_regs_p
, 1, retrying
);
1161 if (reg_renumber
[allocno
[num
].reg
] >= 0)
1163 caller_save_needed
= 1;
1169 /* If we haven't succeeded yet,
1170 see if some hard reg that conflicts with us
1171 was utilized poorly by local-alloc.
1172 If so, kick out the regs that were put there by local-alloc
1173 so we can use it instead. */
1174 if (best_reg
< 0 && !retrying
1175 /* Let's not bother with multi-reg allocnos. */
1176 && allocno
[num
].size
== 1)
1178 /* Count from the end, to find the least-used ones first. */
1179 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1181 #ifdef REG_ALLOC_ORDER
1182 int regno
= reg_alloc_order
[i
];
1187 if (local_reg_n_refs
[regno
] != 0
1188 /* Don't use a reg no good for this pseudo. */
1189 && ! TEST_HARD_REG_BIT (used2
, regno
)
1190 && HARD_REGNO_MODE_OK (regno
, mode
)
1191 #ifdef CLASS_CANNOT_CHANGE_SIZE
1192 && ! (REG_CHANGES_SIZE (allocno
[num
].reg
)
1193 && (TEST_HARD_REG_BIT
1194 (reg_class_contents
[(int) CLASS_CANNOT_CHANGE_SIZE
],
1199 /* We explicitly evaluate the divide results into temporary
1200 variables so as to avoid excess precision problems that occur
1201 on a i386-unknown-sysv4.2 (unixware) host. */
1203 double tmp1
= ((double) local_reg_n_refs
[regno
]
1204 / local_reg_live_length
[regno
]);
1205 double tmp2
= ((double) allocno
[num
].n_refs
1206 / allocno
[num
].live_length
);
1210 /* Hard reg REGNO was used less in total by local regs
1211 than it would be used by this one allocno! */
1213 for (k
= 0; k
< max_regno
; k
++)
1214 if (reg_renumber
[k
] >= 0)
1216 int r
= reg_renumber
[k
];
1218 = r
+ HARD_REGNO_NREGS (r
, PSEUDO_REGNO_MODE (k
));
1220 if (regno
>= r
&& regno
< endregno
)
1221 reg_renumber
[k
] = -1;
1231 /* Did we find a register? */
1235 register int lim
, j
;
1236 HARD_REG_SET this_reg
;
1238 /* Yes. Record it as the hard register of this pseudo-reg. */
1239 reg_renumber
[allocno
[num
].reg
] = best_reg
;
1240 /* Also of any pseudo-regs that share with it. */
1241 if (reg_may_share
[allocno
[num
].reg
])
1242 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1243 if (reg_allocno
[j
] == num
)
1244 reg_renumber
[j
] = best_reg
;
1246 /* Make a set of the hard regs being allocated. */
1247 CLEAR_HARD_REG_SET (this_reg
);
1248 lim
= best_reg
+ HARD_REGNO_NREGS (best_reg
, mode
);
1249 for (j
= best_reg
; j
< lim
; j
++)
1251 SET_HARD_REG_BIT (this_reg
, j
);
1252 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1253 /* This is no longer a reg used just by local regs. */
1254 local_reg_n_refs
[j
] = 0;
1256 /* For each other pseudo-reg conflicting with this one,
1257 mark it as conflicting with the hard regs this one occupies. */
1259 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ lim
* allocno_row_words
, j
,
1261 IOR_HARD_REG_SET (allocno
[j
].hard_reg_conflicts
, this_reg
);
1266 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1267 Perhaps it had previously seemed not worth a hard reg,
1268 or perhaps its old hard reg has been commandeered for reloads.
1269 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1270 they do not appear to be allocated.
1271 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1274 retry_global_alloc (regno
, forbidden_regs
)
1276 HARD_REG_SET forbidden_regs
;
1278 int allocno
= reg_allocno
[regno
];
1281 /* If we have more than one register class,
1282 first try allocating in the class that is cheapest
1283 for this pseudo-reg. If that fails, try any reg. */
1284 if (N_REG_CLASSES
> 1)
1285 find_reg (allocno
, forbidden_regs
, 0, 0, 1);
1286 if (reg_renumber
[regno
] < 0
1287 && reg_alternate_class (regno
) != NO_REGS
)
1288 find_reg (allocno
, forbidden_regs
, 1, 0, 1);
1290 /* If we found a register, modify the RTL for the register to
1291 show the hard register, and mark that register live. */
1292 if (reg_renumber
[regno
] >= 0)
1294 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1295 mark_home_live (regno
);
1300 /* Record a conflict between register REGNO
1301 and everything currently live.
1302 REGNO must not be a pseudo reg that was allocated
1303 by local_alloc; such numbers must be translated through
1304 reg_renumber before calling here. */
1307 record_one_conflict (regno
)
1312 if (regno
< FIRST_PSEUDO_REGISTER
)
1313 /* When a hard register becomes live,
1314 record conflicts with live pseudo regs. */
1315 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, j
,
1317 SET_HARD_REG_BIT (allocno
[j
].hard_reg_conflicts
, regno
);
1320 /* When a pseudo-register becomes live,
1321 record conflicts first with hard regs,
1322 then with other pseudo regs. */
1324 register int ialloc
= reg_allocno
[regno
];
1325 register int ialloc_prod
= ialloc
* allocno_row_words
;
1326 IOR_HARD_REG_SET (allocno
[ialloc
].hard_reg_conflicts
, hard_regs_live
);
1327 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1331 for (k
= 0; k
< n_no_conflict_pairs
; k
++)
1332 if (! ((j
== no_conflict_pairs
[k
].allocno1
1333 && ialloc
== no_conflict_pairs
[k
].allocno2
)
1335 (j
== no_conflict_pairs
[k
].allocno2
1336 && ialloc
== no_conflict_pairs
[k
].allocno1
)))
1338 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1343 /* Record all allocnos currently live as conflicting
1344 with all hard regs currently live.
1346 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1347 are currently live. Their bits are also flagged in allocnos_live. */
1350 record_conflicts (allocno_vec
, len
)
1351 register int *allocno_vec
;
1355 register int ialloc_prod
;
1359 num
= allocno_vec
[len
];
1360 ialloc_prod
= num
* allocno_row_words
;
1361 IOR_HARD_REG_SET (allocno
[num
].hard_reg_conflicts
, hard_regs_live
);
1365 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1370 int rw
= allocno_row_words
;
1371 int rwb
= rw
* INT_BITS
;
1372 INT_TYPE
*p
= conflicts
;
1373 INT_TYPE
*q0
= conflicts
, *q1
, *q2
;
1374 unsigned INT_TYPE mask
;
1376 for (i
= max_allocno
- 1, mask
= 1; i
>= 0; i
--, mask
<<= 1)
1383 for (j
= allocno_row_words
- 1, q1
= q0
; j
>= 0; j
--, q1
+= rwb
)
1385 unsigned INT_TYPE word
;
1387 for (word
= (unsigned INT_TYPE
) *p
++, q2
= q1
; word
;
1388 word
>>= 1, q2
+= rw
)
1397 /* Handle the case where REG is set by the insn being scanned,
1398 during the forward scan to accumulate conflicts.
1399 Store a 1 in regs_live or allocnos_live for this register, record how many
1400 consecutive hardware registers it actually needs,
1401 and record a conflict with all other registers already live.
1403 Note that even if REG does not remain alive after this insn,
1404 we must mark it here as live, to ensure a conflict between
1405 REG and any other regs set in this insn that really do live.
1406 This is because those other regs could be considered after this.
1408 REG might actually be something other than a register;
1409 if so, we do nothing.
1411 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1412 a REG_INC note was found for it). */
1415 mark_reg_store (reg
, setter
, data
)
1417 void *data ATTRIBUTE_UNUSED
;
1421 /* WORD is which word of a multi-register group is being stored.
1422 For the case where the store is actually into a SUBREG of REG.
1423 Except we don't use it; I believe the entire REG needs to be
1427 if (GET_CODE (reg
) == SUBREG
)
1429 word
= SUBREG_WORD (reg
);
1430 reg
= SUBREG_REG (reg
);
1433 if (GET_CODE (reg
) != REG
)
1436 regs_set
[n_regs_set
++] = reg
;
1438 if (setter
&& GET_CODE (setter
) != CLOBBER
)
1439 set_preference (reg
, SET_SRC (setter
));
1441 regno
= REGNO (reg
);
1443 /* Either this is one of the max_allocno pseudo regs not allocated,
1444 or it is or has a hardware reg. First handle the pseudo-regs. */
1445 if (regno
>= FIRST_PSEUDO_REGISTER
)
1447 if (reg_allocno
[regno
] >= 0)
1449 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1450 record_one_conflict (regno
);
1454 if (reg_renumber
[regno
] >= 0)
1455 regno
= reg_renumber
[regno
] /* + word */;
1457 /* Handle hardware regs (and pseudos allocated to hard regs). */
1458 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1460 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1461 while (regno
< last
)
1463 record_one_conflict (regno
);
1464 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1470 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1473 mark_reg_clobber (reg
, setter
, data
)
1475 void *data ATTRIBUTE_UNUSED
;
1477 if (GET_CODE (setter
) == CLOBBER
)
1478 mark_reg_store (reg
, setter
, data
);
1481 /* Record that REG has conflicts with all the regs currently live.
1482 Do not mark REG itself as live. */
1485 mark_reg_conflicts (reg
)
1490 if (GET_CODE (reg
) == SUBREG
)
1491 reg
= SUBREG_REG (reg
);
1493 if (GET_CODE (reg
) != REG
)
1496 regno
= REGNO (reg
);
1498 /* Either this is one of the max_allocno pseudo regs not allocated,
1499 or it is or has a hardware reg. First handle the pseudo-regs. */
1500 if (regno
>= FIRST_PSEUDO_REGISTER
)
1502 if (reg_allocno
[regno
] >= 0)
1503 record_one_conflict (regno
);
1506 if (reg_renumber
[regno
] >= 0)
1507 regno
= reg_renumber
[regno
];
1509 /* Handle hardware regs (and pseudos allocated to hard regs). */
1510 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1512 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1513 while (regno
< last
)
1515 record_one_conflict (regno
);
1521 /* Mark REG as being dead (following the insn being scanned now).
1522 Store a 0 in regs_live or allocnos_live for this register. */
1525 mark_reg_death (reg
)
1528 register int regno
= REGNO (reg
);
1530 /* Either this is one of the max_allocno pseudo regs not allocated,
1531 or it is a hardware reg. First handle the pseudo-regs. */
1532 if (regno
>= FIRST_PSEUDO_REGISTER
)
1534 if (reg_allocno
[regno
] >= 0)
1535 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1538 /* For pseudo reg, see if it has been assigned a hardware reg. */
1539 if (reg_renumber
[regno
] >= 0)
1540 regno
= reg_renumber
[regno
];
1542 /* Handle hardware regs (and pseudos allocated to hard regs). */
1543 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1545 /* Pseudo regs already assigned hardware regs are treated
1546 almost the same as explicit hardware regs. */
1547 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1548 while (regno
< last
)
1550 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1556 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1557 for the value stored in it. MODE determines how many consecutive
1558 registers are actually in use. Do not record conflicts;
1559 it is assumed that the caller will do that. */
1562 mark_reg_live_nc (regno
, mode
)
1564 enum machine_mode mode
;
1566 register int last
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1567 while (regno
< last
)
1569 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1574 /* Try to set a preference for an allocno to a hard register.
1575 We are passed DEST and SRC which are the operands of a SET. It is known
1576 that SRC is a register. If SRC or the first operand of SRC is a register,
1577 try to set a preference. If one of the two is a hard register and the other
1578 is a pseudo-register, mark the preference.
1580 Note that we are not as aggressive as local-alloc in trying to tie a
1581 pseudo-register to a hard register. */
1584 set_preference (dest
, src
)
1587 int src_regno
, dest_regno
;
1588 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1589 to compensate for subregs in SRC or DEST. */
1594 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1595 src
= XEXP (src
, 0), copy
= 0;
1597 /* Get the reg number for both SRC and DEST.
1598 If neither is a reg, give up. */
1600 if (GET_CODE (src
) == REG
)
1601 src_regno
= REGNO (src
);
1602 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1604 src_regno
= REGNO (SUBREG_REG (src
));
1605 offset
+= SUBREG_WORD (src
);
1610 if (GET_CODE (dest
) == REG
)
1611 dest_regno
= REGNO (dest
);
1612 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1614 dest_regno
= REGNO (SUBREG_REG (dest
));
1615 offset
-= SUBREG_WORD (dest
);
1620 /* Convert either or both to hard reg numbers. */
1622 if (reg_renumber
[src_regno
] >= 0)
1623 src_regno
= reg_renumber
[src_regno
];
1625 if (reg_renumber
[dest_regno
] >= 0)
1626 dest_regno
= reg_renumber
[dest_regno
];
1628 /* Now if one is a hard reg and the other is a global pseudo
1629 then give the other a preference. */
1631 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1632 && reg_allocno
[src_regno
] >= 0)
1634 dest_regno
-= offset
;
1635 if (dest_regno
>= 0 && dest_regno
< FIRST_PSEUDO_REGISTER
)
1638 SET_REGBIT (hard_reg_copy_preferences
,
1639 reg_allocno
[src_regno
], dest_regno
);
1641 SET_REGBIT (hard_reg_preferences
,
1642 reg_allocno
[src_regno
], dest_regno
);
1643 for (i
= dest_regno
;
1644 i
< dest_regno
+ HARD_REGNO_NREGS (dest_regno
, GET_MODE (dest
));
1646 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1650 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1651 && reg_allocno
[dest_regno
] >= 0)
1653 src_regno
+= offset
;
1654 if (src_regno
>= 0 && src_regno
< FIRST_PSEUDO_REGISTER
)
1657 SET_REGBIT (hard_reg_copy_preferences
,
1658 reg_allocno
[dest_regno
], src_regno
);
1660 SET_REGBIT (hard_reg_preferences
,
1661 reg_allocno
[dest_regno
], src_regno
);
1663 i
< src_regno
+ HARD_REGNO_NREGS (src_regno
, GET_MODE (src
));
1665 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1670 /* Indicate that hard register number FROM was eliminated and replaced with
1671 an offset from hard register number TO. The status of hard registers live
1672 at the start of a basic block is updated by replacing a use of FROM with
1676 mark_elimination (from
, to
)
1681 for (i
= 0; i
< n_basic_blocks
; i
++)
1683 register regset r
= BASIC_BLOCK (i
)->global_live_at_start
;
1684 if (REGNO_REG_SET_P (r
, from
))
1686 CLEAR_REGNO_REG_SET (r
, from
);
1687 SET_REGNO_REG_SET (r
, to
);
1692 /* Used for communication between the following functions. Holds the
1693 current life information. */
1694 static regset live_relevant_regs
;
1696 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1697 This is called via note_stores. */
1699 reg_becomes_live (reg
, setter
, regs_set
)
1701 rtx setter ATTRIBUTE_UNUSED
;
1706 if (GET_CODE (reg
) == SUBREG
)
1707 reg
= SUBREG_REG (reg
);
1709 if (GET_CODE (reg
) != REG
)
1712 regno
= REGNO (reg
);
1713 if (regno
< FIRST_PSEUDO_REGISTER
)
1715 int nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1718 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1719 if (! fixed_regs
[regno
])
1720 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1724 else if (reg_renumber
[regno
] >= 0)
1726 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1727 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1731 /* Record in live_relevant_regs that register REGNO died. */
1733 reg_dies (regno
, mode
, chain
)
1735 enum machine_mode mode
;
1736 struct insn_chain
*chain
;
1738 if (regno
< FIRST_PSEUDO_REGISTER
)
1740 int nregs
= HARD_REGNO_NREGS (regno
, mode
);
1743 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1744 if (! fixed_regs
[regno
])
1745 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1751 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1752 if (reg_renumber
[regno
] >= 0)
1753 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1757 /* Walk the insns of the current function and build reload_insn_chain,
1758 and record register life information. */
1760 build_insn_chain (first
)
1763 struct insn_chain
**p
= &reload_insn_chain
;
1764 struct insn_chain
*prev
= 0;
1767 live_relevant_regs
= ALLOCA_REG_SET ();
1769 for (; first
; first
= NEXT_INSN (first
))
1771 struct insn_chain
*c
;
1773 if (first
== BLOCK_HEAD (b
))
1777 CLEAR_REG_SET (live_relevant_regs
);
1779 EXECUTE_IF_SET_IN_BITMAP
1780 (BASIC_BLOCK (b
)->global_live_at_start
, 0, i
,
1782 if (i
< FIRST_PSEUDO_REGISTER
1783 ? ! TEST_HARD_REG_BIT (eliminable_regset
, i
)
1784 : reg_renumber
[i
] >= 0)
1785 SET_REGNO_REG_SET (live_relevant_regs
, i
);
1789 if (GET_CODE (first
) != NOTE
&& GET_CODE (first
) != BARRIER
)
1791 c
= new_insn_chain ();
1799 if (GET_RTX_CLASS (GET_CODE (first
)) == 'i')
1803 /* Mark the death of everything that dies in this instruction. */
1805 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1806 if (REG_NOTE_KIND (link
) == REG_DEAD
1807 && GET_CODE (XEXP (link
, 0)) == REG
)
1808 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1811 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1813 /* Mark everything born in this instruction as live. */
1815 note_stores (PATTERN (first
), reg_becomes_live
,
1819 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1821 if (GET_RTX_CLASS (GET_CODE (first
)) == 'i')
1825 /* Mark anything that is set in this insn and then unused as dying. */
1827 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1828 if (REG_NOTE_KIND (link
) == REG_UNUSED
1829 && GET_CODE (XEXP (link
, 0)) == REG
)
1830 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1835 if (first
== BLOCK_END (b
))
1838 /* Stop after we pass the end of the last basic block. Verify that
1839 no real insns are after the end of the last basic block.
1841 We may want to reorganize the loop somewhat since this test should
1842 always be the right exit test. */
1843 if (b
== n_basic_blocks
)
1845 for (first
= NEXT_INSN (first
) ; first
; first
= NEXT_INSN (first
))
1846 if (GET_RTX_CLASS (GET_CODE (first
)) == 'i'
1847 && GET_CODE (PATTERN (first
)) != USE
)
1852 FREE_REG_SET (live_relevant_regs
);
1856 /* Print debugging trace information if -dg switch is given,
1857 showing the information on which the allocation decisions are based. */
1860 dump_conflicts (file
)
1864 register int has_preferences
;
1867 for (i
= 0; i
< max_allocno
; i
++)
1869 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1873 fprintf (file
, ";; %d regs to allocate:", nregs
);
1874 for (i
= 0; i
< max_allocno
; i
++)
1877 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1879 fprintf (file
, " %d", allocno
[allocno_order
[i
]].reg
);
1880 for (j
= 0; j
< max_regno
; j
++)
1881 if (reg_allocno
[j
] == allocno_order
[i
]
1882 && j
!= allocno
[allocno_order
[i
]].reg
)
1883 fprintf (file
, "+%d", j
);
1884 if (allocno
[allocno_order
[i
]].size
!= 1)
1885 fprintf (file
, " (%d)", allocno
[allocno_order
[i
]].size
);
1887 fprintf (file
, "\n");
1889 for (i
= 0; i
< max_allocno
; i
++)
1892 fprintf (file
, ";; %d conflicts:", allocno
[i
].reg
);
1893 for (j
= 0; j
< max_allocno
; j
++)
1894 if (CONFLICTP (j
, i
))
1895 fprintf (file
, " %d", allocno
[j
].reg
);
1896 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1897 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_conflicts
, j
))
1898 fprintf (file
, " %d", j
);
1899 fprintf (file
, "\n");
1901 has_preferences
= 0;
1902 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1903 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1904 has_preferences
= 1;
1906 if (! has_preferences
)
1908 fprintf (file
, ";; %d preferences:", allocno
[i
].reg
);
1909 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1910 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1911 fprintf (file
, " %d", j
);
1912 fprintf (file
, "\n");
1914 fprintf (file
, "\n");
1918 dump_global_regs (file
)
1923 fprintf (file
, ";; Register dispositions:\n");
1924 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1925 if (reg_renumber
[i
] >= 0)
1927 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1929 fprintf (file
, "\n");
1932 fprintf (file
, "\n\n;; Hard regs used: ");
1933 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1934 if (regs_ever_live
[i
])
1935 fprintf (file
, " %d", i
);
1936 fprintf (file
, "\n\n");