1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 1988, 1991, 1994, 1996, 1997, 1998,
3 1999, 2000, 2002 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
25 #include "coretypes.h"
29 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "insn-config.h"
41 /* This pass of the compiler performs global register allocation.
42 It assigns hard register numbers to all the pseudo registers
43 that were not handled in local_alloc. Assignments are recorded
44 in the vector reg_renumber, not by changing the rtl code.
45 (Such changes are made by final). The entry point is
46 the function global_alloc.
48 After allocation is complete, the reload pass is run as a subroutine
49 of this pass, so that when a pseudo reg loses its hard reg due to
50 spilling it is possible to make a second attempt to find a hard
51 reg for it. The reload pass is independent in other respects
52 and it is run even when stupid register allocation is in use.
54 1. Assign allocation-numbers (allocnos) to the pseudo-registers
55 still needing allocations and to the pseudo-registers currently
56 allocated by local-alloc which may be spilled by reload.
57 Set up tables reg_allocno and allocno_reg to map
58 reg numbers to allocnos and vice versa.
59 max_allocno gets the number of allocnos in use.
61 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
62 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
63 for conflicts between allocnos and explicit hard register use
64 (which includes use of pseudo-registers allocated by local_alloc).
66 3. For each basic block
67 walk forward through the block, recording which
68 pseudo-registers and which hardware registers are live.
69 Build the conflict matrix between the pseudo-registers
70 and another of pseudo-registers versus hardware registers.
71 Also record the preferred hardware registers
72 for each pseudo-register.
74 4. Sort a table of the allocnos into order of
75 desirability of the variables.
77 5. Allocate the variables in that order; each if possible into
78 a preferred register, else into another register. */
80 /* Number of pseudo-registers which are candidates for allocation. */
82 static int max_allocno
;
84 /* Indexed by (pseudo) reg number, gives the allocno, or -1
85 for pseudo registers which are not to be allocated. */
87 static int *reg_allocno
;
92 /* Gives the number of consecutive hard registers needed by that
96 /* Number of calls crossed by each allocno. */
99 /* Number of refs to each allocno. */
102 /* Frequency of uses of each allocno. */
105 /* Guess at live length of each allocno.
106 This is actually the max of the live lengths of the regs. */
109 /* Set of hard regs conflicting with allocno N. */
111 HARD_REG_SET hard_reg_conflicts
;
113 /* Set of hard regs preferred by allocno N.
114 This is used to make allocnos go into regs that are copied to or from them,
115 when possible, to reduce register shuffling. */
117 HARD_REG_SET hard_reg_preferences
;
119 /* Similar, but just counts register preferences made in simple copy
120 operations, rather than arithmetic. These are given priority because
121 we can always eliminate an insn by using these, but using a register
122 in the above list won't always eliminate an insn. */
124 HARD_REG_SET hard_reg_copy_preferences
;
126 /* Similar to hard_reg_preferences, but includes bits for subsequent
127 registers when an allocno is multi-word. The above variable is used for
128 allocation while this is used to build reg_someone_prefers, below. */
130 HARD_REG_SET hard_reg_full_preferences
;
132 /* Set of hard registers that some later allocno has a preference for. */
134 HARD_REG_SET regs_someone_prefers
;
137 /* Set to true if allocno can't be allocated in the stack register. */
142 static struct allocno
*allocno
;
144 /* A vector of the integers from 0 to max_allocno-1,
145 sorted in the order of first-to-be-allocated first. */
147 static int *allocno_order
;
149 /* Indexed by (pseudo) reg number, gives the number of another
150 lower-numbered pseudo reg which can share a hard reg with this pseudo
151 *even if the two pseudos would otherwise appear to conflict*. */
153 static int *reg_may_share
;
155 /* Define the number of bits in each element of `conflicts' and what
156 type that element has. We use the largest integer format on the
159 #define INT_BITS HOST_BITS_PER_WIDE_INT
160 #define INT_TYPE HOST_WIDE_INT
162 /* max_allocno by max_allocno array of bits,
163 recording whether two allocno's conflict (can't go in the same
166 `conflicts' is symmetric after the call to mirror_conflicts. */
168 static INT_TYPE
*conflicts
;
170 /* Number of ints require to hold max_allocno bits.
171 This is the length of a row in `conflicts'. */
173 static int allocno_row_words
;
175 /* Two macros to test or store 1 in an element of `conflicts'. */
177 #define CONFLICTP(I, J) \
178 (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS] \
179 & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS)))
181 /* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
183 #define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
187 INT_TYPE *p_ = (ALLOCNO_SET); \
189 for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
190 i_--, allocno_ += INT_BITS) \
192 unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
194 for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
202 /* This doesn't work for non-GNU C due to the way CODE is macro expanded. */
204 /* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to
205 the conflicting allocno, and execute CODE. This macro assumes that
206 mirror_conflicts has been run. */
207 #define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\
208 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\
212 /* Set of hard regs currently live (during scan of all insns). */
214 static HARD_REG_SET hard_regs_live
;
216 /* Set of registers that global-alloc isn't supposed to use. */
218 static HARD_REG_SET no_global_alloc_regs
;
220 /* Set of registers used so far. */
222 static HARD_REG_SET regs_used_so_far
;
224 /* Number of refs to each hard reg, as used by local alloc.
225 It is zero for a reg that contains global pseudos or is explicitly used. */
227 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
229 /* Frequency of uses of given hard reg. */
230 static int local_reg_freq
[FIRST_PSEUDO_REGISTER
];
232 /* Guess at live length of each hard reg, as used by local alloc.
233 This is actually the sum of the live lengths of the specific regs. */
235 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
237 /* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
238 element I, and hard register number J. */
240 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
242 /* Bit mask for allocnos live at current point in the scan. */
244 static INT_TYPE
*allocnos_live
;
246 /* Test, set or clear bit number I in allocnos_live,
247 a bit vector indexed by allocno. */
249 #define SET_ALLOCNO_LIVE(I) \
250 (allocnos_live[(unsigned) (I) / INT_BITS] \
251 |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
253 #define CLEAR_ALLOCNO_LIVE(I) \
254 (allocnos_live[(unsigned) (I) / INT_BITS] \
255 &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
257 /* This is turned off because it doesn't work right for DImode.
258 (And it is only used for DImode, so the other cases are worthless.)
259 The problem is that it isn't true that there is NO possibility of conflict;
260 only that there is no conflict if the two pseudos get the exact same regs.
261 If they were allocated with a partial overlap, there would be a conflict.
262 We can't safely turn off the conflict unless we have another way to
263 prevent the partial overlap.
265 Idea: change hard_reg_conflicts so that instead of recording which
266 hard regs the allocno may not overlap, it records where the allocno
267 may not start. Change both where it is used and where it is updated.
268 Then there is a way to record that (reg:DI 108) may start at 10
269 but not at 9 or 11. There is still the question of how to record
270 this semi-conflict between two pseudos. */
272 /* Reg pairs for which conflict after the current insn
273 is inhibited by a REG_NO_CONFLICT note.
274 If the table gets full, we ignore any other notes--that is conservative. */
275 #define NUM_NO_CONFLICT_PAIRS 4
276 /* Number of pairs in use in this insn. */
277 int n_no_conflict_pairs
;
278 static struct { int allocno1
, allocno2
;}
279 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
282 /* Record all regs that are set in any one insn.
283 Communication from mark_reg_{store,clobber} and global_conflicts. */
285 static rtx
*regs_set
;
286 static int n_regs_set
;
288 /* All registers that can be eliminated. */
290 static HARD_REG_SET eliminable_regset
;
292 static int allocno_compare
PARAMS ((const void *, const void *));
293 static void global_conflicts
PARAMS ((void));
294 static void mirror_conflicts
PARAMS ((void));
295 static void expand_preferences
PARAMS ((void));
296 static void prune_preferences
PARAMS ((void));
297 static void find_reg
PARAMS ((int, HARD_REG_SET
, int, int, int));
298 static void record_one_conflict
PARAMS ((int));
299 static void record_conflicts
PARAMS ((int *, int));
300 static void mark_reg_store
PARAMS ((rtx
, rtx
, void *));
301 static void mark_reg_clobber
PARAMS ((rtx
, rtx
, void *));
302 static void mark_reg_conflicts
PARAMS ((rtx
));
303 static void mark_reg_death
PARAMS ((rtx
));
304 static void mark_reg_live_nc
PARAMS ((int, enum machine_mode
));
305 static void set_preference
PARAMS ((rtx
, rtx
));
306 static void dump_conflicts
PARAMS ((FILE *));
307 static void reg_becomes_live
PARAMS ((rtx
, rtx
, void *));
308 static void reg_dies
PARAMS ((int, enum machine_mode
,
309 struct insn_chain
*));
311 /* Perform allocation of pseudo-registers not allocated by local_alloc.
312 FILE is a file to output debugging information on,
313 or zero if such output is not desired.
315 Return value is nonzero if reload failed
316 and we must not do any more for this function. */
323 #ifdef ELIMINABLE_REGS
324 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
327 = (! flag_omit_frame_pointer
328 #ifdef EXIT_IGNORE_STACK
329 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
331 || FRAME_POINTER_REQUIRED
);
338 /* A machine may have certain hard registers that
339 are safe to use only within a basic block. */
341 CLEAR_HARD_REG_SET (no_global_alloc_regs
);
343 /* Build the regset of all eliminable registers and show we can't use those
344 that we already know won't be eliminated. */
345 #ifdef ELIMINABLE_REGS
346 for (i
= 0; i
< ARRAY_SIZE (eliminables
); i
++)
348 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
350 if (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
351 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
))
352 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
354 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
355 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
357 SET_HARD_REG_BIT (no_global_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
361 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
363 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
366 /* Track which registers have already been used. Start with registers
367 explicitly in the rtl, then registers allocated by local register
370 CLEAR_HARD_REG_SET (regs_used_so_far
);
371 #ifdef LEAF_REGISTERS
372 /* If we are doing the leaf function optimization, and this is a leaf
373 function, it means that the registers that take work to save are those
374 that need a register window. So prefer the ones that can be used in
377 const char *cheap_regs
;
378 const char *const leaf_regs
= LEAF_REGISTERS
;
380 if (only_leaf_regs_used () && leaf_function_p ())
381 cheap_regs
= leaf_regs
;
383 cheap_regs
= call_used_regs
;
384 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
385 if (regs_ever_live
[i
] || cheap_regs
[i
])
386 SET_HARD_REG_BIT (regs_used_so_far
, i
);
389 /* We consider registers that do not have to be saved over calls as if
390 they were already used since there is no cost in using them. */
391 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
392 if (regs_ever_live
[i
] || call_used_regs
[i
])
393 SET_HARD_REG_BIT (regs_used_so_far
, i
);
396 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
397 if (reg_renumber
[i
] >= 0)
398 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
400 /* Establish mappings from register number to allocation number
401 and vice versa. In the process, count the allocnos. */
403 reg_allocno
= (int *) xmalloc (max_regno
* sizeof (int));
405 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
408 /* Initialize the shared-hard-reg mapping
409 from the list of pairs that may share. */
410 reg_may_share
= (int *) xcalloc (max_regno
, sizeof (int));
411 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
413 int r1
= REGNO (XEXP (x
, 0));
414 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
416 reg_may_share
[r1
] = r2
;
418 reg_may_share
[r2
] = r1
;
421 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
422 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
423 that we are supposed to refrain from putting in a hard reg.
424 -2 means do make an allocno but don't allocate it. */
425 if (REG_N_REFS (i
) != 0 && REG_LIVE_LENGTH (i
) != -1
426 /* Don't allocate pseudos that cross calls,
427 if this function receives a nonlocal goto. */
428 && (! current_function_has_nonlocal_label
429 || REG_N_CALLS_CROSSED (i
) == 0))
431 if (reg_renumber
[i
] < 0 && reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
432 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
434 reg_allocno
[i
] = max_allocno
++;
435 if (REG_LIVE_LENGTH (i
) == 0)
441 allocno
= (struct allocno
*) xcalloc (max_allocno
, sizeof (struct allocno
));
443 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
444 if (reg_allocno
[i
] >= 0)
446 int num
= reg_allocno
[i
];
447 allocno
[num
].reg
= i
;
448 allocno
[num
].size
= PSEUDO_REGNO_SIZE (i
);
449 allocno
[num
].calls_crossed
+= REG_N_CALLS_CROSSED (i
);
450 allocno
[num
].n_refs
+= REG_N_REFS (i
);
451 allocno
[num
].freq
+= REG_FREQ (i
);
452 if (allocno
[num
].live_length
< REG_LIVE_LENGTH (i
))
453 allocno
[num
].live_length
= REG_LIVE_LENGTH (i
);
456 /* Calculate amount of usage of each hard reg by pseudos
457 allocated by local-alloc. This is to see if we want to
459 memset ((char *) local_reg_live_length
, 0, sizeof local_reg_live_length
);
460 memset ((char *) local_reg_n_refs
, 0, sizeof local_reg_n_refs
);
461 memset ((char *) local_reg_freq
, 0, sizeof local_reg_freq
);
462 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
463 if (reg_renumber
[i
] >= 0)
465 int regno
= reg_renumber
[i
];
466 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (i
));
469 for (j
= regno
; j
< endregno
; j
++)
471 local_reg_n_refs
[j
] += REG_N_REFS (i
);
472 local_reg_freq
[j
] += REG_FREQ (i
);
473 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
477 /* We can't override local-alloc for a reg used not just by local-alloc. */
478 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
479 if (regs_ever_live
[i
])
480 local_reg_n_refs
[i
] = 0, local_reg_freq
[i
] = 0;
482 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
484 /* We used to use alloca here, but the size of what it would try to
485 allocate would occasionally cause it to exceed the stack limit and
486 cause unpredictable core dumps. Some examples were > 2Mb in size. */
487 conflicts
= (INT_TYPE
*) xcalloc (max_allocno
* allocno_row_words
,
490 allocnos_live
= (INT_TYPE
*) xmalloc (allocno_row_words
* sizeof (INT_TYPE
));
492 /* If there is work to be done (at least one reg to allocate),
493 perform global conflict analysis and allocate the regs. */
497 /* Scan all the insns and compute the conflicts among allocnos
498 and between allocnos and hard regs. */
504 /* Eliminate conflicts between pseudos and eliminable registers. If
505 the register is not eliminated, the pseudo won't really be able to
506 live in the eliminable register, so the conflict doesn't matter.
507 If we do eliminate the register, the conflict will no longer exist.
508 So in either case, we can ignore the conflict. Likewise for
511 for (i
= 0; i
< (size_t) max_allocno
; i
++)
513 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_conflicts
,
515 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_copy_preferences
,
517 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_preferences
,
521 /* Try to expand the preferences by merging them between allocnos. */
523 expand_preferences ();
525 /* Determine the order to allocate the remaining pseudo registers. */
527 allocno_order
= (int *) xmalloc (max_allocno
* sizeof (int));
528 for (i
= 0; i
< (size_t) max_allocno
; i
++)
529 allocno_order
[i
] = i
;
531 /* Default the size to 1, since allocno_compare uses it to divide by.
532 Also convert allocno_live_length of zero to -1. A length of zero
533 can occur when all the registers for that allocno have reg_live_length
534 equal to -2. In this case, we want to make an allocno, but not
535 allocate it. So avoid the divide-by-zero and set it to a low
538 for (i
= 0; i
< (size_t) max_allocno
; i
++)
540 if (allocno
[i
].size
== 0)
542 if (allocno
[i
].live_length
== 0)
543 allocno
[i
].live_length
= -1;
546 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
548 prune_preferences ();
551 dump_conflicts (file
);
553 /* Try allocating them, one by one, in that order,
554 except for parameters marked with reg_live_length[regno] == -2. */
556 for (i
= 0; i
< (size_t) max_allocno
; i
++)
557 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] < 0
558 && REG_LIVE_LENGTH (allocno
[allocno_order
[i
]].reg
) >= 0)
560 /* If we have more than one register class,
561 first try allocating in the class that is cheapest
562 for this pseudo-reg. If that fails, try any reg. */
563 if (N_REG_CLASSES
> 1)
565 find_reg (allocno_order
[i
], 0, 0, 0, 0);
566 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
569 if (reg_alternate_class (allocno
[allocno_order
[i
]].reg
) != NO_REGS
)
570 find_reg (allocno_order
[i
], 0, 1, 0, 0);
573 free (allocno_order
);
576 /* Do the reloads now while the allocno data still exist, so that we can
577 try to assign new hard regs to any pseudo regs that are spilled. */
579 #if 0 /* We need to eliminate regs even if there is no rtl code,
580 for the sake of debugging information. */
581 if (n_basic_blocks
> 0)
584 build_insn_chain (get_insns ());
585 retval
= reload (get_insns (), 1);
590 free (reg_may_share
);
593 free (allocnos_live
);
598 /* Sort predicate for ordering the allocnos.
599 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
602 allocno_compare (v1p
, v2p
)
606 int v1
= *(const int *)v1p
, v2
= *(const int *)v2p
;
607 /* Note that the quotient will never be bigger than
608 the value of floor_log2 times the maximum number of
609 times a register can occur in one insn (surely less than 100)
610 weighted by the frequency (maximally REG_FREQ_MAX).
611 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
613 = (((double) (floor_log2 (allocno
[v1
].n_refs
) * allocno
[v1
].freq
)
614 / allocno
[v1
].live_length
)
615 * (10000 / REG_FREQ_MAX
) * allocno
[v1
].size
);
617 = (((double) (floor_log2 (allocno
[v2
].n_refs
) * allocno
[v2
].freq
)
618 / allocno
[v2
].live_length
)
619 * (10000 / REG_FREQ_MAX
) * allocno
[v2
].size
);
623 /* If regs are equally good, sort by allocno,
624 so that the results of qsort leave nothing to chance. */
628 /* Scan the rtl code and record all conflicts and register preferences in the
629 conflict matrices and preference tables. */
637 int *block_start_allocnos
;
639 /* Make a vector that mark_reg_{store,clobber} will store in. */
640 regs_set
= (rtx
*) xmalloc (max_parallel
* sizeof (rtx
) * 2);
642 block_start_allocnos
= (int *) xmalloc (max_allocno
* sizeof (int));
646 memset ((char *) allocnos_live
, 0, allocno_row_words
* sizeof (INT_TYPE
));
648 /* Initialize table of registers currently live
649 to the state at the beginning of this basic block.
650 This also marks the conflicts among hard registers
651 and any allocnos that are live.
653 For pseudo-regs, there is only one bit for each one
654 no matter how many hard regs it occupies.
655 This is ok; we know the size from PSEUDO_REGNO_SIZE.
656 For explicit hard regs, we cannot know the size that way
657 since one hard reg can be used with various sizes.
658 Therefore, we must require that all the hard regs
659 implicitly live as part of a multi-word hard reg
660 are explicitly marked in basic_block_live_at_start. */
663 regset old
= b
->global_live_at_start
;
666 REG_SET_TO_HARD_REG_SET (hard_regs_live
, old
);
667 EXECUTE_IF_SET_IN_REG_SET (old
, FIRST_PSEUDO_REGISTER
, i
,
669 int a
= reg_allocno
[i
];
672 SET_ALLOCNO_LIVE (a
);
673 block_start_allocnos
[ax
++] = a
;
675 else if ((a
= reg_renumber
[i
]) >= 0)
677 (a
, PSEUDO_REGNO_MODE (i
));
680 /* Record that each allocno now live conflicts with each hard reg
683 It is not necessary to mark any conflicts between pseudos as
684 this point, even for pseudos which are live at the start of
687 Given two pseudos X and Y and any point in the CFG P.
689 On any path to point P where X and Y are live one of the
690 following conditions must be true:
692 1. X is live at some instruction on the path that
695 2. Y is live at some instruction on the path that
698 3. Either X or Y is not evaluated on the path to P
699 (ie it is used uninitialized) and thus the
700 conflict can be ignored.
702 In cases #1 and #2 the conflict will be recorded when we
703 scan the instruction that makes either X or Y become live. */
704 record_conflicts (block_start_allocnos
, ax
);
706 /* Pseudos can't go in stack regs at the start of a basic block that
707 is reached by an abnormal edge. Likewise for call clobbered regs,
708 because because caller-save, fixup_abnormal_edges, and possibly
709 the table driven EH machinery are not quite ready to handle such
710 regs live across such edges. */
714 for (e
= b
->pred
; e
; e
= e
->pred_next
)
715 if (e
->flags
& EDGE_ABNORMAL
)
721 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, ax
,
723 allocno
[ax
].no_stack_reg
= 1;
725 for (ax
= FIRST_STACK_REG
; ax
<= LAST_STACK_REG
; ax
++)
726 record_one_conflict (ax
);
729 /* No need to record conflicts for call clobbered regs if we have
730 nonlocal labels around, as we don't ever try to allocate such
731 regs in this case. */
732 if (! current_function_has_nonlocal_label
)
733 for (ax
= 0; ax
< FIRST_PSEUDO_REGISTER
; ax
++)
734 if (call_used_regs
[ax
])
735 record_one_conflict (ax
);
742 /* Scan the code of this basic block, noting which allocnos
743 and hard regs are born or die. When one is born,
744 record a conflict with all others currently live. */
748 RTX_CODE code
= GET_CODE (insn
);
751 /* Make regs_set an empty set. */
755 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
760 for (link
= REG_NOTES (insn
);
761 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
762 link
= XEXP (link
, 1))
763 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
765 no_conflict_pairs
[i
].allocno1
766 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
767 no_conflict_pairs
[i
].allocno2
768 = reg_allocno
[REGNO (XEXP (link
, 0))];
773 /* Mark any registers clobbered by INSN as live,
774 so they conflict with the inputs. */
776 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
778 /* Mark any registers dead after INSN as dead now. */
780 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
781 if (REG_NOTE_KIND (link
) == REG_DEAD
)
782 mark_reg_death (XEXP (link
, 0));
784 /* Mark any registers set in INSN as live,
785 and mark them as conflicting with all other live regs.
786 Clobbers are processed again, so they conflict with
787 the registers that are set. */
789 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
792 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
793 if (REG_NOTE_KIND (link
) == REG_INC
)
794 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
797 /* If INSN has multiple outputs, then any reg that dies here
798 and is used inside of an output
799 must conflict with the other outputs.
801 It is unsafe to use !single_set here since it will ignore an
802 unused output. Just because an output is unused does not mean
803 the compiler can assume the side effect will not occur.
804 Consider if REG appears in the address of an output and we
805 reload the output. If we allocate REG to the same hard
806 register as an unused output we could set the hard register
807 before the output reload insn. */
808 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
809 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
810 if (REG_NOTE_KIND (link
) == REG_DEAD
)
812 int used_in_output
= 0;
814 rtx reg
= XEXP (link
, 0);
816 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
818 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
819 if (GET_CODE (set
) == SET
820 && GET_CODE (SET_DEST (set
)) != REG
821 && !rtx_equal_p (reg
, SET_DEST (set
))
822 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
826 mark_reg_conflicts (reg
);
829 /* Mark any registers set in INSN and then never used. */
831 while (n_regs_set
-- > 0)
833 rtx note
= find_regno_note (insn
, REG_UNUSED
,
834 REGNO (regs_set
[n_regs_set
]));
836 mark_reg_death (XEXP (note
, 0));
842 insn
= NEXT_INSN (insn
);
847 free (block_start_allocnos
);
850 /* Expand the preference information by looking for cases where one allocno
851 dies in an insn that sets an allocno. If those two allocnos don't conflict,
852 merge any preferences between those allocnos. */
855 expand_preferences ()
861 /* We only try to handle the most common cases here. Most of the cases
862 where this wins are reg-reg copies. */
864 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
866 && (set
= single_set (insn
)) != 0
867 && GET_CODE (SET_DEST (set
)) == REG
868 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
869 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
870 if (REG_NOTE_KIND (link
) == REG_DEAD
871 && GET_CODE (XEXP (link
, 0)) == REG
872 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
873 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
874 reg_allocno
[REGNO (XEXP (link
, 0))]))
876 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
877 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
879 if (XEXP (link
, 0) == SET_SRC (set
))
881 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_copy_preferences
,
882 allocno
[a2
].hard_reg_copy_preferences
);
883 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_copy_preferences
,
884 allocno
[a1
].hard_reg_copy_preferences
);
887 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_preferences
,
888 allocno
[a2
].hard_reg_preferences
);
889 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_preferences
,
890 allocno
[a1
].hard_reg_preferences
);
891 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_full_preferences
,
892 allocno
[a2
].hard_reg_full_preferences
);
893 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_full_preferences
,
894 allocno
[a1
].hard_reg_full_preferences
);
898 /* Prune the preferences for global registers to exclude registers that cannot
901 Compute `regs_someone_prefers', which is a bitmask of the hard registers
902 that are preferred by conflicting registers of lower priority. If possible,
903 we will avoid using these registers. */
910 int *allocno_to_order
= (int *) xmalloc (max_allocno
* sizeof (int));
912 /* Scan least most important to most important.
913 For each allocno, remove from preferences registers that cannot be used,
914 either because of conflicts or register type. Then compute all registers
915 preferred by each lower-priority register that conflicts. */
917 for (i
= max_allocno
- 1; i
>= 0; i
--)
921 num
= allocno_order
[i
];
922 allocno_to_order
[num
] = i
;
923 COPY_HARD_REG_SET (temp
, allocno
[num
].hard_reg_conflicts
);
925 if (allocno
[num
].calls_crossed
== 0)
926 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
928 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
930 IOR_COMPL_HARD_REG_SET
932 reg_class_contents
[(int) reg_preferred_class (allocno
[num
].reg
)]);
934 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, temp
);
935 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, temp
);
936 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_full_preferences
, temp
);
939 for (i
= max_allocno
- 1; i
>= 0; i
--)
941 /* Merge in the preferences of lower-priority registers (they have
942 already been pruned). If we also prefer some of those registers,
943 don't exclude them unless we are of a smaller size (in which case
944 we want to give the lower-priority allocno the first chance for
946 HARD_REG_SET temp
, temp2
;
949 num
= allocno_order
[i
];
951 CLEAR_HARD_REG_SET (temp
);
952 CLEAR_HARD_REG_SET (temp2
);
954 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ num
* allocno_row_words
,
957 if (allocno_to_order
[allocno2
] > i
)
959 if (allocno
[allocno2
].size
<= allocno
[num
].size
)
960 IOR_HARD_REG_SET (temp
,
961 allocno
[allocno2
].hard_reg_full_preferences
);
963 IOR_HARD_REG_SET (temp2
,
964 allocno
[allocno2
].hard_reg_full_preferences
);
968 AND_COMPL_HARD_REG_SET (temp
, allocno
[num
].hard_reg_full_preferences
);
969 IOR_HARD_REG_SET (temp
, temp2
);
970 COPY_HARD_REG_SET (allocno
[num
].regs_someone_prefers
, temp
);
972 free (allocno_to_order
);
975 /* Assign a hard register to allocno NUM; look for one that is the beginning
976 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
977 The registers marked in PREFREGS are tried first.
979 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
980 be used for this allocation.
982 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
983 Otherwise ignore that preferred class and use the alternate class.
985 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
986 will have to be saved and restored at calls.
988 RETRYING is nonzero if this is called from retry_global_alloc.
990 If we find one, record it in reg_renumber.
991 If not, do nothing. */
994 find_reg (num
, losers
, alt_regs_p
, accept_call_clobbered
, retrying
)
998 int accept_call_clobbered
;
1001 int i
, best_reg
, pass
;
1002 HARD_REG_SET used
, used1
, used2
;
1004 enum reg_class
class = (alt_regs_p
1005 ? reg_alternate_class (allocno
[num
].reg
)
1006 : reg_preferred_class (allocno
[num
].reg
));
1007 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno
[num
].reg
);
1009 if (accept_call_clobbered
)
1010 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
1011 else if (allocno
[num
].calls_crossed
== 0)
1012 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
1014 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
1016 /* Some registers should not be allocated in global-alloc. */
1017 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
1019 IOR_HARD_REG_SET (used1
, losers
);
1021 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
1022 COPY_HARD_REG_SET (used2
, used1
);
1024 IOR_HARD_REG_SET (used1
, allocno
[num
].hard_reg_conflicts
);
1026 #ifdef CANNOT_CHANGE_MODE_CLASS
1027 cannot_change_mode_set_regs (&used1
, mode
, allocno
[num
].reg
);
1030 /* Try each hard reg to see if it fits. Do this in two passes.
1031 In the first pass, skip registers that are preferred by some other pseudo
1032 to give it a better chance of getting one of those registers. Only if
1033 we can't get a register when excluding those do we take one of them.
1034 However, we never allocate a register for the first time in pass 0. */
1036 COPY_HARD_REG_SET (used
, used1
);
1037 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
1038 IOR_HARD_REG_SET (used
, allocno
[num
].regs_someone_prefers
);
1041 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
1042 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
1046 COPY_HARD_REG_SET (used
, used1
);
1047 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1049 #ifdef REG_ALLOC_ORDER
1050 int regno
= reg_alloc_order
[i
];
1054 if (! TEST_HARD_REG_BIT (used
, regno
)
1055 && HARD_REGNO_MODE_OK (regno
, mode
)
1056 && (allocno
[num
].calls_crossed
== 0
1057 || accept_call_clobbered
1058 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
)))
1061 int lim
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1064 && ! TEST_HARD_REG_BIT (used
, j
));
1071 #ifndef REG_ALLOC_ORDER
1072 i
= j
; /* Skip starting points we know will lose */
1078 /* See if there is a preferred register with the same class as the register
1079 we allocated above. Making this restriction prevents register
1080 preferencing from creating worse register allocation.
1082 Remove from the preferred registers and conflicting registers. Note that
1083 additional conflicts may have been added after `prune_preferences' was
1086 First do this for those register with copy preferences, then all
1087 preferred registers. */
1089 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, used
);
1090 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_copy_preferences
,
1091 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
1095 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1096 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_copy_preferences
, i
)
1097 && HARD_REGNO_MODE_OK (i
, mode
)
1098 && (allocno
[num
].calls_crossed
== 0
1099 || accept_call_clobbered
1100 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1101 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1102 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1103 REGNO_REG_CLASS (best_reg
))
1104 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1105 REGNO_REG_CLASS (i
))))
1108 int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1111 && ! TEST_HARD_REG_BIT (used
, j
)
1112 && (REGNO_REG_CLASS (j
)
1113 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1114 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1115 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1116 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1117 REGNO_REG_CLASS (j
))));
1128 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, used
);
1129 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_preferences
,
1130 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1134 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1135 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_preferences
, i
)
1136 && HARD_REGNO_MODE_OK (i
, mode
)
1137 && (allocno
[num
].calls_crossed
== 0
1138 || accept_call_clobbered
1139 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1140 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1141 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1142 REGNO_REG_CLASS (best_reg
))
1143 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1144 REGNO_REG_CLASS (i
))))
1147 int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1150 && ! TEST_HARD_REG_BIT (used
, j
)
1151 && (REGNO_REG_CLASS (j
)
1152 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1153 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1154 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1155 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1156 REGNO_REG_CLASS (j
))));
1167 /* If we haven't succeeded yet, try with caller-saves.
1168 We need not check to see if the current function has nonlocal
1169 labels because we don't put any pseudos that are live over calls in
1170 registers in that case. */
1172 if (flag_caller_saves
&& best_reg
< 0)
1174 /* Did not find a register. If it would be profitable to
1175 allocate a call-clobbered register and save and restore it
1176 around calls, do that. */
1177 if (! accept_call_clobbered
1178 && allocno
[num
].calls_crossed
!= 0
1179 && CALLER_SAVE_PROFITABLE (allocno
[num
].n_refs
,
1180 allocno
[num
].calls_crossed
))
1182 HARD_REG_SET new_losers
;
1184 CLEAR_HARD_REG_SET (new_losers
);
1186 COPY_HARD_REG_SET (new_losers
, losers
);
1188 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1189 find_reg (num
, new_losers
, alt_regs_p
, 1, retrying
);
1190 if (reg_renumber
[allocno
[num
].reg
] >= 0)
1192 caller_save_needed
= 1;
1198 /* If we haven't succeeded yet,
1199 see if some hard reg that conflicts with us
1200 was utilized poorly by local-alloc.
1201 If so, kick out the regs that were put there by local-alloc
1202 so we can use it instead. */
1203 if (best_reg
< 0 && !retrying
1204 /* Let's not bother with multi-reg allocnos. */
1205 && allocno
[num
].size
== 1)
1207 /* Count from the end, to find the least-used ones first. */
1208 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1210 #ifdef REG_ALLOC_ORDER
1211 int regno
= reg_alloc_order
[i
];
1216 if (local_reg_n_refs
[regno
] != 0
1217 /* Don't use a reg no good for this pseudo. */
1218 && ! TEST_HARD_REG_BIT (used2
, regno
)
1219 && HARD_REGNO_MODE_OK (regno
, mode
)
1220 /* The code below assumes that we need only a single
1221 register, but the check of allocno[num].size above
1222 was not enough. Sometimes we need more than one
1223 register for a single-word value. */
1224 && HARD_REGNO_NREGS (regno
, mode
) == 1
1225 && (allocno
[num
].calls_crossed
== 0
1226 || accept_call_clobbered
1227 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
))
1228 #ifdef CANNOT_CHANGE_MODE_CLASS
1229 && ! invalid_mode_change_p (regno
, REGNO_REG_CLASS (regno
),
1233 && (!allocno
[num
].no_stack_reg
1234 || regno
< FIRST_STACK_REG
|| regno
> LAST_STACK_REG
)
1238 /* We explicitly evaluate the divide results into temporary
1239 variables so as to avoid excess precision problems that occur
1240 on an i386-unknown-sysv4.2 (unixware) host. */
1242 double tmp1
= ((double) local_reg_freq
[regno
]
1243 / local_reg_live_length
[regno
]);
1244 double tmp2
= ((double) allocno
[num
].freq
1245 / allocno
[num
].live_length
);
1249 /* Hard reg REGNO was used less in total by local regs
1250 than it would be used by this one allocno! */
1252 for (k
= 0; k
< max_regno
; k
++)
1253 if (reg_renumber
[k
] >= 0)
1255 int r
= reg_renumber
[k
];
1257 = r
+ HARD_REGNO_NREGS (r
, PSEUDO_REGNO_MODE (k
));
1259 if (regno
>= r
&& regno
< endregno
)
1260 reg_renumber
[k
] = -1;
1270 /* Did we find a register? */
1275 HARD_REG_SET this_reg
;
1277 /* Yes. Record it as the hard register of this pseudo-reg. */
1278 reg_renumber
[allocno
[num
].reg
] = best_reg
;
1279 /* Also of any pseudo-regs that share with it. */
1280 if (reg_may_share
[allocno
[num
].reg
])
1281 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1282 if (reg_allocno
[j
] == num
)
1283 reg_renumber
[j
] = best_reg
;
1285 /* Make a set of the hard regs being allocated. */
1286 CLEAR_HARD_REG_SET (this_reg
);
1287 lim
= best_reg
+ HARD_REGNO_NREGS (best_reg
, mode
);
1288 for (j
= best_reg
; j
< lim
; j
++)
1290 SET_HARD_REG_BIT (this_reg
, j
);
1291 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1292 /* This is no longer a reg used just by local regs. */
1293 local_reg_n_refs
[j
] = 0;
1294 local_reg_freq
[j
] = 0;
1296 /* For each other pseudo-reg conflicting with this one,
1297 mark it as conflicting with the hard regs this one occupies. */
1299 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ lim
* allocno_row_words
, j
,
1301 IOR_HARD_REG_SET (allocno
[j
].hard_reg_conflicts
, this_reg
);
1306 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1307 Perhaps it had previously seemed not worth a hard reg,
1308 or perhaps its old hard reg has been commandeered for reloads.
1309 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1310 they do not appear to be allocated.
1311 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1314 retry_global_alloc (regno
, forbidden_regs
)
1316 HARD_REG_SET forbidden_regs
;
1318 int alloc_no
= reg_allocno
[regno
];
1321 /* If we have more than one register class,
1322 first try allocating in the class that is cheapest
1323 for this pseudo-reg. If that fails, try any reg. */
1324 if (N_REG_CLASSES
> 1)
1325 find_reg (alloc_no
, forbidden_regs
, 0, 0, 1);
1326 if (reg_renumber
[regno
] < 0
1327 && reg_alternate_class (regno
) != NO_REGS
)
1328 find_reg (alloc_no
, forbidden_regs
, 1, 0, 1);
1330 /* If we found a register, modify the RTL for the register to
1331 show the hard register, and mark that register live. */
1332 if (reg_renumber
[regno
] >= 0)
1334 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1335 mark_home_live (regno
);
1340 /* Record a conflict between register REGNO
1341 and everything currently live.
1342 REGNO must not be a pseudo reg that was allocated
1343 by local_alloc; such numbers must be translated through
1344 reg_renumber before calling here. */
1347 record_one_conflict (regno
)
1352 if (regno
< FIRST_PSEUDO_REGISTER
)
1353 /* When a hard register becomes live,
1354 record conflicts with live pseudo regs. */
1355 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, j
,
1357 SET_HARD_REG_BIT (allocno
[j
].hard_reg_conflicts
, regno
);
1360 /* When a pseudo-register becomes live,
1361 record conflicts first with hard regs,
1362 then with other pseudo regs. */
1364 int ialloc
= reg_allocno
[regno
];
1365 int ialloc_prod
= ialloc
* allocno_row_words
;
1367 IOR_HARD_REG_SET (allocno
[ialloc
].hard_reg_conflicts
, hard_regs_live
);
1368 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1372 for (k
= 0; k
< n_no_conflict_pairs
; k
++)
1373 if (! ((j
== no_conflict_pairs
[k
].allocno1
1374 && ialloc
== no_conflict_pairs
[k
].allocno2
)
1376 (j
== no_conflict_pairs
[k
].allocno2
1377 && ialloc
== no_conflict_pairs
[k
].allocno1
)))
1379 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1384 /* Record all allocnos currently live as conflicting
1385 with all hard regs currently live.
1387 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1388 are currently live. Their bits are also flagged in allocnos_live. */
1391 record_conflicts (allocno_vec
, len
)
1396 IOR_HARD_REG_SET (allocno
[allocno_vec
[len
]].hard_reg_conflicts
,
1400 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1405 int rw
= allocno_row_words
;
1406 int rwb
= rw
* INT_BITS
;
1407 INT_TYPE
*p
= conflicts
;
1408 INT_TYPE
*q0
= conflicts
, *q1
, *q2
;
1409 unsigned INT_TYPE mask
;
1411 for (i
= max_allocno
- 1, mask
= 1; i
>= 0; i
--, mask
<<= 1)
1418 for (j
= allocno_row_words
- 1, q1
= q0
; j
>= 0; j
--, q1
+= rwb
)
1420 unsigned INT_TYPE word
;
1422 for (word
= (unsigned INT_TYPE
) *p
++, q2
= q1
; word
;
1423 word
>>= 1, q2
+= rw
)
1432 /* Handle the case where REG is set by the insn being scanned,
1433 during the forward scan to accumulate conflicts.
1434 Store a 1 in regs_live or allocnos_live for this register, record how many
1435 consecutive hardware registers it actually needs,
1436 and record a conflict with all other registers already live.
1438 Note that even if REG does not remain alive after this insn,
1439 we must mark it here as live, to ensure a conflict between
1440 REG and any other regs set in this insn that really do live.
1441 This is because those other regs could be considered after this.
1443 REG might actually be something other than a register;
1444 if so, we do nothing.
1446 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1447 a REG_INC note was found for it). */
1450 mark_reg_store (reg
, setter
, data
)
1452 void *data ATTRIBUTE_UNUSED
;
1456 if (GET_CODE (reg
) == SUBREG
)
1457 reg
= SUBREG_REG (reg
);
1459 if (GET_CODE (reg
) != REG
)
1462 regs_set
[n_regs_set
++] = reg
;
1464 if (setter
&& GET_CODE (setter
) != CLOBBER
)
1465 set_preference (reg
, SET_SRC (setter
));
1467 regno
= REGNO (reg
);
1469 /* Either this is one of the max_allocno pseudo regs not allocated,
1470 or it is or has a hardware reg. First handle the pseudo-regs. */
1471 if (regno
>= FIRST_PSEUDO_REGISTER
)
1473 if (reg_allocno
[regno
] >= 0)
1475 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1476 record_one_conflict (regno
);
1480 if (reg_renumber
[regno
] >= 0)
1481 regno
= reg_renumber
[regno
];
1483 /* Handle hardware regs (and pseudos allocated to hard regs). */
1484 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1486 int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1487 while (regno
< last
)
1489 record_one_conflict (regno
);
1490 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1496 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1499 mark_reg_clobber (reg
, setter
, data
)
1501 void *data ATTRIBUTE_UNUSED
;
1503 if (GET_CODE (setter
) == CLOBBER
)
1504 mark_reg_store (reg
, setter
, data
);
1507 /* Record that REG has conflicts with all the regs currently live.
1508 Do not mark REG itself as live. */
1511 mark_reg_conflicts (reg
)
1516 if (GET_CODE (reg
) == SUBREG
)
1517 reg
= SUBREG_REG (reg
);
1519 if (GET_CODE (reg
) != REG
)
1522 regno
= REGNO (reg
);
1524 /* Either this is one of the max_allocno pseudo regs not allocated,
1525 or it is or has a hardware reg. First handle the pseudo-regs. */
1526 if (regno
>= FIRST_PSEUDO_REGISTER
)
1528 if (reg_allocno
[regno
] >= 0)
1529 record_one_conflict (regno
);
1532 if (reg_renumber
[regno
] >= 0)
1533 regno
= reg_renumber
[regno
];
1535 /* Handle hardware regs (and pseudos allocated to hard regs). */
1536 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1538 int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1539 while (regno
< last
)
1541 record_one_conflict (regno
);
1547 /* Mark REG as being dead (following the insn being scanned now).
1548 Store a 0 in regs_live or allocnos_live for this register. */
1551 mark_reg_death (reg
)
1554 int regno
= REGNO (reg
);
1556 /* Either this is one of the max_allocno pseudo regs not allocated,
1557 or it is a hardware reg. First handle the pseudo-regs. */
1558 if (regno
>= FIRST_PSEUDO_REGISTER
)
1560 if (reg_allocno
[regno
] >= 0)
1561 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1564 /* For pseudo reg, see if it has been assigned a hardware reg. */
1565 if (reg_renumber
[regno
] >= 0)
1566 regno
= reg_renumber
[regno
];
1568 /* Handle hardware regs (and pseudos allocated to hard regs). */
1569 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1571 /* Pseudo regs already assigned hardware regs are treated
1572 almost the same as explicit hardware regs. */
1573 int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1574 while (regno
< last
)
1576 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1582 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1583 for the value stored in it. MODE determines how many consecutive
1584 registers are actually in use. Do not record conflicts;
1585 it is assumed that the caller will do that. */
1588 mark_reg_live_nc (regno
, mode
)
1590 enum machine_mode mode
;
1592 int last
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1593 while (regno
< last
)
1595 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1600 /* Try to set a preference for an allocno to a hard register.
1601 We are passed DEST and SRC which are the operands of a SET. It is known
1602 that SRC is a register. If SRC or the first operand of SRC is a register,
1603 try to set a preference. If one of the two is a hard register and the other
1604 is a pseudo-register, mark the preference.
1606 Note that we are not as aggressive as local-alloc in trying to tie a
1607 pseudo-register to a hard register. */
1610 set_preference (dest
, src
)
1613 unsigned int src_regno
, dest_regno
;
1614 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1615 to compensate for subregs in SRC or DEST. */
1620 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1621 src
= XEXP (src
, 0), copy
= 0;
1623 /* Get the reg number for both SRC and DEST.
1624 If neither is a reg, give up. */
1626 if (GET_CODE (src
) == REG
)
1627 src_regno
= REGNO (src
);
1628 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1630 src_regno
= REGNO (SUBREG_REG (src
));
1632 if (REGNO (SUBREG_REG (src
)) < FIRST_PSEUDO_REGISTER
)
1633 offset
+= subreg_regno_offset (REGNO (SUBREG_REG (src
)),
1634 GET_MODE (SUBREG_REG (src
)),
1638 offset
+= (SUBREG_BYTE (src
)
1639 / REGMODE_NATURAL_SIZE (GET_MODE (src
)));
1644 if (GET_CODE (dest
) == REG
)
1645 dest_regno
= REGNO (dest
);
1646 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1648 dest_regno
= REGNO (SUBREG_REG (dest
));
1650 if (REGNO (SUBREG_REG (dest
)) < FIRST_PSEUDO_REGISTER
)
1651 offset
-= subreg_regno_offset (REGNO (SUBREG_REG (dest
)),
1652 GET_MODE (SUBREG_REG (dest
)),
1656 offset
-= (SUBREG_BYTE (dest
)
1657 / REGMODE_NATURAL_SIZE (GET_MODE (dest
)));
1662 /* Convert either or both to hard reg numbers. */
1664 if (reg_renumber
[src_regno
] >= 0)
1665 src_regno
= reg_renumber
[src_regno
];
1667 if (reg_renumber
[dest_regno
] >= 0)
1668 dest_regno
= reg_renumber
[dest_regno
];
1670 /* Now if one is a hard reg and the other is a global pseudo
1671 then give the other a preference. */
1673 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1674 && reg_allocno
[src_regno
] >= 0)
1676 dest_regno
-= offset
;
1677 if (dest_regno
< FIRST_PSEUDO_REGISTER
)
1680 SET_REGBIT (hard_reg_copy_preferences
,
1681 reg_allocno
[src_regno
], dest_regno
);
1683 SET_REGBIT (hard_reg_preferences
,
1684 reg_allocno
[src_regno
], dest_regno
);
1685 for (i
= dest_regno
;
1686 i
< dest_regno
+ HARD_REGNO_NREGS (dest_regno
, GET_MODE (dest
));
1688 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1692 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1693 && reg_allocno
[dest_regno
] >= 0)
1695 src_regno
+= offset
;
1696 if (src_regno
< FIRST_PSEUDO_REGISTER
)
1699 SET_REGBIT (hard_reg_copy_preferences
,
1700 reg_allocno
[dest_regno
], src_regno
);
1702 SET_REGBIT (hard_reg_preferences
,
1703 reg_allocno
[dest_regno
], src_regno
);
1705 i
< src_regno
+ HARD_REGNO_NREGS (src_regno
, GET_MODE (src
));
1707 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1712 /* Indicate that hard register number FROM was eliminated and replaced with
1713 an offset from hard register number TO. The status of hard registers live
1714 at the start of a basic block is updated by replacing a use of FROM with
1718 mark_elimination (from
, to
)
1725 regset r
= bb
->global_live_at_start
;
1726 if (REGNO_REG_SET_P (r
, from
))
1728 CLEAR_REGNO_REG_SET (r
, from
);
1729 SET_REGNO_REG_SET (r
, to
);
1734 /* Used for communication between the following functions. Holds the
1735 current life information. */
1736 static regset live_relevant_regs
;
1738 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1739 This is called via note_stores. */
1741 reg_becomes_live (reg
, setter
, regs_set
)
1743 rtx setter ATTRIBUTE_UNUSED
;
1748 if (GET_CODE (reg
) == SUBREG
)
1749 reg
= SUBREG_REG (reg
);
1751 if (GET_CODE (reg
) != REG
)
1754 regno
= REGNO (reg
);
1755 if (regno
< FIRST_PSEUDO_REGISTER
)
1757 int nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1760 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1761 if (! fixed_regs
[regno
])
1762 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1766 else if (reg_renumber
[regno
] >= 0)
1768 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1769 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1773 /* Record in live_relevant_regs that register REGNO died. */
1775 reg_dies (regno
, mode
, chain
)
1777 enum machine_mode mode
;
1778 struct insn_chain
*chain
;
1780 if (regno
< FIRST_PSEUDO_REGISTER
)
1782 int nregs
= HARD_REGNO_NREGS (regno
, mode
);
1785 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1786 if (! fixed_regs
[regno
])
1787 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1793 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1794 if (reg_renumber
[regno
] >= 0)
1795 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1799 /* Walk the insns of the current function and build reload_insn_chain,
1800 and record register life information. */
1802 build_insn_chain (first
)
1805 struct insn_chain
**p
= &reload_insn_chain
;
1806 struct insn_chain
*prev
= 0;
1807 basic_block b
= ENTRY_BLOCK_PTR
->next_bb
;
1808 regset_head live_relevant_regs_head
;
1810 live_relevant_regs
= INITIALIZE_REG_SET (live_relevant_regs_head
);
1812 for (; first
; first
= NEXT_INSN (first
))
1814 struct insn_chain
*c
;
1816 if (first
== b
->head
)
1820 CLEAR_REG_SET (live_relevant_regs
);
1822 EXECUTE_IF_SET_IN_BITMAP
1823 (b
->global_live_at_start
, 0, i
,
1825 if (i
< FIRST_PSEUDO_REGISTER
1826 ? ! TEST_HARD_REG_BIT (eliminable_regset
, i
)
1827 : reg_renumber
[i
] >= 0)
1828 SET_REGNO_REG_SET (live_relevant_regs
, i
);
1832 if (GET_CODE (first
) != NOTE
&& GET_CODE (first
) != BARRIER
)
1834 c
= new_insn_chain ();
1840 c
->block
= b
->index
;
1846 /* Mark the death of everything that dies in this instruction. */
1848 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1849 if (REG_NOTE_KIND (link
) == REG_DEAD
1850 && GET_CODE (XEXP (link
, 0)) == REG
)
1851 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1854 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1856 /* Mark everything born in this instruction as live. */
1858 note_stores (PATTERN (first
), reg_becomes_live
,
1862 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1868 /* Mark anything that is set in this insn and then unused as dying. */
1870 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1871 if (REG_NOTE_KIND (link
) == REG_UNUSED
1872 && GET_CODE (XEXP (link
, 0)) == REG
)
1873 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1878 if (first
== b
->end
)
1881 /* Stop after we pass the end of the last basic block. Verify that
1882 no real insns are after the end of the last basic block.
1884 We may want to reorganize the loop somewhat since this test should
1885 always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if
1886 the previous real insn is a JUMP_INSN. */
1887 if (b
== EXIT_BLOCK_PTR
)
1889 for (first
= NEXT_INSN (first
) ; first
; first
= NEXT_INSN (first
))
1891 && GET_CODE (PATTERN (first
)) != USE
1892 && ! ((GET_CODE (PATTERN (first
)) == ADDR_VEC
1893 || GET_CODE (PATTERN (first
)) == ADDR_DIFF_VEC
)
1894 && prev_real_insn (first
) != 0
1895 && GET_CODE (prev_real_insn (first
)) == JUMP_INSN
))
1900 FREE_REG_SET (live_relevant_regs
);
1904 /* Print debugging trace information if -dg switch is given,
1905 showing the information on which the allocation decisions are based. */
1908 dump_conflicts (file
)
1912 int has_preferences
;
1915 for (i
= 0; i
< max_allocno
; i
++)
1917 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1921 fprintf (file
, ";; %d regs to allocate:", nregs
);
1922 for (i
= 0; i
< max_allocno
; i
++)
1925 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1927 fprintf (file
, " %d", allocno
[allocno_order
[i
]].reg
);
1928 for (j
= 0; j
< max_regno
; j
++)
1929 if (reg_allocno
[j
] == allocno_order
[i
]
1930 && j
!= allocno
[allocno_order
[i
]].reg
)
1931 fprintf (file
, "+%d", j
);
1932 if (allocno
[allocno_order
[i
]].size
!= 1)
1933 fprintf (file
, " (%d)", allocno
[allocno_order
[i
]].size
);
1935 fprintf (file
, "\n");
1937 for (i
= 0; i
< max_allocno
; i
++)
1940 fprintf (file
, ";; %d conflicts:", allocno
[i
].reg
);
1941 for (j
= 0; j
< max_allocno
; j
++)
1942 if (CONFLICTP (j
, i
))
1943 fprintf (file
, " %d", allocno
[j
].reg
);
1944 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1945 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_conflicts
, j
))
1946 fprintf (file
, " %d", j
);
1947 fprintf (file
, "\n");
1949 has_preferences
= 0;
1950 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1951 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1952 has_preferences
= 1;
1954 if (! has_preferences
)
1956 fprintf (file
, ";; %d preferences:", allocno
[i
].reg
);
1957 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1958 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1959 fprintf (file
, " %d", j
);
1960 fprintf (file
, "\n");
1962 fprintf (file
, "\n");
1966 dump_global_regs (file
)
1971 fprintf (file
, ";; Register dispositions:\n");
1972 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1973 if (reg_renumber
[i
] >= 0)
1975 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1977 fprintf (file
, "\n");
1980 fprintf (file
, "\n\n;; Hard regs used: ");
1981 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1982 if (regs_ever_live
[i
])
1983 fprintf (file
, " %d", i
);
1984 fprintf (file
, "\n\n");