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
++)
347 = (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
348 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
));
350 if (!regs_asm_clobbered
[eliminables
[i
].from
])
352 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
355 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
357 else if (cannot_elim
)
358 error ("%s cannot be used in asm here",
359 reg_names
[eliminables
[i
].from
]);
361 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
362 if (!regs_asm_clobbered
[HARD_FRAME_POINTER_REGNUM
])
364 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
366 SET_HARD_REG_BIT (no_global_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
369 error ("%s cannot be used in asm here",
370 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
374 if (!regs_asm_clobbered
[FRAME_POINTER_REGNUM
])
376 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
378 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
381 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
384 /* Track which registers have already been used. Start with registers
385 explicitly in the rtl, then registers allocated by local register
388 CLEAR_HARD_REG_SET (regs_used_so_far
);
389 #ifdef LEAF_REGISTERS
390 /* If we are doing the leaf function optimization, and this is a leaf
391 function, it means that the registers that take work to save are those
392 that need a register window. So prefer the ones that can be used in
395 const char *cheap_regs
;
396 const char *const leaf_regs
= LEAF_REGISTERS
;
398 if (only_leaf_regs_used () && leaf_function_p ())
399 cheap_regs
= leaf_regs
;
401 cheap_regs
= call_used_regs
;
402 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
403 if (regs_ever_live
[i
] || cheap_regs
[i
])
404 SET_HARD_REG_BIT (regs_used_so_far
, i
);
407 /* We consider registers that do not have to be saved over calls as if
408 they were already used since there is no cost in using them. */
409 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
410 if (regs_ever_live
[i
] || call_used_regs
[i
])
411 SET_HARD_REG_BIT (regs_used_so_far
, i
);
414 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
415 if (reg_renumber
[i
] >= 0)
416 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
418 /* Establish mappings from register number to allocation number
419 and vice versa. In the process, count the allocnos. */
421 reg_allocno
= xmalloc (max_regno
* sizeof (int));
423 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
426 /* Initialize the shared-hard-reg mapping
427 from the list of pairs that may share. */
428 reg_may_share
= xcalloc (max_regno
, sizeof (int));
429 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
431 int r1
= REGNO (XEXP (x
, 0));
432 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
434 reg_may_share
[r1
] = r2
;
436 reg_may_share
[r2
] = r1
;
439 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
440 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
441 that we are supposed to refrain from putting in a hard reg.
442 -2 means do make an allocno but don't allocate it. */
443 if (REG_N_REFS (i
) != 0 && REG_LIVE_LENGTH (i
) != -1
444 /* Don't allocate pseudos that cross calls,
445 if this function receives a nonlocal goto. */
446 && (! current_function_has_nonlocal_label
447 || REG_N_CALLS_CROSSED (i
) == 0))
449 if (reg_renumber
[i
] < 0 && reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
450 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
452 reg_allocno
[i
] = max_allocno
++;
453 if (REG_LIVE_LENGTH (i
) == 0)
459 allocno
= xcalloc (max_allocno
, sizeof (struct allocno
));
461 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
462 if (reg_allocno
[i
] >= 0)
464 int num
= reg_allocno
[i
];
465 allocno
[num
].reg
= i
;
466 allocno
[num
].size
= PSEUDO_REGNO_SIZE (i
);
467 allocno
[num
].calls_crossed
+= REG_N_CALLS_CROSSED (i
);
468 allocno
[num
].n_refs
+= REG_N_REFS (i
);
469 allocno
[num
].freq
+= REG_FREQ (i
);
470 if (allocno
[num
].live_length
< REG_LIVE_LENGTH (i
))
471 allocno
[num
].live_length
= REG_LIVE_LENGTH (i
);
474 /* Calculate amount of usage of each hard reg by pseudos
475 allocated by local-alloc. This is to see if we want to
477 memset (local_reg_live_length
, 0, sizeof local_reg_live_length
);
478 memset (local_reg_n_refs
, 0, sizeof local_reg_n_refs
);
479 memset (local_reg_freq
, 0, sizeof local_reg_freq
);
480 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
481 if (reg_renumber
[i
] >= 0)
483 int regno
= reg_renumber
[i
];
484 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, PSEUDO_REGNO_MODE (i
));
487 for (j
= regno
; j
< endregno
; j
++)
489 local_reg_n_refs
[j
] += REG_N_REFS (i
);
490 local_reg_freq
[j
] += REG_FREQ (i
);
491 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
495 /* We can't override local-alloc for a reg used not just by local-alloc. */
496 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
497 if (regs_ever_live
[i
])
498 local_reg_n_refs
[i
] = 0, local_reg_freq
[i
] = 0;
500 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
502 /* We used to use alloca here, but the size of what it would try to
503 allocate would occasionally cause it to exceed the stack limit and
504 cause unpredictable core dumps. Some examples were > 2Mb in size. */
505 conflicts
= xcalloc (max_allocno
* allocno_row_words
, sizeof (INT_TYPE
));
507 allocnos_live
= xmalloc (allocno_row_words
* sizeof (INT_TYPE
));
509 /* If there is work to be done (at least one reg to allocate),
510 perform global conflict analysis and allocate the regs. */
514 /* Scan all the insns and compute the conflicts among allocnos
515 and between allocnos and hard regs. */
521 /* Eliminate conflicts between pseudos and eliminable registers. If
522 the register is not eliminated, the pseudo won't really be able to
523 live in the eliminable register, so the conflict doesn't matter.
524 If we do eliminate the register, the conflict will no longer exist.
525 So in either case, we can ignore the conflict. Likewise for
528 for (i
= 0; i
< (size_t) max_allocno
; i
++)
530 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_conflicts
,
532 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_copy_preferences
,
534 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_preferences
,
538 /* Try to expand the preferences by merging them between allocnos. */
540 expand_preferences ();
542 /* Determine the order to allocate the remaining pseudo registers. */
544 allocno_order
= xmalloc (max_allocno
* sizeof (int));
545 for (i
= 0; i
< (size_t) max_allocno
; i
++)
546 allocno_order
[i
] = i
;
548 /* Default the size to 1, since allocno_compare uses it to divide by.
549 Also convert allocno_live_length of zero to -1. A length of zero
550 can occur when all the registers for that allocno have reg_live_length
551 equal to -2. In this case, we want to make an allocno, but not
552 allocate it. So avoid the divide-by-zero and set it to a low
555 for (i
= 0; i
< (size_t) max_allocno
; i
++)
557 if (allocno
[i
].size
== 0)
559 if (allocno
[i
].live_length
== 0)
560 allocno
[i
].live_length
= -1;
563 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
565 prune_preferences ();
568 dump_conflicts (file
);
570 /* Try allocating them, one by one, in that order,
571 except for parameters marked with reg_live_length[regno] == -2. */
573 for (i
= 0; i
< (size_t) max_allocno
; i
++)
574 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] < 0
575 && REG_LIVE_LENGTH (allocno
[allocno_order
[i
]].reg
) >= 0)
577 /* If we have more than one register class,
578 first try allocating in the class that is cheapest
579 for this pseudo-reg. If that fails, try any reg. */
580 if (N_REG_CLASSES
> 1)
582 find_reg (allocno_order
[i
], 0, 0, 0, 0);
583 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
586 if (reg_alternate_class (allocno
[allocno_order
[i
]].reg
) != NO_REGS
)
587 find_reg (allocno_order
[i
], 0, 1, 0, 0);
590 free (allocno_order
);
593 /* Do the reloads now while the allocno data still exist, so that we can
594 try to assign new hard regs to any pseudo regs that are spilled. */
596 #if 0 /* We need to eliminate regs even if there is no rtl code,
597 for the sake of debugging information. */
598 if (n_basic_blocks
> 0)
601 build_insn_chain (get_insns ());
602 retval
= reload (get_insns (), 1);
607 free (reg_may_share
);
610 free (allocnos_live
);
615 /* Sort predicate for ordering the allocnos.
616 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
619 allocno_compare (const void *v1p
, const void *v2p
)
621 int v1
= *(const int *)v1p
, v2
= *(const int *)v2p
;
622 /* Note that the quotient will never be bigger than
623 the value of floor_log2 times the maximum number of
624 times a register can occur in one insn (surely less than 100)
625 weighted by the frequency (maximally REG_FREQ_MAX).
626 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
628 = (((double) (floor_log2 (allocno
[v1
].n_refs
) * allocno
[v1
].freq
)
629 / allocno
[v1
].live_length
)
630 * (10000 / REG_FREQ_MAX
) * allocno
[v1
].size
);
632 = (((double) (floor_log2 (allocno
[v2
].n_refs
) * allocno
[v2
].freq
)
633 / allocno
[v2
].live_length
)
634 * (10000 / REG_FREQ_MAX
) * allocno
[v2
].size
);
638 /* If regs are equally good, sort by allocno,
639 so that the results of qsort leave nothing to chance. */
643 /* Scan the rtl code and record all conflicts and register preferences in the
644 conflict matrices and preference tables. */
647 global_conflicts (void)
652 int *block_start_allocnos
;
654 /* Make a vector that mark_reg_{store,clobber} will store in. */
655 regs_set
= xmalloc (max_parallel
* sizeof (rtx
) * 2);
657 block_start_allocnos
= xmalloc (max_allocno
* sizeof (int));
661 memset (allocnos_live
, 0, allocno_row_words
* sizeof (INT_TYPE
));
663 /* Initialize table of registers currently live
664 to the state at the beginning of this basic block.
665 This also marks the conflicts among hard registers
666 and any allocnos that are live.
668 For pseudo-regs, there is only one bit for each one
669 no matter how many hard regs it occupies.
670 This is ok; we know the size from PSEUDO_REGNO_SIZE.
671 For explicit hard regs, we cannot know the size that way
672 since one hard reg can be used with various sizes.
673 Therefore, we must require that all the hard regs
674 implicitly live as part of a multi-word hard reg
675 are explicitly marked in basic_block_live_at_start. */
678 regset old
= b
->global_live_at_start
;
681 REG_SET_TO_HARD_REG_SET (hard_regs_live
, old
);
682 EXECUTE_IF_SET_IN_REG_SET (old
, FIRST_PSEUDO_REGISTER
, i
,
684 int a
= reg_allocno
[i
];
687 SET_ALLOCNO_LIVE (a
);
688 block_start_allocnos
[ax
++] = a
;
690 else if ((a
= reg_renumber
[i
]) >= 0)
692 (a
, PSEUDO_REGNO_MODE (i
));
695 /* Record that each allocno now live conflicts with each hard reg
698 It is not necessary to mark any conflicts between pseudos as
699 this point, even for pseudos which are live at the start of
702 Given two pseudos X and Y and any point in the CFG P.
704 On any path to point P where X and Y are live one of the
705 following conditions must be true:
707 1. X is live at some instruction on the path that
710 2. Y is live at some instruction on the path that
713 3. Either X or Y is not evaluated on the path to P
714 (ie it is used uninitialized) and thus the
715 conflict can be ignored.
717 In cases #1 and #2 the conflict will be recorded when we
718 scan the instruction that makes either X or Y become live. */
719 record_conflicts (block_start_allocnos
, ax
);
721 /* Pseudos can't go in stack regs at the start of a basic block that
722 is reached by an abnormal edge. Likewise for call clobbered regs,
723 because because caller-save, fixup_abnormal_edges, and possibly
724 the table driven EH machinery are not quite ready to handle such
725 regs live across such edges. */
729 for (e
= b
->pred
; e
; e
= e
->pred_next
)
730 if (e
->flags
& EDGE_ABNORMAL
)
736 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, ax
,
738 allocno
[ax
].no_stack_reg
= 1;
740 for (ax
= FIRST_STACK_REG
; ax
<= LAST_STACK_REG
; ax
++)
741 record_one_conflict (ax
);
744 /* No need to record conflicts for call clobbered regs if we have
745 nonlocal labels around, as we don't ever try to allocate such
746 regs in this case. */
747 if (! current_function_has_nonlocal_label
)
748 for (ax
= 0; ax
< FIRST_PSEUDO_REGISTER
; ax
++)
749 if (call_used_regs
[ax
])
750 record_one_conflict (ax
);
757 /* Scan the code of this basic block, noting which allocnos
758 and hard regs are born or die. When one is born,
759 record a conflict with all others currently live. */
763 RTX_CODE code
= GET_CODE (insn
);
766 /* Make regs_set an empty set. */
770 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
775 for (link
= REG_NOTES (insn
);
776 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
777 link
= XEXP (link
, 1))
778 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
780 no_conflict_pairs
[i
].allocno1
781 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
782 no_conflict_pairs
[i
].allocno2
783 = reg_allocno
[REGNO (XEXP (link
, 0))];
788 /* Mark any registers clobbered by INSN as live,
789 so they conflict with the inputs. */
791 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
793 /* Mark any registers dead after INSN as dead now. */
795 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
796 if (REG_NOTE_KIND (link
) == REG_DEAD
)
797 mark_reg_death (XEXP (link
, 0));
799 /* Mark any registers set in INSN as live,
800 and mark them as conflicting with all other live regs.
801 Clobbers are processed again, so they conflict with
802 the registers that are set. */
804 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
807 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
808 if (REG_NOTE_KIND (link
) == REG_INC
)
809 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
812 /* If INSN has multiple outputs, then any reg that dies here
813 and is used inside of an output
814 must conflict with the other outputs.
816 It is unsafe to use !single_set here since it will ignore an
817 unused output. Just because an output is unused does not mean
818 the compiler can assume the side effect will not occur.
819 Consider if REG appears in the address of an output and we
820 reload the output. If we allocate REG to the same hard
821 register as an unused output we could set the hard register
822 before the output reload insn. */
823 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
824 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
825 if (REG_NOTE_KIND (link
) == REG_DEAD
)
827 int used_in_output
= 0;
829 rtx reg
= XEXP (link
, 0);
831 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
833 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
834 if (GET_CODE (set
) == SET
835 && GET_CODE (SET_DEST (set
)) != REG
836 && !rtx_equal_p (reg
, SET_DEST (set
))
837 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
841 mark_reg_conflicts (reg
);
844 /* Mark any registers set in INSN and then never used. */
846 while (n_regs_set
-- > 0)
848 rtx note
= find_regno_note (insn
, REG_UNUSED
,
849 REGNO (regs_set
[n_regs_set
]));
851 mark_reg_death (XEXP (note
, 0));
855 if (insn
== BB_END (b
))
857 insn
= NEXT_INSN (insn
);
862 free (block_start_allocnos
);
865 /* Expand the preference information by looking for cases where one allocno
866 dies in an insn that sets an allocno. If those two allocnos don't conflict,
867 merge any preferences between those allocnos. */
870 expand_preferences (void)
876 /* We only try to handle the most common cases here. Most of the cases
877 where this wins are reg-reg copies. */
879 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
881 && (set
= single_set (insn
)) != 0
882 && GET_CODE (SET_DEST (set
)) == REG
883 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
884 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
885 if (REG_NOTE_KIND (link
) == REG_DEAD
886 && GET_CODE (XEXP (link
, 0)) == REG
887 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
888 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
889 reg_allocno
[REGNO (XEXP (link
, 0))]))
891 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
892 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
894 if (XEXP (link
, 0) == SET_SRC (set
))
896 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_copy_preferences
,
897 allocno
[a2
].hard_reg_copy_preferences
);
898 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_copy_preferences
,
899 allocno
[a1
].hard_reg_copy_preferences
);
902 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_preferences
,
903 allocno
[a2
].hard_reg_preferences
);
904 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_preferences
,
905 allocno
[a1
].hard_reg_preferences
);
906 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_full_preferences
,
907 allocno
[a2
].hard_reg_full_preferences
);
908 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_full_preferences
,
909 allocno
[a1
].hard_reg_full_preferences
);
913 /* Prune the preferences for global registers to exclude registers that cannot
916 Compute `regs_someone_prefers', which is a bitmask of the hard registers
917 that are preferred by conflicting registers of lower priority. If possible,
918 we will avoid using these registers. */
921 prune_preferences (void)
925 int *allocno_to_order
= xmalloc (max_allocno
* sizeof (int));
927 /* Scan least most important to most important.
928 For each allocno, remove from preferences registers that cannot be used,
929 either because of conflicts or register type. Then compute all registers
930 preferred by each lower-priority register that conflicts. */
932 for (i
= max_allocno
- 1; i
>= 0; i
--)
936 num
= allocno_order
[i
];
937 allocno_to_order
[num
] = i
;
938 COPY_HARD_REG_SET (temp
, allocno
[num
].hard_reg_conflicts
);
940 if (allocno
[num
].calls_crossed
== 0)
941 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
943 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
945 IOR_COMPL_HARD_REG_SET
947 reg_class_contents
[(int) reg_preferred_class (allocno
[num
].reg
)]);
949 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, temp
);
950 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, temp
);
951 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_full_preferences
, temp
);
954 for (i
= max_allocno
- 1; i
>= 0; i
--)
956 /* Merge in the preferences of lower-priority registers (they have
957 already been pruned). If we also prefer some of those registers,
958 don't exclude them unless we are of a smaller size (in which case
959 we want to give the lower-priority allocno the first chance for
961 HARD_REG_SET temp
, temp2
;
964 num
= allocno_order
[i
];
966 CLEAR_HARD_REG_SET (temp
);
967 CLEAR_HARD_REG_SET (temp2
);
969 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ num
* allocno_row_words
,
972 if (allocno_to_order
[allocno2
] > i
)
974 if (allocno
[allocno2
].size
<= allocno
[num
].size
)
975 IOR_HARD_REG_SET (temp
,
976 allocno
[allocno2
].hard_reg_full_preferences
);
978 IOR_HARD_REG_SET (temp2
,
979 allocno
[allocno2
].hard_reg_full_preferences
);
983 AND_COMPL_HARD_REG_SET (temp
, allocno
[num
].hard_reg_full_preferences
);
984 IOR_HARD_REG_SET (temp
, temp2
);
985 COPY_HARD_REG_SET (allocno
[num
].regs_someone_prefers
, temp
);
987 free (allocno_to_order
);
990 /* Assign a hard register to allocno NUM; look for one that is the beginning
991 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
992 The registers marked in PREFREGS are tried first.
994 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
995 be used for this allocation.
997 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
998 Otherwise ignore that preferred class and use the alternate class.
1000 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
1001 will have to be saved and restored at calls.
1003 RETRYING is nonzero if this is called from retry_global_alloc.
1005 If we find one, record it in reg_renumber.
1006 If not, do nothing. */
1009 find_reg (int num
, HARD_REG_SET losers
, int alt_regs_p
, int accept_call_clobbered
, int retrying
)
1011 int i
, best_reg
, pass
;
1012 HARD_REG_SET used
, used1
, used2
;
1014 enum reg_class
class = (alt_regs_p
1015 ? reg_alternate_class (allocno
[num
].reg
)
1016 : reg_preferred_class (allocno
[num
].reg
));
1017 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno
[num
].reg
);
1019 if (accept_call_clobbered
)
1020 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
1021 else if (allocno
[num
].calls_crossed
== 0)
1022 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
1024 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
1026 /* Some registers should not be allocated in global-alloc. */
1027 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
1029 IOR_HARD_REG_SET (used1
, losers
);
1031 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
1032 COPY_HARD_REG_SET (used2
, used1
);
1034 IOR_HARD_REG_SET (used1
, allocno
[num
].hard_reg_conflicts
);
1036 #ifdef CANNOT_CHANGE_MODE_CLASS
1037 cannot_change_mode_set_regs (&used1
, mode
, allocno
[num
].reg
);
1040 /* Try each hard reg to see if it fits. Do this in two passes.
1041 In the first pass, skip registers that are preferred by some other pseudo
1042 to give it a better chance of getting one of those registers. Only if
1043 we can't get a register when excluding those do we take one of them.
1044 However, we never allocate a register for the first time in pass 0. */
1046 COPY_HARD_REG_SET (used
, used1
);
1047 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
1048 IOR_HARD_REG_SET (used
, allocno
[num
].regs_someone_prefers
);
1051 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
1052 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
1056 COPY_HARD_REG_SET (used
, used1
);
1057 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1059 #ifdef REG_ALLOC_ORDER
1060 int regno
= reg_alloc_order
[i
];
1064 if (! TEST_HARD_REG_BIT (used
, regno
)
1065 && HARD_REGNO_MODE_OK (regno
, mode
)
1066 && (allocno
[num
].calls_crossed
== 0
1067 || accept_call_clobbered
1068 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
)))
1071 int lim
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1074 && ! TEST_HARD_REG_BIT (used
, j
));
1081 #ifndef REG_ALLOC_ORDER
1082 i
= j
; /* Skip starting points we know will lose */
1088 /* See if there is a preferred register with the same class as the register
1089 we allocated above. Making this restriction prevents register
1090 preferencing from creating worse register allocation.
1092 Remove from the preferred registers and conflicting registers. Note that
1093 additional conflicts may have been added after `prune_preferences' was
1096 First do this for those register with copy preferences, then all
1097 preferred registers. */
1099 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, used
);
1100 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_copy_preferences
,
1101 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
1105 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1106 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_copy_preferences
, i
)
1107 && HARD_REGNO_MODE_OK (i
, mode
)
1108 && (allocno
[num
].calls_crossed
== 0
1109 || accept_call_clobbered
1110 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1111 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1112 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1113 REGNO_REG_CLASS (best_reg
))
1114 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1115 REGNO_REG_CLASS (i
))))
1118 int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1121 && ! TEST_HARD_REG_BIT (used
, j
)
1122 && (REGNO_REG_CLASS (j
)
1123 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1124 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1125 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1126 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1127 REGNO_REG_CLASS (j
))));
1138 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, used
);
1139 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_preferences
,
1140 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1144 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1145 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_preferences
, i
)
1146 && HARD_REGNO_MODE_OK (i
, mode
)
1147 && (allocno
[num
].calls_crossed
== 0
1148 || accept_call_clobbered
1149 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1150 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1151 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1152 REGNO_REG_CLASS (best_reg
))
1153 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1154 REGNO_REG_CLASS (i
))))
1157 int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
1160 && ! TEST_HARD_REG_BIT (used
, j
)
1161 && (REGNO_REG_CLASS (j
)
1162 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1163 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1164 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1165 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1166 REGNO_REG_CLASS (j
))));
1177 /* If we haven't succeeded yet, try with caller-saves.
1178 We need not check to see if the current function has nonlocal
1179 labels because we don't put any pseudos that are live over calls in
1180 registers in that case. */
1182 if (flag_caller_saves
&& best_reg
< 0)
1184 /* Did not find a register. If it would be profitable to
1185 allocate a call-clobbered register and save and restore it
1186 around calls, do that. */
1187 if (! accept_call_clobbered
1188 && allocno
[num
].calls_crossed
!= 0
1189 && CALLER_SAVE_PROFITABLE (allocno
[num
].n_refs
,
1190 allocno
[num
].calls_crossed
))
1192 HARD_REG_SET new_losers
;
1194 CLEAR_HARD_REG_SET (new_losers
);
1196 COPY_HARD_REG_SET (new_losers
, losers
);
1198 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1199 find_reg (num
, new_losers
, alt_regs_p
, 1, retrying
);
1200 if (reg_renumber
[allocno
[num
].reg
] >= 0)
1202 caller_save_needed
= 1;
1208 /* If we haven't succeeded yet,
1209 see if some hard reg that conflicts with us
1210 was utilized poorly by local-alloc.
1211 If so, kick out the regs that were put there by local-alloc
1212 so we can use it instead. */
1213 if (best_reg
< 0 && !retrying
1214 /* Let's not bother with multi-reg allocnos. */
1215 && allocno
[num
].size
== 1)
1217 /* Count from the end, to find the least-used ones first. */
1218 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1220 #ifdef REG_ALLOC_ORDER
1221 int regno
= reg_alloc_order
[i
];
1226 if (local_reg_n_refs
[regno
] != 0
1227 /* Don't use a reg no good for this pseudo. */
1228 && ! TEST_HARD_REG_BIT (used2
, regno
)
1229 && HARD_REGNO_MODE_OK (regno
, mode
)
1230 /* The code below assumes that we need only a single
1231 register, but the check of allocno[num].size above
1232 was not enough. Sometimes we need more than one
1233 register for a single-word value. */
1234 && HARD_REGNO_NREGS (regno
, mode
) == 1
1235 && (allocno
[num
].calls_crossed
== 0
1236 || accept_call_clobbered
1237 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
))
1238 #ifdef CANNOT_CHANGE_MODE_CLASS
1239 && ! invalid_mode_change_p (regno
, REGNO_REG_CLASS (regno
),
1243 && (!allocno
[num
].no_stack_reg
1244 || regno
< FIRST_STACK_REG
|| regno
> LAST_STACK_REG
)
1248 /* We explicitly evaluate the divide results into temporary
1249 variables so as to avoid excess precision problems that occur
1250 on an i386-unknown-sysv4.2 (unixware) host. */
1252 double tmp1
= ((double) local_reg_freq
[regno
]
1253 / local_reg_live_length
[regno
]);
1254 double tmp2
= ((double) allocno
[num
].freq
1255 / allocno
[num
].live_length
);
1259 /* Hard reg REGNO was used less in total by local regs
1260 than it would be used by this one allocno! */
1262 for (k
= 0; k
< max_regno
; k
++)
1263 if (reg_renumber
[k
] >= 0)
1265 int r
= reg_renumber
[k
];
1267 = r
+ HARD_REGNO_NREGS (r
, PSEUDO_REGNO_MODE (k
));
1269 if (regno
>= r
&& regno
< endregno
)
1270 reg_renumber
[k
] = -1;
1280 /* Did we find a register? */
1285 HARD_REG_SET this_reg
;
1287 /* Yes. Record it as the hard register of this pseudo-reg. */
1288 reg_renumber
[allocno
[num
].reg
] = best_reg
;
1289 /* Also of any pseudo-regs that share with it. */
1290 if (reg_may_share
[allocno
[num
].reg
])
1291 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1292 if (reg_allocno
[j
] == num
)
1293 reg_renumber
[j
] = best_reg
;
1295 /* Make a set of the hard regs being allocated. */
1296 CLEAR_HARD_REG_SET (this_reg
);
1297 lim
= best_reg
+ HARD_REGNO_NREGS (best_reg
, mode
);
1298 for (j
= best_reg
; j
< lim
; j
++)
1300 SET_HARD_REG_BIT (this_reg
, j
);
1301 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1302 /* This is no longer a reg used just by local regs. */
1303 local_reg_n_refs
[j
] = 0;
1304 local_reg_freq
[j
] = 0;
1306 /* For each other pseudo-reg conflicting with this one,
1307 mark it as conflicting with the hard regs this one occupies. */
1309 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ lim
* allocno_row_words
, j
,
1311 IOR_HARD_REG_SET (allocno
[j
].hard_reg_conflicts
, this_reg
);
1316 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1317 Perhaps it had previously seemed not worth a hard reg,
1318 or perhaps its old hard reg has been commandeered for reloads.
1319 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1320 they do not appear to be allocated.
1321 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1324 retry_global_alloc (int regno
, HARD_REG_SET forbidden_regs
)
1326 int alloc_no
= reg_allocno
[regno
];
1329 /* If we have more than one register class,
1330 first try allocating in the class that is cheapest
1331 for this pseudo-reg. If that fails, try any reg. */
1332 if (N_REG_CLASSES
> 1)
1333 find_reg (alloc_no
, forbidden_regs
, 0, 0, 1);
1334 if (reg_renumber
[regno
] < 0
1335 && reg_alternate_class (regno
) != NO_REGS
)
1336 find_reg (alloc_no
, forbidden_regs
, 1, 0, 1);
1338 /* If we found a register, modify the RTL for the register to
1339 show the hard register, and mark that register live. */
1340 if (reg_renumber
[regno
] >= 0)
1342 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1343 mark_home_live (regno
);
1348 /* Record a conflict between register REGNO
1349 and everything currently live.
1350 REGNO must not be a pseudo reg that was allocated
1351 by local_alloc; such numbers must be translated through
1352 reg_renumber before calling here. */
1355 record_one_conflict (int regno
)
1359 if (regno
< FIRST_PSEUDO_REGISTER
)
1360 /* When a hard register becomes live,
1361 record conflicts with live pseudo regs. */
1362 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, j
,
1364 SET_HARD_REG_BIT (allocno
[j
].hard_reg_conflicts
, regno
);
1367 /* When a pseudo-register becomes live,
1368 record conflicts first with hard regs,
1369 then with other pseudo regs. */
1371 int ialloc
= reg_allocno
[regno
];
1372 int ialloc_prod
= ialloc
* allocno_row_words
;
1374 IOR_HARD_REG_SET (allocno
[ialloc
].hard_reg_conflicts
, hard_regs_live
);
1375 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1379 for (k
= 0; k
< n_no_conflict_pairs
; k
++)
1380 if (! ((j
== no_conflict_pairs
[k
].allocno1
1381 && ialloc
== no_conflict_pairs
[k
].allocno2
)
1383 (j
== no_conflict_pairs
[k
].allocno2
1384 && ialloc
== no_conflict_pairs
[k
].allocno1
)))
1386 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1391 /* Record all allocnos currently live as conflicting
1392 with all hard regs currently live.
1394 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1395 are currently live. Their bits are also flagged in allocnos_live. */
1398 record_conflicts (int *allocno_vec
, int len
)
1401 IOR_HARD_REG_SET (allocno
[allocno_vec
[len
]].hard_reg_conflicts
,
1405 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1407 mirror_conflicts (void)
1410 int rw
= allocno_row_words
;
1411 int rwb
= rw
* INT_BITS
;
1412 INT_TYPE
*p
= conflicts
;
1413 INT_TYPE
*q0
= conflicts
, *q1
, *q2
;
1414 unsigned INT_TYPE mask
;
1416 for (i
= max_allocno
- 1, mask
= 1; i
>= 0; i
--, mask
<<= 1)
1423 for (j
= allocno_row_words
- 1, q1
= q0
; j
>= 0; j
--, q1
+= rwb
)
1425 unsigned INT_TYPE word
;
1427 for (word
= (unsigned INT_TYPE
) *p
++, q2
= q1
; word
;
1428 word
>>= 1, q2
+= rw
)
1437 /* Handle the case where REG is set by the insn being scanned,
1438 during the forward scan to accumulate conflicts.
1439 Store a 1 in regs_live or allocnos_live for this register, record how many
1440 consecutive hardware registers it actually needs,
1441 and record a conflict with all other registers already live.
1443 Note that even if REG does not remain alive after this insn,
1444 we must mark it here as live, to ensure a conflict between
1445 REG and any other regs set in this insn that really do live.
1446 This is because those other regs could be considered after this.
1448 REG might actually be something other than a register;
1449 if so, we do nothing.
1451 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1452 a REG_INC note was found for it). */
1455 mark_reg_store (rtx reg
, rtx setter
, void *data ATTRIBUTE_UNUSED
)
1459 if (GET_CODE (reg
) == SUBREG
)
1460 reg
= SUBREG_REG (reg
);
1462 if (GET_CODE (reg
) != REG
)
1465 regs_set
[n_regs_set
++] = reg
;
1467 if (setter
&& GET_CODE (setter
) != CLOBBER
)
1468 set_preference (reg
, SET_SRC (setter
));
1470 regno
= REGNO (reg
);
1472 /* Either this is one of the max_allocno pseudo regs not allocated,
1473 or it is or has a hardware reg. First handle the pseudo-regs. */
1474 if (regno
>= FIRST_PSEUDO_REGISTER
)
1476 if (reg_allocno
[regno
] >= 0)
1478 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1479 record_one_conflict (regno
);
1483 if (reg_renumber
[regno
] >= 0)
1484 regno
= reg_renumber
[regno
];
1486 /* Handle hardware regs (and pseudos allocated to hard regs). */
1487 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1489 int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1490 while (regno
< last
)
1492 record_one_conflict (regno
);
1493 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1499 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1502 mark_reg_clobber (rtx reg
, rtx setter
, void *data ATTRIBUTE_UNUSED
)
1504 if (GET_CODE (setter
) == CLOBBER
)
1505 mark_reg_store (reg
, setter
, data
);
1508 /* Record that REG has conflicts with all the regs currently live.
1509 Do not mark REG itself as live. */
1512 mark_reg_conflicts (rtx 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 (rtx reg
)
1553 int regno
= REGNO (reg
);
1555 /* Either this is one of the max_allocno pseudo regs not allocated,
1556 or it is a hardware reg. First handle the pseudo-regs. */
1557 if (regno
>= FIRST_PSEUDO_REGISTER
)
1559 if (reg_allocno
[regno
] >= 0)
1560 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1563 /* For pseudo reg, see if it has been assigned a hardware reg. */
1564 if (reg_renumber
[regno
] >= 0)
1565 regno
= reg_renumber
[regno
];
1567 /* Handle hardware regs (and pseudos allocated to hard regs). */
1568 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1570 /* Pseudo regs already assigned hardware regs are treated
1571 almost the same as explicit hardware regs. */
1572 int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1573 while (regno
< last
)
1575 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1581 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1582 for the value stored in it. MODE determines how many consecutive
1583 registers are actually in use. Do not record conflicts;
1584 it is assumed that the caller will do that. */
1587 mark_reg_live_nc (int regno
, enum machine_mode mode
)
1589 int last
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1590 while (regno
< last
)
1592 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1597 /* Try to set a preference for an allocno to a hard register.
1598 We are passed DEST and SRC which are the operands of a SET. It is known
1599 that SRC is a register. If SRC or the first operand of SRC is a register,
1600 try to set a preference. If one of the two is a hard register and the other
1601 is a pseudo-register, mark the preference.
1603 Note that we are not as aggressive as local-alloc in trying to tie a
1604 pseudo-register to a hard register. */
1607 set_preference (rtx dest
, rtx src
)
1609 unsigned int src_regno
, dest_regno
;
1610 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1611 to compensate for subregs in SRC or DEST. */
1616 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1617 src
= XEXP (src
, 0), copy
= 0;
1619 /* Get the reg number for both SRC and DEST.
1620 If neither is a reg, give up. */
1622 if (GET_CODE (src
) == REG
)
1623 src_regno
= REGNO (src
);
1624 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1626 src_regno
= REGNO (SUBREG_REG (src
));
1628 if (REGNO (SUBREG_REG (src
)) < FIRST_PSEUDO_REGISTER
)
1629 offset
+= subreg_regno_offset (REGNO (SUBREG_REG (src
)),
1630 GET_MODE (SUBREG_REG (src
)),
1634 offset
+= (SUBREG_BYTE (src
)
1635 / REGMODE_NATURAL_SIZE (GET_MODE (src
)));
1640 if (GET_CODE (dest
) == REG
)
1641 dest_regno
= REGNO (dest
);
1642 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1644 dest_regno
= REGNO (SUBREG_REG (dest
));
1646 if (REGNO (SUBREG_REG (dest
)) < FIRST_PSEUDO_REGISTER
)
1647 offset
-= subreg_regno_offset (REGNO (SUBREG_REG (dest
)),
1648 GET_MODE (SUBREG_REG (dest
)),
1652 offset
-= (SUBREG_BYTE (dest
)
1653 / REGMODE_NATURAL_SIZE (GET_MODE (dest
)));
1658 /* Convert either or both to hard reg numbers. */
1660 if (reg_renumber
[src_regno
] >= 0)
1661 src_regno
= reg_renumber
[src_regno
];
1663 if (reg_renumber
[dest_regno
] >= 0)
1664 dest_regno
= reg_renumber
[dest_regno
];
1666 /* Now if one is a hard reg and the other is a global pseudo
1667 then give the other a preference. */
1669 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1670 && reg_allocno
[src_regno
] >= 0)
1672 dest_regno
-= offset
;
1673 if (dest_regno
< FIRST_PSEUDO_REGISTER
)
1676 SET_REGBIT (hard_reg_copy_preferences
,
1677 reg_allocno
[src_regno
], dest_regno
);
1679 SET_REGBIT (hard_reg_preferences
,
1680 reg_allocno
[src_regno
], dest_regno
);
1681 for (i
= dest_regno
;
1682 i
< dest_regno
+ HARD_REGNO_NREGS (dest_regno
, GET_MODE (dest
));
1684 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1688 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1689 && reg_allocno
[dest_regno
] >= 0)
1691 src_regno
+= offset
;
1692 if (src_regno
< FIRST_PSEUDO_REGISTER
)
1695 SET_REGBIT (hard_reg_copy_preferences
,
1696 reg_allocno
[dest_regno
], src_regno
);
1698 SET_REGBIT (hard_reg_preferences
,
1699 reg_allocno
[dest_regno
], src_regno
);
1701 i
< src_regno
+ HARD_REGNO_NREGS (src_regno
, GET_MODE (src
));
1703 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1708 /* Indicate that hard register number FROM was eliminated and replaced with
1709 an offset from hard register number TO. The status of hard registers live
1710 at the start of a basic block is updated by replacing a use of FROM with
1714 mark_elimination (int from
, int to
)
1720 regset r
= bb
->global_live_at_start
;
1721 if (REGNO_REG_SET_P (r
, from
))
1723 CLEAR_REGNO_REG_SET (r
, from
);
1724 SET_REGNO_REG_SET (r
, to
);
1729 /* Used for communication between the following functions. Holds the
1730 current life information. */
1731 static regset live_relevant_regs
;
1733 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1734 This is called via note_stores. */
1736 reg_becomes_live (rtx reg
, rtx setter ATTRIBUTE_UNUSED
, void *regs_set
)
1740 if (GET_CODE (reg
) == SUBREG
)
1741 reg
= SUBREG_REG (reg
);
1743 if (GET_CODE (reg
) != REG
)
1746 regno
= REGNO (reg
);
1747 if (regno
< FIRST_PSEUDO_REGISTER
)
1749 int nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1752 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1753 if (! fixed_regs
[regno
])
1754 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1758 else if (reg_renumber
[regno
] >= 0)
1760 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1761 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1765 /* Record in live_relevant_regs that register REGNO died. */
1767 reg_dies (int regno
, enum machine_mode mode
, struct insn_chain
*chain
)
1769 if (regno
< FIRST_PSEUDO_REGISTER
)
1771 int nregs
= HARD_REGNO_NREGS (regno
, mode
);
1774 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1775 if (! fixed_regs
[regno
])
1776 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1782 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1783 if (reg_renumber
[regno
] >= 0)
1784 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1788 /* Walk the insns of the current function and build reload_insn_chain,
1789 and record register life information. */
1791 build_insn_chain (rtx first
)
1793 struct insn_chain
**p
= &reload_insn_chain
;
1794 struct insn_chain
*prev
= 0;
1795 basic_block b
= ENTRY_BLOCK_PTR
->next_bb
;
1796 regset_head live_relevant_regs_head
;
1798 live_relevant_regs
= INITIALIZE_REG_SET (live_relevant_regs_head
);
1800 for (; first
; first
= NEXT_INSN (first
))
1802 struct insn_chain
*c
;
1804 if (first
== BB_HEAD (b
))
1808 CLEAR_REG_SET (live_relevant_regs
);
1810 EXECUTE_IF_SET_IN_BITMAP
1811 (b
->global_live_at_start
, 0, i
,
1813 if (i
< FIRST_PSEUDO_REGISTER
1814 ? ! TEST_HARD_REG_BIT (eliminable_regset
, i
)
1815 : reg_renumber
[i
] >= 0)
1816 SET_REGNO_REG_SET (live_relevant_regs
, i
);
1820 if (GET_CODE (first
) != NOTE
&& GET_CODE (first
) != BARRIER
)
1822 c
= new_insn_chain ();
1828 c
->block
= b
->index
;
1834 /* Mark the death of everything that dies in this instruction. */
1836 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1837 if (REG_NOTE_KIND (link
) == REG_DEAD
1838 && GET_CODE (XEXP (link
, 0)) == REG
)
1839 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1842 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1844 /* Mark everything born in this instruction as live. */
1846 note_stores (PATTERN (first
), reg_becomes_live
,
1850 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1856 /* Mark anything that is set in this insn and then unused as dying. */
1858 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1859 if (REG_NOTE_KIND (link
) == REG_UNUSED
1860 && GET_CODE (XEXP (link
, 0)) == REG
)
1861 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1866 if (first
== BB_END (b
))
1869 /* Stop after we pass the end of the last basic block. Verify that
1870 no real insns are after the end of the last basic block.
1872 We may want to reorganize the loop somewhat since this test should
1873 always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if
1874 the previous real insn is a JUMP_INSN. */
1875 if (b
== EXIT_BLOCK_PTR
)
1877 for (first
= NEXT_INSN (first
) ; first
; first
= NEXT_INSN (first
))
1879 && GET_CODE (PATTERN (first
)) != USE
1880 && ! ((GET_CODE (PATTERN (first
)) == ADDR_VEC
1881 || GET_CODE (PATTERN (first
)) == ADDR_DIFF_VEC
)
1882 && prev_real_insn (first
) != 0
1883 && GET_CODE (prev_real_insn (first
)) == JUMP_INSN
))
1888 FREE_REG_SET (live_relevant_regs
);
1892 /* Print debugging trace information if -dg switch is given,
1893 showing the information on which the allocation decisions are based. */
1896 dump_conflicts (FILE *file
)
1899 int has_preferences
;
1902 for (i
= 0; i
< max_allocno
; i
++)
1904 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1908 fprintf (file
, ";; %d regs to allocate:", nregs
);
1909 for (i
= 0; i
< max_allocno
; i
++)
1912 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1914 fprintf (file
, " %d", allocno
[allocno_order
[i
]].reg
);
1915 for (j
= 0; j
< max_regno
; j
++)
1916 if (reg_allocno
[j
] == allocno_order
[i
]
1917 && j
!= allocno
[allocno_order
[i
]].reg
)
1918 fprintf (file
, "+%d", j
);
1919 if (allocno
[allocno_order
[i
]].size
!= 1)
1920 fprintf (file
, " (%d)", allocno
[allocno_order
[i
]].size
);
1922 fprintf (file
, "\n");
1924 for (i
= 0; i
< max_allocno
; i
++)
1927 fprintf (file
, ";; %d conflicts:", allocno
[i
].reg
);
1928 for (j
= 0; j
< max_allocno
; j
++)
1929 if (CONFLICTP (j
, i
))
1930 fprintf (file
, " %d", allocno
[j
].reg
);
1931 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1932 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_conflicts
, j
))
1933 fprintf (file
, " %d", j
);
1934 fprintf (file
, "\n");
1936 has_preferences
= 0;
1937 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1938 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1939 has_preferences
= 1;
1941 if (! has_preferences
)
1943 fprintf (file
, ";; %d preferences:", allocno
[i
].reg
);
1944 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1945 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1946 fprintf (file
, " %d", j
);
1947 fprintf (file
, "\n");
1949 fprintf (file
, "\n");
1953 dump_global_regs (FILE *file
)
1957 fprintf (file
, ";; Register dispositions:\n");
1958 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1959 if (reg_renumber
[i
] >= 0)
1961 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1963 fprintf (file
, "\n");
1966 fprintf (file
, "\n\n;; Hard regs used: ");
1967 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1968 if (regs_ever_live
[i
])
1969 fprintf (file
, " %d", i
);
1970 fprintf (file
, "\n\n");