1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 1988, 1991, 1994, 1996, 1997, 1998,
3 1999, 2000, 2002, 2003 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 (const void *, const void *);
293 static void global_conflicts (void);
294 static void mirror_conflicts (void);
295 static void expand_preferences (void);
296 static void prune_preferences (void);
297 static void find_reg (int, HARD_REG_SET
, int, int, int);
298 static void record_one_conflict (int);
299 static void record_conflicts (int *, int);
300 static void mark_reg_store (rtx
, rtx
, void *);
301 static void mark_reg_clobber (rtx
, rtx
, void *);
302 static void mark_reg_conflicts (rtx
);
303 static void mark_reg_death (rtx
);
304 static void mark_reg_live_nc (int, enum machine_mode
);
305 static void set_preference (rtx
, rtx
);
306 static void dump_conflicts (FILE *);
307 static void reg_becomes_live (rtx
, rtx
, void *);
308 static void reg_dies (int, enum machine_mode
, struct insn_chain
*);
310 /* Perform allocation of pseudo-registers not allocated by local_alloc.
311 FILE is a file to output debugging information on,
312 or zero if such output is not desired.
314 Return value is nonzero if reload failed
315 and we must not do any more for this function. */
318 global_alloc (FILE *file
)
321 #ifdef ELIMINABLE_REGS
322 static const struct {const 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
< ARRAY_SIZE (eliminables
); 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
375 const char *cheap_regs
;
376 const char *const 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
= 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
= 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
= 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 allocno
[num
].freq
+= REG_FREQ (i
);
450 if (allocno
[num
].live_length
< REG_LIVE_LENGTH (i
))
451 allocno
[num
].live_length
= REG_LIVE_LENGTH (i
);
454 /* Calculate amount of usage of each hard reg by pseudos
455 allocated by local-alloc. This is to see if we want to
457 memset (local_reg_live_length
, 0, sizeof local_reg_live_length
);
458 memset (local_reg_n_refs
, 0, sizeof local_reg_n_refs
);
459 memset (local_reg_freq
, 0, sizeof local_reg_freq
);
460 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
461 if (reg_renumber
[i
] >= 0)
463 int regno
= reg_renumber
[i
];
464 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (i
));
467 for (j
= regno
; j
< endregno
; j
++)
469 local_reg_n_refs
[j
] += REG_N_REFS (i
);
470 local_reg_freq
[j
] += REG_FREQ (i
);
471 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
475 /* We can't override local-alloc for a reg used not just by local-alloc. */
476 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
477 if (regs_ever_live
[i
])
478 local_reg_n_refs
[i
] = 0, local_reg_freq
[i
] = 0;
480 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
482 /* We used to use alloca here, but the size of what it would try to
483 allocate would occasionally cause it to exceed the stack limit and
484 cause unpredictable core dumps. Some examples were > 2Mb in size. */
485 conflicts
= xcalloc (max_allocno
* allocno_row_words
, sizeof (INT_TYPE
));
487 allocnos_live
= xmalloc (allocno_row_words
* sizeof (INT_TYPE
));
489 /* If there is work to be done (at least one reg to allocate),
490 perform global conflict analysis and allocate the regs. */
494 /* Scan all the insns and compute the conflicts among allocnos
495 and between allocnos and hard regs. */
501 /* Eliminate conflicts between pseudos and eliminable registers. If
502 the register is not eliminated, the pseudo won't really be able to
503 live in the eliminable register, so the conflict doesn't matter.
504 If we do eliminate the register, the conflict will no longer exist.
505 So in either case, we can ignore the conflict. Likewise for
508 for (i
= 0; i
< (size_t) max_allocno
; i
++)
510 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_conflicts
,
512 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_copy_preferences
,
514 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_preferences
,
518 /* Try to expand the preferences by merging them between allocnos. */
520 expand_preferences ();
522 /* Determine the order to allocate the remaining pseudo registers. */
524 allocno_order
= xmalloc (max_allocno
* sizeof (int));
525 for (i
= 0; i
< (size_t) max_allocno
; i
++)
526 allocno_order
[i
] = i
;
528 /* Default the size to 1, since allocno_compare uses it to divide by.
529 Also convert allocno_live_length of zero to -1. A length of zero
530 can occur when all the registers for that allocno have reg_live_length
531 equal to -2. In this case, we want to make an allocno, but not
532 allocate it. So avoid the divide-by-zero and set it to a low
535 for (i
= 0; i
< (size_t) max_allocno
; i
++)
537 if (allocno
[i
].size
== 0)
539 if (allocno
[i
].live_length
== 0)
540 allocno
[i
].live_length
= -1;
543 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
545 prune_preferences ();
548 dump_conflicts (file
);
550 /* Try allocating them, one by one, in that order,
551 except for parameters marked with reg_live_length[regno] == -2. */
553 for (i
= 0; i
< (size_t) max_allocno
; i
++)
554 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] < 0
555 && REG_LIVE_LENGTH (allocno
[allocno_order
[i
]].reg
) >= 0)
557 /* If we have more than one register class,
558 first try allocating in the class that is cheapest
559 for this pseudo-reg. If that fails, try any reg. */
560 if (N_REG_CLASSES
> 1)
562 find_reg (allocno_order
[i
], 0, 0, 0, 0);
563 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
566 if (reg_alternate_class (allocno
[allocno_order
[i
]].reg
) != NO_REGS
)
567 find_reg (allocno_order
[i
], 0, 1, 0, 0);
570 free (allocno_order
);
573 /* Do the reloads now while the allocno data still exist, so that we can
574 try to assign new hard regs to any pseudo regs that are spilled. */
576 #if 0 /* We need to eliminate regs even if there is no rtl code,
577 for the sake of debugging information. */
578 if (n_basic_blocks
> 0)
581 build_insn_chain (get_insns ());
582 retval
= reload (get_insns (), 1);
587 free (reg_may_share
);
590 free (allocnos_live
);
595 /* Sort predicate for ordering the allocnos.
596 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
599 allocno_compare (const void *v1p
, const void *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 weighted by the frequency (maximally REG_FREQ_MAX).
606 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
608 = (((double) (floor_log2 (allocno
[v1
].n_refs
) * allocno
[v1
].freq
)
609 / allocno
[v1
].live_length
)
610 * (10000 / REG_FREQ_MAX
) * allocno
[v1
].size
);
612 = (((double) (floor_log2 (allocno
[v2
].n_refs
) * allocno
[v2
].freq
)
613 / allocno
[v2
].live_length
)
614 * (10000 / REG_FREQ_MAX
) * allocno
[v2
].size
);
618 /* If regs are equally good, sort by allocno,
619 so that the results of qsort leave nothing to chance. */
623 /* Scan the rtl code and record all conflicts and register preferences in the
624 conflict matrices and preference tables. */
627 global_conflicts (void)
632 int *block_start_allocnos
;
634 /* Make a vector that mark_reg_{store,clobber} will store in. */
635 regs_set
= xmalloc (max_parallel
* sizeof (rtx
) * 2);
637 block_start_allocnos
= xmalloc (max_allocno
* sizeof (int));
641 memset (allocnos_live
, 0, allocno_row_words
* sizeof (INT_TYPE
));
643 /* Initialize table of registers currently live
644 to the state at the beginning of this basic block.
645 This also marks the conflicts among hard registers
646 and any allocnos that are live.
648 For pseudo-regs, there is only one bit for each one
649 no matter how many hard regs it occupies.
650 This is ok; we know the size from PSEUDO_REGNO_SIZE.
651 For explicit hard regs, we cannot know the size that way
652 since one hard reg can be used with various sizes.
653 Therefore, we must require that all the hard regs
654 implicitly live as part of a multi-word hard reg
655 are explicitly marked in basic_block_live_at_start. */
658 regset old
= b
->global_live_at_start
;
661 REG_SET_TO_HARD_REG_SET (hard_regs_live
, old
);
662 EXECUTE_IF_SET_IN_REG_SET (old
, FIRST_PSEUDO_REGISTER
, i
,
664 int a
= reg_allocno
[i
];
667 SET_ALLOCNO_LIVE (a
);
668 block_start_allocnos
[ax
++] = a
;
670 else if ((a
= reg_renumber
[i
]) >= 0)
672 (a
, PSEUDO_REGNO_MODE (i
));
675 /* Record that each allocno now live conflicts with each hard reg
678 It is not necessary to mark any conflicts between pseudos as
679 this point, even for pseudos which are live at the start of
682 Given two pseudos X and Y and any point in the CFG P.
684 On any path to point P where X and Y are live one of the
685 following conditions must be true:
687 1. X is live at some instruction on the path that
690 2. Y is live at some instruction on the path that
693 3. Either X or Y is not evaluated on the path to P
694 (ie it is used uninitialized) and thus the
695 conflict can be ignored.
697 In cases #1 and #2 the conflict will be recorded when we
698 scan the instruction that makes either X or Y become live. */
699 record_conflicts (block_start_allocnos
, ax
);
701 /* Pseudos can't go in stack regs at the start of a basic block that
702 is reached by an abnormal edge. Likewise for call clobbered regs,
703 because because caller-save, fixup_abnormal_edges, and possibly
704 the table driven EH machinery are not quite ready to handle such
705 regs live across such edges. */
709 for (e
= b
->pred
; e
; e
= e
->pred_next
)
710 if (e
->flags
& EDGE_ABNORMAL
)
716 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, ax
,
718 allocno
[ax
].no_stack_reg
= 1;
720 for (ax
= FIRST_STACK_REG
; ax
<= LAST_STACK_REG
; ax
++)
721 record_one_conflict (ax
);
724 /* No need to record conflicts for call clobbered regs if we have
725 nonlocal labels around, as we don't ever try to allocate such
726 regs in this case. */
727 if (! current_function_has_nonlocal_label
)
728 for (ax
= 0; ax
< FIRST_PSEUDO_REGISTER
; ax
++)
729 if (call_used_regs
[ax
])
730 record_one_conflict (ax
);
737 /* Scan the code of this basic block, noting which allocnos
738 and hard regs are born or die. When one is born,
739 record a conflict with all others currently live. */
743 RTX_CODE code
= GET_CODE (insn
);
746 /* Make regs_set an empty set. */
750 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
755 for (link
= REG_NOTES (insn
);
756 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
757 link
= XEXP (link
, 1))
758 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
760 no_conflict_pairs
[i
].allocno1
761 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
762 no_conflict_pairs
[i
].allocno2
763 = reg_allocno
[REGNO (XEXP (link
, 0))];
768 /* Mark any registers clobbered by INSN as live,
769 so they conflict with the inputs. */
771 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
773 /* Mark any registers dead after INSN as dead now. */
775 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
776 if (REG_NOTE_KIND (link
) == REG_DEAD
)
777 mark_reg_death (XEXP (link
, 0));
779 /* Mark any registers set in INSN as live,
780 and mark them as conflicting with all other live regs.
781 Clobbers are processed again, so they conflict with
782 the registers that are set. */
784 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
787 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
788 if (REG_NOTE_KIND (link
) == REG_INC
)
789 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
792 /* If INSN has multiple outputs, then any reg that dies here
793 and is used inside of an output
794 must conflict with the other outputs.
796 It is unsafe to use !single_set here since it will ignore an
797 unused output. Just because an output is unused does not mean
798 the compiler can assume the side effect will not occur.
799 Consider if REG appears in the address of an output and we
800 reload the output. If we allocate REG to the same hard
801 register as an unused output we could set the hard register
802 before the output reload insn. */
803 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
804 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
805 if (REG_NOTE_KIND (link
) == REG_DEAD
)
807 int used_in_output
= 0;
809 rtx reg
= XEXP (link
, 0);
811 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
813 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
814 if (GET_CODE (set
) == SET
815 && GET_CODE (SET_DEST (set
)) != REG
816 && !rtx_equal_p (reg
, SET_DEST (set
))
817 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
821 mark_reg_conflicts (reg
);
824 /* Mark any registers set in INSN and then never used. */
826 while (n_regs_set
-- > 0)
828 rtx note
= find_regno_note (insn
, REG_UNUSED
,
829 REGNO (regs_set
[n_regs_set
]));
831 mark_reg_death (XEXP (note
, 0));
837 insn
= NEXT_INSN (insn
);
842 free (block_start_allocnos
);
845 /* Expand the preference information by looking for cases where one allocno
846 dies in an insn that sets an allocno. If those two allocnos don't conflict,
847 merge any preferences between those allocnos. */
850 expand_preferences (void)
856 /* We only try to handle the most common cases here. Most of the cases
857 where this wins are reg-reg copies. */
859 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
861 && (set
= single_set (insn
)) != 0
862 && GET_CODE (SET_DEST (set
)) == REG
863 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
864 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
865 if (REG_NOTE_KIND (link
) == REG_DEAD
866 && GET_CODE (XEXP (link
, 0)) == REG
867 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
868 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
869 reg_allocno
[REGNO (XEXP (link
, 0))]))
871 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
872 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
874 if (XEXP (link
, 0) == SET_SRC (set
))
876 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_copy_preferences
,
877 allocno
[a2
].hard_reg_copy_preferences
);
878 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_copy_preferences
,
879 allocno
[a1
].hard_reg_copy_preferences
);
882 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_preferences
,
883 allocno
[a2
].hard_reg_preferences
);
884 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_preferences
,
885 allocno
[a1
].hard_reg_preferences
);
886 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_full_preferences
,
887 allocno
[a2
].hard_reg_full_preferences
);
888 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_full_preferences
,
889 allocno
[a1
].hard_reg_full_preferences
);
893 /* Prune the preferences for global registers to exclude registers that cannot
896 Compute `regs_someone_prefers', which is a bitmask of the hard registers
897 that are preferred by conflicting registers of lower priority. If possible,
898 we will avoid using these registers. */
901 prune_preferences (void)
905 int *allocno_to_order
= xmalloc (max_allocno
* sizeof (int));
907 /* Scan least most important to most important.
908 For each allocno, remove from preferences registers that cannot be used,
909 either because of conflicts or register type. Then compute all registers
910 preferred by each lower-priority register that conflicts. */
912 for (i
= max_allocno
- 1; i
>= 0; i
--)
916 num
= allocno_order
[i
];
917 allocno_to_order
[num
] = i
;
918 COPY_HARD_REG_SET (temp
, allocno
[num
].hard_reg_conflicts
);
920 if (allocno
[num
].calls_crossed
== 0)
921 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
923 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
925 IOR_COMPL_HARD_REG_SET
927 reg_class_contents
[(int) reg_preferred_class (allocno
[num
].reg
)]);
929 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, temp
);
930 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, temp
);
931 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_full_preferences
, temp
);
934 for (i
= max_allocno
- 1; i
>= 0; i
--)
936 /* Merge in the preferences of lower-priority registers (they have
937 already been pruned). If we also prefer some of those registers,
938 don't exclude them unless we are of a smaller size (in which case
939 we want to give the lower-priority allocno the first chance for
941 HARD_REG_SET temp
, temp2
;
944 num
= allocno_order
[i
];
946 CLEAR_HARD_REG_SET (temp
);
947 CLEAR_HARD_REG_SET (temp2
);
949 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ num
* allocno_row_words
,
952 if (allocno_to_order
[allocno2
] > i
)
954 if (allocno
[allocno2
].size
<= allocno
[num
].size
)
955 IOR_HARD_REG_SET (temp
,
956 allocno
[allocno2
].hard_reg_full_preferences
);
958 IOR_HARD_REG_SET (temp2
,
959 allocno
[allocno2
].hard_reg_full_preferences
);
963 AND_COMPL_HARD_REG_SET (temp
, allocno
[num
].hard_reg_full_preferences
);
964 IOR_HARD_REG_SET (temp
, temp2
);
965 COPY_HARD_REG_SET (allocno
[num
].regs_someone_prefers
, temp
);
967 free (allocno_to_order
);
970 /* Assign a hard register to allocno NUM; look for one that is the beginning
971 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
972 The registers marked in PREFREGS are tried first.
974 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
975 be used for this allocation.
977 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
978 Otherwise ignore that preferred class and use the alternate class.
980 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
981 will have to be saved and restored at calls.
983 RETRYING is nonzero if this is called from retry_global_alloc.
985 If we find one, record it in reg_renumber.
986 If not, do nothing. */
989 find_reg (int num
, HARD_REG_SET losers
, int alt_regs_p
, int accept_call_clobbered
, int retrying
)
991 int i
, best_reg
, pass
;
992 HARD_REG_SET used
, used1
, used2
;
994 enum reg_class
class = (alt_regs_p
995 ? reg_alternate_class (allocno
[num
].reg
)
996 : reg_preferred_class (allocno
[num
].reg
));
997 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno
[num
].reg
);
999 if (accept_call_clobbered
)
1000 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
1001 else if (allocno
[num
].calls_crossed
== 0)
1002 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
1004 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
1006 /* Some registers should not be allocated in global-alloc. */
1007 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
1009 IOR_HARD_REG_SET (used1
, losers
);
1011 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
1012 COPY_HARD_REG_SET (used2
, used1
);
1014 IOR_HARD_REG_SET (used1
, allocno
[num
].hard_reg_conflicts
);
1016 #ifdef CANNOT_CHANGE_MODE_CLASS
1017 cannot_change_mode_set_regs (&used1
, mode
, allocno
[num
].reg
);
1020 /* Try each hard reg to see if it fits. Do this in two passes.
1021 In the first pass, skip registers that are preferred by some other pseudo
1022 to give it a better chance of getting one of those registers. Only if
1023 we can't get a register when excluding those do we take one of them.
1024 However, we never allocate a register for the first time in pass 0. */
1026 COPY_HARD_REG_SET (used
, used1
);
1027 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
1028 IOR_HARD_REG_SET (used
, allocno
[num
].regs_someone_prefers
);
1031 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
1032 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
1036 COPY_HARD_REG_SET (used
, used1
);
1037 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1039 #ifdef REG_ALLOC_ORDER
1040 int regno
= reg_alloc_order
[i
];
1044 if (! TEST_HARD_REG_BIT (used
, regno
)
1045 && HARD_REGNO_MODE_OK (regno
, mode
)
1046 && (allocno
[num
].calls_crossed
== 0
1047 || accept_call_clobbered
1048 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
)))
1051 int lim
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1054 && ! TEST_HARD_REG_BIT (used
, j
));
1061 #ifndef REG_ALLOC_ORDER
1062 i
= j
; /* Skip starting points we know will lose */
1068 /* See if there is a preferred register with the same class as the register
1069 we allocated above. Making this restriction prevents register
1070 preferencing from creating worse register allocation.
1072 Remove from the preferred registers and conflicting registers. Note that
1073 additional conflicts may have been added after `prune_preferences' was
1076 First do this for those register with copy preferences, then all
1077 preferred registers. */
1079 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, used
);
1080 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_copy_preferences
,
1081 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
1085 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1086 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_copy_preferences
, i
)
1087 && HARD_REGNO_MODE_OK (i
, mode
)
1088 && (allocno
[num
].calls_crossed
== 0
1089 || accept_call_clobbered
1090 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1091 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1092 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1093 REGNO_REG_CLASS (best_reg
))
1094 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1095 REGNO_REG_CLASS (i
))))
1098 int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1101 && ! TEST_HARD_REG_BIT (used
, j
)
1102 && (REGNO_REG_CLASS (j
)
1103 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1104 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1105 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1106 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1107 REGNO_REG_CLASS (j
))));
1118 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, used
);
1119 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_preferences
,
1120 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1124 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1125 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_preferences
, i
)
1126 && HARD_REGNO_MODE_OK (i
, mode
)
1127 && (allocno
[num
].calls_crossed
== 0
1128 || accept_call_clobbered
1129 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1130 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1131 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1132 REGNO_REG_CLASS (best_reg
))
1133 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1134 REGNO_REG_CLASS (i
))))
1137 int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1140 && ! TEST_HARD_REG_BIT (used
, j
)
1141 && (REGNO_REG_CLASS (j
)
1142 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1143 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1144 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1145 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1146 REGNO_REG_CLASS (j
))));
1157 /* If we haven't succeeded yet, try with caller-saves.
1158 We need not check to see if the current function has nonlocal
1159 labels because we don't put any pseudos that are live over calls in
1160 registers in that case. */
1162 if (flag_caller_saves
&& best_reg
< 0)
1164 /* Did not find a register. If it would be profitable to
1165 allocate a call-clobbered register and save and restore it
1166 around calls, do that. */
1167 if (! accept_call_clobbered
1168 && allocno
[num
].calls_crossed
!= 0
1169 && CALLER_SAVE_PROFITABLE (allocno
[num
].n_refs
,
1170 allocno
[num
].calls_crossed
))
1172 HARD_REG_SET new_losers
;
1174 CLEAR_HARD_REG_SET (new_losers
);
1176 COPY_HARD_REG_SET (new_losers
, losers
);
1178 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1179 find_reg (num
, new_losers
, alt_regs_p
, 1, retrying
);
1180 if (reg_renumber
[allocno
[num
].reg
] >= 0)
1182 caller_save_needed
= 1;
1188 /* If we haven't succeeded yet,
1189 see if some hard reg that conflicts with us
1190 was utilized poorly by local-alloc.
1191 If so, kick out the regs that were put there by local-alloc
1192 so we can use it instead. */
1193 if (best_reg
< 0 && !retrying
1194 /* Let's not bother with multi-reg allocnos. */
1195 && allocno
[num
].size
== 1)
1197 /* Count from the end, to find the least-used ones first. */
1198 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1200 #ifdef REG_ALLOC_ORDER
1201 int regno
= reg_alloc_order
[i
];
1206 if (local_reg_n_refs
[regno
] != 0
1207 /* Don't use a reg no good for this pseudo. */
1208 && ! TEST_HARD_REG_BIT (used2
, regno
)
1209 && HARD_REGNO_MODE_OK (regno
, mode
)
1210 /* The code below assumes that we need only a single
1211 register, but the check of allocno[num].size above
1212 was not enough. Sometimes we need more than one
1213 register for a single-word value. */
1214 && HARD_REGNO_NREGS (regno
, mode
) == 1
1215 && (allocno
[num
].calls_crossed
== 0
1216 || accept_call_clobbered
1217 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
))
1218 #ifdef CANNOT_CHANGE_MODE_CLASS
1219 && ! invalid_mode_change_p (regno
, REGNO_REG_CLASS (regno
),
1223 && (!allocno
[num
].no_stack_reg
1224 || regno
< FIRST_STACK_REG
|| regno
> LAST_STACK_REG
)
1228 /* We explicitly evaluate the divide results into temporary
1229 variables so as to avoid excess precision problems that occur
1230 on an i386-unknown-sysv4.2 (unixware) host. */
1232 double tmp1
= ((double) local_reg_freq
[regno
]
1233 / local_reg_live_length
[regno
]);
1234 double tmp2
= ((double) allocno
[num
].freq
1235 / allocno
[num
].live_length
);
1239 /* Hard reg REGNO was used less in total by local regs
1240 than it would be used by this one allocno! */
1242 for (k
= 0; k
< max_regno
; k
++)
1243 if (reg_renumber
[k
] >= 0)
1245 int r
= reg_renumber
[k
];
1247 = r
+ HARD_REGNO_NREGS (r
, PSEUDO_REGNO_MODE (k
));
1249 if (regno
>= r
&& regno
< endregno
)
1250 reg_renumber
[k
] = -1;
1260 /* Did we find a register? */
1265 HARD_REG_SET this_reg
;
1267 /* Yes. Record it as the hard register of this pseudo-reg. */
1268 reg_renumber
[allocno
[num
].reg
] = best_reg
;
1269 /* Also of any pseudo-regs that share with it. */
1270 if (reg_may_share
[allocno
[num
].reg
])
1271 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1272 if (reg_allocno
[j
] == num
)
1273 reg_renumber
[j
] = best_reg
;
1275 /* Make a set of the hard regs being allocated. */
1276 CLEAR_HARD_REG_SET (this_reg
);
1277 lim
= best_reg
+ HARD_REGNO_NREGS (best_reg
, mode
);
1278 for (j
= best_reg
; j
< lim
; j
++)
1280 SET_HARD_REG_BIT (this_reg
, j
);
1281 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1282 /* This is no longer a reg used just by local regs. */
1283 local_reg_n_refs
[j
] = 0;
1284 local_reg_freq
[j
] = 0;
1286 /* For each other pseudo-reg conflicting with this one,
1287 mark it as conflicting with the hard regs this one occupies. */
1289 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ lim
* allocno_row_words
, j
,
1291 IOR_HARD_REG_SET (allocno
[j
].hard_reg_conflicts
, this_reg
);
1296 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1297 Perhaps it had previously seemed not worth a hard reg,
1298 or perhaps its old hard reg has been commandeered for reloads.
1299 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1300 they do not appear to be allocated.
1301 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1304 retry_global_alloc (int regno
, HARD_REG_SET forbidden_regs
)
1306 int alloc_no
= reg_allocno
[regno
];
1309 /* If we have more than one register class,
1310 first try allocating in the class that is cheapest
1311 for this pseudo-reg. If that fails, try any reg. */
1312 if (N_REG_CLASSES
> 1)
1313 find_reg (alloc_no
, forbidden_regs
, 0, 0, 1);
1314 if (reg_renumber
[regno
] < 0
1315 && reg_alternate_class (regno
) != NO_REGS
)
1316 find_reg (alloc_no
, forbidden_regs
, 1, 0, 1);
1318 /* If we found a register, modify the RTL for the register to
1319 show the hard register, and mark that register live. */
1320 if (reg_renumber
[regno
] >= 0)
1322 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1323 mark_home_live (regno
);
1328 /* Record a conflict between register REGNO
1329 and everything currently live.
1330 REGNO must not be a pseudo reg that was allocated
1331 by local_alloc; such numbers must be translated through
1332 reg_renumber before calling here. */
1335 record_one_conflict (int regno
)
1339 if (regno
< FIRST_PSEUDO_REGISTER
)
1340 /* When a hard register becomes live,
1341 record conflicts with live pseudo regs. */
1342 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, j
,
1344 SET_HARD_REG_BIT (allocno
[j
].hard_reg_conflicts
, regno
);
1347 /* When a pseudo-register becomes live,
1348 record conflicts first with hard regs,
1349 then with other pseudo regs. */
1351 int ialloc
= reg_allocno
[regno
];
1352 int ialloc_prod
= ialloc
* allocno_row_words
;
1354 IOR_HARD_REG_SET (allocno
[ialloc
].hard_reg_conflicts
, hard_regs_live
);
1355 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1359 for (k
= 0; k
< n_no_conflict_pairs
; k
++)
1360 if (! ((j
== no_conflict_pairs
[k
].allocno1
1361 && ialloc
== no_conflict_pairs
[k
].allocno2
)
1363 (j
== no_conflict_pairs
[k
].allocno2
1364 && ialloc
== no_conflict_pairs
[k
].allocno1
)))
1366 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1371 /* Record all allocnos currently live as conflicting
1372 with all hard regs currently live.
1374 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1375 are currently live. Their bits are also flagged in allocnos_live. */
1378 record_conflicts (int *allocno_vec
, int len
)
1381 IOR_HARD_REG_SET (allocno
[allocno_vec
[len
]].hard_reg_conflicts
,
1385 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1387 mirror_conflicts (void)
1390 int rw
= allocno_row_words
;
1391 int rwb
= rw
* INT_BITS
;
1392 INT_TYPE
*p
= conflicts
;
1393 INT_TYPE
*q0
= conflicts
, *q1
, *q2
;
1394 unsigned INT_TYPE mask
;
1396 for (i
= max_allocno
- 1, mask
= 1; i
>= 0; i
--, mask
<<= 1)
1403 for (j
= allocno_row_words
- 1, q1
= q0
; j
>= 0; j
--, q1
+= rwb
)
1405 unsigned INT_TYPE word
;
1407 for (word
= (unsigned INT_TYPE
) *p
++, q2
= q1
; word
;
1408 word
>>= 1, q2
+= rw
)
1417 /* Handle the case where REG is set by the insn being scanned,
1418 during the forward scan to accumulate conflicts.
1419 Store a 1 in regs_live or allocnos_live for this register, record how many
1420 consecutive hardware registers it actually needs,
1421 and record a conflict with all other registers already live.
1423 Note that even if REG does not remain alive after this insn,
1424 we must mark it here as live, to ensure a conflict between
1425 REG and any other regs set in this insn that really do live.
1426 This is because those other regs could be considered after this.
1428 REG might actually be something other than a register;
1429 if so, we do nothing.
1431 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1432 a REG_INC note was found for it). */
1435 mark_reg_store (rtx reg
, rtx setter
, void *data ATTRIBUTE_UNUSED
)
1439 if (GET_CODE (reg
) == SUBREG
)
1440 reg
= SUBREG_REG (reg
);
1442 if (GET_CODE (reg
) != REG
)
1445 regs_set
[n_regs_set
++] = reg
;
1447 if (setter
&& GET_CODE (setter
) != CLOBBER
)
1448 set_preference (reg
, SET_SRC (setter
));
1450 regno
= REGNO (reg
);
1452 /* Either this is one of the max_allocno pseudo regs not allocated,
1453 or it is or has a hardware reg. First handle the pseudo-regs. */
1454 if (regno
>= FIRST_PSEUDO_REGISTER
)
1456 if (reg_allocno
[regno
] >= 0)
1458 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1459 record_one_conflict (regno
);
1463 if (reg_renumber
[regno
] >= 0)
1464 regno
= reg_renumber
[regno
];
1466 /* Handle hardware regs (and pseudos allocated to hard regs). */
1467 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1469 int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1470 while (regno
< last
)
1472 record_one_conflict (regno
);
1473 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1479 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1482 mark_reg_clobber (rtx reg
, rtx setter
, void *data ATTRIBUTE_UNUSED
)
1484 if (GET_CODE (setter
) == CLOBBER
)
1485 mark_reg_store (reg
, setter
, data
);
1488 /* Record that REG has conflicts with all the regs currently live.
1489 Do not mark REG itself as live. */
1492 mark_reg_conflicts (rtx reg
)
1496 if (GET_CODE (reg
) == SUBREG
)
1497 reg
= SUBREG_REG (reg
);
1499 if (GET_CODE (reg
) != REG
)
1502 regno
= REGNO (reg
);
1504 /* Either this is one of the max_allocno pseudo regs not allocated,
1505 or it is or has a hardware reg. First handle the pseudo-regs. */
1506 if (regno
>= FIRST_PSEUDO_REGISTER
)
1508 if (reg_allocno
[regno
] >= 0)
1509 record_one_conflict (regno
);
1512 if (reg_renumber
[regno
] >= 0)
1513 regno
= reg_renumber
[regno
];
1515 /* Handle hardware regs (and pseudos allocated to hard regs). */
1516 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1518 int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1519 while (regno
< last
)
1521 record_one_conflict (regno
);
1527 /* Mark REG as being dead (following the insn being scanned now).
1528 Store a 0 in regs_live or allocnos_live for this register. */
1531 mark_reg_death (rtx reg
)
1533 int regno
= REGNO (reg
);
1535 /* Either this is one of the max_allocno pseudo regs not allocated,
1536 or it is a hardware reg. First handle the pseudo-regs. */
1537 if (regno
>= FIRST_PSEUDO_REGISTER
)
1539 if (reg_allocno
[regno
] >= 0)
1540 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1543 /* For pseudo reg, see if it has been assigned a hardware reg. */
1544 if (reg_renumber
[regno
] >= 0)
1545 regno
= reg_renumber
[regno
];
1547 /* Handle hardware regs (and pseudos allocated to hard regs). */
1548 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1550 /* Pseudo regs already assigned hardware regs are treated
1551 almost the same as explicit hardware regs. */
1552 int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1553 while (regno
< last
)
1555 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1561 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1562 for the value stored in it. MODE determines how many consecutive
1563 registers are actually in use. Do not record conflicts;
1564 it is assumed that the caller will do that. */
1567 mark_reg_live_nc (int regno
, enum machine_mode mode
)
1569 int last
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1570 while (regno
< last
)
1572 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1577 /* Try to set a preference for an allocno to a hard register.
1578 We are passed DEST and SRC which are the operands of a SET. It is known
1579 that SRC is a register. If SRC or the first operand of SRC is a register,
1580 try to set a preference. If one of the two is a hard register and the other
1581 is a pseudo-register, mark the preference.
1583 Note that we are not as aggressive as local-alloc in trying to tie a
1584 pseudo-register to a hard register. */
1587 set_preference (rtx dest
, rtx src
)
1589 unsigned int src_regno
, dest_regno
;
1590 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1591 to compensate for subregs in SRC or DEST. */
1596 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1597 src
= XEXP (src
, 0), copy
= 0;
1599 /* Get the reg number for both SRC and DEST.
1600 If neither is a reg, give up. */
1602 if (GET_CODE (src
) == REG
)
1603 src_regno
= REGNO (src
);
1604 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1606 src_regno
= REGNO (SUBREG_REG (src
));
1608 if (REGNO (SUBREG_REG (src
)) < FIRST_PSEUDO_REGISTER
)
1609 offset
+= subreg_regno_offset (REGNO (SUBREG_REG (src
)),
1610 GET_MODE (SUBREG_REG (src
)),
1614 offset
+= (SUBREG_BYTE (src
)
1615 / REGMODE_NATURAL_SIZE (GET_MODE (src
)));
1620 if (GET_CODE (dest
) == REG
)
1621 dest_regno
= REGNO (dest
);
1622 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1624 dest_regno
= REGNO (SUBREG_REG (dest
));
1626 if (REGNO (SUBREG_REG (dest
)) < FIRST_PSEUDO_REGISTER
)
1627 offset
-= subreg_regno_offset (REGNO (SUBREG_REG (dest
)),
1628 GET_MODE (SUBREG_REG (dest
)),
1632 offset
-= (SUBREG_BYTE (dest
)
1633 / REGMODE_NATURAL_SIZE (GET_MODE (dest
)));
1638 /* Convert either or both to hard reg numbers. */
1640 if (reg_renumber
[src_regno
] >= 0)
1641 src_regno
= reg_renumber
[src_regno
];
1643 if (reg_renumber
[dest_regno
] >= 0)
1644 dest_regno
= reg_renumber
[dest_regno
];
1646 /* Now if one is a hard reg and the other is a global pseudo
1647 then give the other a preference. */
1649 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1650 && reg_allocno
[src_regno
] >= 0)
1652 dest_regno
-= offset
;
1653 if (dest_regno
< FIRST_PSEUDO_REGISTER
)
1656 SET_REGBIT (hard_reg_copy_preferences
,
1657 reg_allocno
[src_regno
], dest_regno
);
1659 SET_REGBIT (hard_reg_preferences
,
1660 reg_allocno
[src_regno
], dest_regno
);
1661 for (i
= dest_regno
;
1662 i
< dest_regno
+ HARD_REGNO_NREGS (dest_regno
, GET_MODE (dest
));
1664 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1668 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1669 && reg_allocno
[dest_regno
] >= 0)
1671 src_regno
+= offset
;
1672 if (src_regno
< FIRST_PSEUDO_REGISTER
)
1675 SET_REGBIT (hard_reg_copy_preferences
,
1676 reg_allocno
[dest_regno
], src_regno
);
1678 SET_REGBIT (hard_reg_preferences
,
1679 reg_allocno
[dest_regno
], src_regno
);
1681 i
< src_regno
+ HARD_REGNO_NREGS (src_regno
, GET_MODE (src
));
1683 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1688 /* Indicate that hard register number FROM was eliminated and replaced with
1689 an offset from hard register number TO. The status of hard registers live
1690 at the start of a basic block is updated by replacing a use of FROM with
1694 mark_elimination (int from
, int to
)
1700 regset r
= bb
->global_live_at_start
;
1701 if (REGNO_REG_SET_P (r
, from
))
1703 CLEAR_REGNO_REG_SET (r
, from
);
1704 SET_REGNO_REG_SET (r
, to
);
1709 /* Used for communication between the following functions. Holds the
1710 current life information. */
1711 static regset live_relevant_regs
;
1713 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1714 This is called via note_stores. */
1716 reg_becomes_live (rtx reg
, rtx setter ATTRIBUTE_UNUSED
, void *regs_set
)
1720 if (GET_CODE (reg
) == SUBREG
)
1721 reg
= SUBREG_REG (reg
);
1723 if (GET_CODE (reg
) != REG
)
1726 regno
= REGNO (reg
);
1727 if (regno
< FIRST_PSEUDO_REGISTER
)
1729 int nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1732 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1733 if (! fixed_regs
[regno
])
1734 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1738 else if (reg_renumber
[regno
] >= 0)
1740 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1741 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1745 /* Record in live_relevant_regs that register REGNO died. */
1747 reg_dies (int regno
, enum machine_mode mode
, struct insn_chain
*chain
)
1749 if (regno
< FIRST_PSEUDO_REGISTER
)
1751 int nregs
= HARD_REGNO_NREGS (regno
, mode
);
1754 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1755 if (! fixed_regs
[regno
])
1756 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1762 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1763 if (reg_renumber
[regno
] >= 0)
1764 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1768 /* Walk the insns of the current function and build reload_insn_chain,
1769 and record register life information. */
1771 build_insn_chain (rtx first
)
1773 struct insn_chain
**p
= &reload_insn_chain
;
1774 struct insn_chain
*prev
= 0;
1775 basic_block b
= ENTRY_BLOCK_PTR
->next_bb
;
1776 regset_head live_relevant_regs_head
;
1778 live_relevant_regs
= INITIALIZE_REG_SET (live_relevant_regs_head
);
1780 for (; first
; first
= NEXT_INSN (first
))
1782 struct insn_chain
*c
;
1784 if (first
== b
->head
)
1788 CLEAR_REG_SET (live_relevant_regs
);
1790 EXECUTE_IF_SET_IN_BITMAP
1791 (b
->global_live_at_start
, 0, i
,
1793 if (i
< FIRST_PSEUDO_REGISTER
1794 ? ! TEST_HARD_REG_BIT (eliminable_regset
, i
)
1795 : reg_renumber
[i
] >= 0)
1796 SET_REGNO_REG_SET (live_relevant_regs
, i
);
1800 if (GET_CODE (first
) != NOTE
&& GET_CODE (first
) != BARRIER
)
1802 c
= new_insn_chain ();
1808 c
->block
= b
->index
;
1814 /* Mark the death of everything that dies in this instruction. */
1816 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1817 if (REG_NOTE_KIND (link
) == REG_DEAD
1818 && GET_CODE (XEXP (link
, 0)) == REG
)
1819 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1822 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1824 /* Mark everything born in this instruction as live. */
1826 note_stores (PATTERN (first
), reg_becomes_live
,
1830 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1836 /* Mark anything that is set in this insn and then unused as dying. */
1838 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1839 if (REG_NOTE_KIND (link
) == REG_UNUSED
1840 && GET_CODE (XEXP (link
, 0)) == REG
)
1841 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1846 if (first
== b
->end
)
1849 /* Stop after we pass the end of the last basic block. Verify that
1850 no real insns are after the end of the last basic block.
1852 We may want to reorganize the loop somewhat since this test should
1853 always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if
1854 the previous real insn is a JUMP_INSN. */
1855 if (b
== EXIT_BLOCK_PTR
)
1857 for (first
= NEXT_INSN (first
) ; first
; first
= NEXT_INSN (first
))
1859 && GET_CODE (PATTERN (first
)) != USE
1860 && ! ((GET_CODE (PATTERN (first
)) == ADDR_VEC
1861 || GET_CODE (PATTERN (first
)) == ADDR_DIFF_VEC
)
1862 && prev_real_insn (first
) != 0
1863 && GET_CODE (prev_real_insn (first
)) == JUMP_INSN
))
1868 FREE_REG_SET (live_relevant_regs
);
1872 /* Print debugging trace information if -dg switch is given,
1873 showing the information on which the allocation decisions are based. */
1876 dump_conflicts (FILE *file
)
1879 int has_preferences
;
1882 for (i
= 0; i
< max_allocno
; i
++)
1884 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1888 fprintf (file
, ";; %d regs to allocate:", nregs
);
1889 for (i
= 0; i
< max_allocno
; i
++)
1892 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1894 fprintf (file
, " %d", allocno
[allocno_order
[i
]].reg
);
1895 for (j
= 0; j
< max_regno
; j
++)
1896 if (reg_allocno
[j
] == allocno_order
[i
]
1897 && j
!= allocno
[allocno_order
[i
]].reg
)
1898 fprintf (file
, "+%d", j
);
1899 if (allocno
[allocno_order
[i
]].size
!= 1)
1900 fprintf (file
, " (%d)", allocno
[allocno_order
[i
]].size
);
1902 fprintf (file
, "\n");
1904 for (i
= 0; i
< max_allocno
; i
++)
1907 fprintf (file
, ";; %d conflicts:", allocno
[i
].reg
);
1908 for (j
= 0; j
< max_allocno
; j
++)
1909 if (CONFLICTP (j
, i
))
1910 fprintf (file
, " %d", allocno
[j
].reg
);
1911 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1912 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_conflicts
, j
))
1913 fprintf (file
, " %d", j
);
1914 fprintf (file
, "\n");
1916 has_preferences
= 0;
1917 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1918 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1919 has_preferences
= 1;
1921 if (! has_preferences
)
1923 fprintf (file
, ";; %d preferences:", allocno
[i
].reg
);
1924 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1925 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1926 fprintf (file
, " %d", j
);
1927 fprintf (file
, "\n");
1929 fprintf (file
, "\n");
1933 dump_global_regs (FILE *file
)
1937 fprintf (file
, ";; Register dispositions:\n");
1938 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1939 if (reg_renumber
[i
] >= 0)
1941 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1943 fprintf (file
, "\n");
1946 fprintf (file
, "\n\n;; Hard regs used: ");
1947 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1948 if (regs_ever_live
[i
])
1949 fprintf (file
, " %d", i
);
1950 fprintf (file
, "\n\n");