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, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA
25 #include "coretypes.h"
28 #include "hard-reg-set.h"
34 #include "insn-config.h"
39 #include "tree-pass.h"
43 /* This pass of the compiler performs global register allocation.
44 It assigns hard register numbers to all the pseudo registers
45 that were not handled in local_alloc. Assignments are recorded
46 in the vector reg_renumber, not by changing the rtl code.
47 (Such changes are made by final). The entry point is
48 the function global_alloc.
50 After allocation is complete, the reload pass is run as a subroutine
51 of this pass, so that when a pseudo reg loses its hard reg due to
52 spilling it is possible to make a second attempt to find a hard
53 reg for it. The reload pass is independent in other respects
54 and it is run even when stupid register allocation is in use.
56 1. Assign allocation-numbers (allocnos) to the pseudo-registers
57 still needing allocations and to the pseudo-registers currently
58 allocated by local-alloc which may be spilled by reload.
59 Set up tables reg_allocno and allocno_reg to map
60 reg numbers to allocnos and vice versa.
61 max_allocno gets the number of allocnos in use.
63 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
64 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
65 for conflicts between allocnos and explicit hard register use
66 (which includes use of pseudo-registers allocated by local_alloc).
68 3. For each basic block
69 walk forward through the block, recording which
70 pseudo-registers and which hardware registers are live.
71 Build the conflict matrix between the pseudo-registers
72 and another of pseudo-registers versus hardware registers.
73 Also record the preferred hardware registers
74 for each pseudo-register.
76 4. Sort a table of the allocnos into order of
77 desirability of the variables.
79 5. Allocate the variables in that order; each if possible into
80 a preferred register, else into another register. */
82 /* Number of pseudo-registers which are candidates for allocation. */
84 static int max_allocno
;
86 /* Indexed by (pseudo) reg number, gives the allocno, or -1
87 for pseudo registers which are not to be allocated. */
89 static int *reg_allocno
;
94 /* Gives the number of consecutive hard registers needed by that
98 /* Number of calls crossed by each allocno. */
101 /* Number of calls that might throw crossed by each allocno. */
102 int throwing_calls_crossed
;
104 /* Number of refs to each allocno. */
107 /* Frequency of uses of each allocno. */
110 /* Guess at live length of each allocno.
111 This is actually the max of the live lengths of the regs. */
114 /* Set of hard regs conflicting with allocno N. */
116 HARD_REG_SET hard_reg_conflicts
;
118 /* Set of hard regs preferred by allocno N.
119 This is used to make allocnos go into regs that are copied to or from them,
120 when possible, to reduce register shuffling. */
122 HARD_REG_SET hard_reg_preferences
;
124 /* Similar, but just counts register preferences made in simple copy
125 operations, rather than arithmetic. These are given priority because
126 we can always eliminate an insn by using these, but using a register
127 in the above list won't always eliminate an insn. */
129 HARD_REG_SET hard_reg_copy_preferences
;
131 /* Similar to hard_reg_preferences, but includes bits for subsequent
132 registers when an allocno is multi-word. The above variable is used for
133 allocation while this is used to build reg_someone_prefers, below. */
135 HARD_REG_SET hard_reg_full_preferences
;
137 /* Set of hard registers that some later allocno has a preference for. */
139 HARD_REG_SET regs_someone_prefers
;
142 /* Set to true if allocno can't be allocated in the stack register. */
147 static struct allocno
*allocno
;
149 /* A vector of the integers from 0 to max_allocno-1,
150 sorted in the order of first-to-be-allocated first. */
152 static int *allocno_order
;
154 /* Indexed by (pseudo) reg number, gives the number of another
155 lower-numbered pseudo reg which can share a hard reg with this pseudo
156 *even if the two pseudos would otherwise appear to conflict*. */
158 static int *reg_may_share
;
160 /* Define the number of bits in each element of `conflicts' and what
161 type that element has. We use the largest integer format on the
164 #define INT_BITS HOST_BITS_PER_WIDE_INT
165 #define INT_TYPE HOST_WIDE_INT
167 /* max_allocno by max_allocno array of bits,
168 recording whether two allocno's conflict (can't go in the same
171 `conflicts' is symmetric after the call to mirror_conflicts. */
173 static INT_TYPE
*conflicts
;
175 /* Number of ints required to hold max_allocno bits.
176 This is the length of a row in `conflicts'. */
178 static int allocno_row_words
;
180 /* Two macros to test or store 1 in an element of `conflicts'. */
182 #define CONFLICTP(I, J) \
183 (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS] \
184 & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS)))
186 /* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
188 #define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
192 INT_TYPE *p_ = (ALLOCNO_SET); \
194 for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
195 i_--, allocno_ += INT_BITS) \
197 unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
199 for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
207 /* Set of hard regs currently live (during scan of all insns). */
209 static HARD_REG_SET hard_regs_live
;
211 /* Set of registers that global-alloc isn't supposed to use. */
213 static HARD_REG_SET no_global_alloc_regs
;
215 /* Set of registers used so far. */
217 static HARD_REG_SET regs_used_so_far
;
219 /* Number of refs to each hard reg, as used by local alloc.
220 It is zero for a reg that contains global pseudos or is explicitly used. */
222 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
224 /* Frequency of uses of given hard reg. */
225 static int local_reg_freq
[FIRST_PSEUDO_REGISTER
];
227 /* Guess at live length of each hard reg, as used by local alloc.
228 This is actually the sum of the live lengths of the specific regs. */
230 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
232 /* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
233 element I, and hard register number J. */
235 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
237 /* Bit mask for allocnos live at current point in the scan. */
239 static INT_TYPE
*allocnos_live
;
241 /* Test, set or clear bit number I in allocnos_live,
242 a bit vector indexed by allocno. */
244 #define SET_ALLOCNO_LIVE(I) \
245 (allocnos_live[(unsigned) (I) / INT_BITS] \
246 |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
248 #define CLEAR_ALLOCNO_LIVE(I) \
249 (allocnos_live[(unsigned) (I) / INT_BITS] \
250 &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
252 /* This is turned off because it doesn't work right for DImode.
253 (And it is only used for DImode, so the other cases are worthless.)
254 The problem is that it isn't true that there is NO possibility of conflict;
255 only that there is no conflict if the two pseudos get the exact same regs.
256 If they were allocated with a partial overlap, there would be a conflict.
257 We can't safely turn off the conflict unless we have another way to
258 prevent the partial overlap.
260 Idea: change hard_reg_conflicts so that instead of recording which
261 hard regs the allocno may not overlap, it records where the allocno
262 may not start. Change both where it is used and where it is updated.
263 Then there is a way to record that (reg:DI 108) may start at 10
264 but not at 9 or 11. There is still the question of how to record
265 this semi-conflict between two pseudos. */
267 /* Reg pairs for which conflict after the current insn
268 is inhibited by a REG_NO_CONFLICT note.
269 If the table gets full, we ignore any other notes--that is conservative. */
270 #define NUM_NO_CONFLICT_PAIRS 4
271 /* Number of pairs in use in this insn. */
272 int n_no_conflict_pairs
;
273 static struct { int allocno1
, allocno2
;}
274 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
277 /* Record all regs that are set in any one insn.
278 Communication from mark_reg_{store,clobber} and global_conflicts. */
280 static rtx
*regs_set
;
281 static int n_regs_set
;
283 /* All registers that can be eliminated. */
285 static HARD_REG_SET eliminable_regset
;
287 static int allocno_compare (const void *, const void *);
288 static void global_conflicts (void);
289 static void mirror_conflicts (void);
290 static void expand_preferences (void);
291 static void prune_preferences (void);
292 static void find_reg (int, HARD_REG_SET
, int, int, int);
293 static void record_one_conflict (int);
294 static void record_conflicts (int *, int);
295 static void mark_reg_store (rtx
, rtx
, void *);
296 static void mark_reg_clobber (rtx
, rtx
, void *);
297 static void mark_reg_conflicts (rtx
);
298 static void mark_reg_death (rtx
);
299 static void set_preference (rtx
, rtx
);
300 static void dump_conflicts (FILE *);
301 static void reg_becomes_live (rtx
, rtx
, void *);
302 static void reg_dies (int, enum machine_mode
, struct insn_chain
*);
304 static void allocate_bb_info (void);
305 static void free_bb_info (void);
306 static bool check_earlyclobber (rtx
);
307 static void mark_reg_use_for_earlyclobber_1 (rtx
*, void *);
308 static int mark_reg_use_for_earlyclobber (rtx
*, void *);
309 static void calculate_local_reg_bb_info (void);
310 static void set_up_bb_rts_numbers (void);
311 static int rpost_cmp (const void *, const void *);
312 static void calculate_reg_pav (void);
313 static void modify_reg_pav (void);
314 static void make_accurate_live_analysis (void);
318 /* Look through the list of eliminable registers. Add registers
319 clobbered by asm statements to LIVE_REGS. Set ELIM_SET to the set of
320 registers which may be eliminated. Set NO_GLOBAL_SET to the set of
321 registers which may not be used across blocks.
323 ASM_CLOBBERED is the set of registers clobbered by some asm statement.
325 This will normally be called with LIVE_REGS as the global variable
326 regs_ever_live, ELIM_SET as the file static variable
327 eliminable_regset, and NO_GLOBAL_SET as the file static variable
328 NO_GLOBAL_ALLOC_REGS. */
331 compute_regsets (char asm_clobbered
[FIRST_PSEUDO_REGISTER
],
332 char live_regs
[FIRST_PSEUDO_REGISTER
],
333 HARD_REG_SET
*elim_set
,
334 HARD_REG_SET
*no_global_set
)
336 #ifdef ELIMINABLE_REGS
337 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
341 = (! flag_omit_frame_pointer
342 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
343 || FRAME_POINTER_REQUIRED
);
345 /* A machine may have certain hard registers that
346 are safe to use only within a basic block. */
348 CLEAR_HARD_REG_SET (*no_global_set
);
349 CLEAR_HARD_REG_SET (*elim_set
);
351 /* Build the regset of all eliminable registers and show we can't use those
352 that we already know won't be eliminated. */
353 #ifdef ELIMINABLE_REGS
354 for (i
= 0; i
< ARRAY_SIZE (eliminables
); i
++)
357 = (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
358 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
));
360 if (!asm_clobbered
[eliminables
[i
].from
])
362 SET_HARD_REG_BIT (*elim_set
, eliminables
[i
].from
);
365 SET_HARD_REG_BIT (*no_global_set
, eliminables
[i
].from
);
367 else if (cannot_elim
)
368 error ("%s cannot be used in asm here",
369 reg_names
[eliminables
[i
].from
]);
371 live_regs
[eliminables
[i
].from
] = 1;
373 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
374 if (!asm_clobbered
[HARD_FRAME_POINTER_REGNUM
])
376 SET_HARD_REG_BIT (*elim_set
, HARD_FRAME_POINTER_REGNUM
);
378 SET_HARD_REG_BIT (*no_global_set
, HARD_FRAME_POINTER_REGNUM
);
381 error ("%s cannot be used in asm here",
382 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
384 live_regs
[HARD_FRAME_POINTER_REGNUM
] = 1;
388 if (!asm_clobbered
[FRAME_POINTER_REGNUM
])
390 SET_HARD_REG_BIT (*elim_set
, FRAME_POINTER_REGNUM
);
392 SET_HARD_REG_BIT (*no_global_set
, FRAME_POINTER_REGNUM
);
395 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
397 live_regs
[FRAME_POINTER_REGNUM
] = 1;
401 /* Perform allocation of pseudo-registers not allocated by local_alloc.
403 Return value is nonzero if reload failed
404 and we must not do any more for this function. */
413 make_accurate_live_analysis ();
415 compute_regsets (regs_asm_clobbered
, regs_ever_live
,
416 &eliminable_regset
, &no_global_alloc_regs
);
418 /* Track which registers have already been used. Start with registers
419 explicitly in the rtl, then registers allocated by local register
422 CLEAR_HARD_REG_SET (regs_used_so_far
);
423 #ifdef LEAF_REGISTERS
424 /* If we are doing the leaf function optimization, and this is a leaf
425 function, it means that the registers that take work to save are those
426 that need a register window. So prefer the ones that can be used in
429 const char *cheap_regs
;
430 const char *const leaf_regs
= LEAF_REGISTERS
;
432 if (only_leaf_regs_used () && leaf_function_p ())
433 cheap_regs
= leaf_regs
;
435 cheap_regs
= call_used_regs
;
436 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
437 if (regs_ever_live
[i
] || cheap_regs
[i
])
438 SET_HARD_REG_BIT (regs_used_so_far
, i
);
441 /* We consider registers that do not have to be saved over calls as if
442 they were already used since there is no cost in using them. */
443 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
444 if (regs_ever_live
[i
] || call_used_regs
[i
])
445 SET_HARD_REG_BIT (regs_used_so_far
, i
);
448 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
449 if (reg_renumber
[i
] >= 0)
450 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
452 /* Establish mappings from register number to allocation number
453 and vice versa. In the process, count the allocnos. */
455 reg_allocno
= XNEWVEC (int, max_regno
);
457 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
460 /* Initialize the shared-hard-reg mapping
461 from the list of pairs that may share. */
462 reg_may_share
= XCNEWVEC (int, max_regno
);
463 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
465 int r1
= REGNO (XEXP (x
, 0));
466 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
468 reg_may_share
[r1
] = r2
;
470 reg_may_share
[r2
] = r1
;
474 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
475 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
476 that we are supposed to refrain from putting in a hard reg.
477 -2 means do make an allocno but don't allocate it. */
478 if (REG_N_REFS (i
) != 0 && REG_LIVE_LENGTH (i
) != -1
479 /* Don't allocate pseudos that cross calls,
480 if this function receives a nonlocal goto. */
481 && (! current_function_has_nonlocal_label
482 || REG_N_CALLS_CROSSED (i
) == 0))
484 if (reg_renumber
[i
] < 0
485 && reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
486 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
488 reg_allocno
[i
] = max_allocno
++;
489 gcc_assert (REG_LIVE_LENGTH (i
));
494 allocno
= XCNEWVEC (struct allocno
, max_allocno
);
496 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
497 if (reg_allocno
[i
] >= 0)
499 int num
= reg_allocno
[i
];
500 allocno
[num
].reg
= i
;
501 allocno
[num
].size
= PSEUDO_REGNO_SIZE (i
);
502 allocno
[num
].calls_crossed
+= REG_N_CALLS_CROSSED (i
);
503 allocno
[num
].throwing_calls_crossed
504 += REG_N_THROWING_CALLS_CROSSED (i
);
505 allocno
[num
].n_refs
+= REG_N_REFS (i
);
506 allocno
[num
].freq
+= REG_FREQ (i
);
507 if (allocno
[num
].live_length
< REG_LIVE_LENGTH (i
))
508 allocno
[num
].live_length
= REG_LIVE_LENGTH (i
);
511 /* Calculate amount of usage of each hard reg by pseudos
512 allocated by local-alloc. This is to see if we want to
514 memset (local_reg_live_length
, 0, sizeof local_reg_live_length
);
515 memset (local_reg_n_refs
, 0, sizeof local_reg_n_refs
);
516 memset (local_reg_freq
, 0, sizeof local_reg_freq
);
517 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
518 if (reg_renumber
[i
] >= 0)
520 int regno
= reg_renumber
[i
];
521 int endregno
= end_hard_regno (PSEUDO_REGNO_MODE (i
), regno
);
524 for (j
= regno
; j
< endregno
; j
++)
526 local_reg_n_refs
[j
] += REG_N_REFS (i
);
527 local_reg_freq
[j
] += REG_FREQ (i
);
528 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
532 /* We can't override local-alloc for a reg used not just by local-alloc. */
533 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
534 if (regs_ever_live
[i
])
535 local_reg_n_refs
[i
] = 0, local_reg_freq
[i
] = 0;
537 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
539 /* We used to use alloca here, but the size of what it would try to
540 allocate would occasionally cause it to exceed the stack limit and
541 cause unpredictable core dumps. Some examples were > 2Mb in size. */
542 conflicts
= XCNEWVEC (INT_TYPE
, max_allocno
* allocno_row_words
);
544 allocnos_live
= XNEWVEC (INT_TYPE
, allocno_row_words
);
546 /* If there is work to be done (at least one reg to allocate),
547 perform global conflict analysis and allocate the regs. */
551 /* Scan all the insns and compute the conflicts among allocnos
552 and between allocnos and hard regs. */
558 /* Eliminate conflicts between pseudos and eliminable registers. If
559 the register is not eliminated, the pseudo won't really be able to
560 live in the eliminable register, so the conflict doesn't matter.
561 If we do eliminate the register, the conflict will no longer exist.
562 So in either case, we can ignore the conflict. Likewise for
565 for (i
= 0; i
< (size_t) max_allocno
; i
++)
567 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_conflicts
,
569 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_copy_preferences
,
571 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_preferences
,
575 /* Try to expand the preferences by merging them between allocnos. */
577 expand_preferences ();
579 /* Determine the order to allocate the remaining pseudo registers. */
581 allocno_order
= XNEWVEC (int, max_allocno
);
582 for (i
= 0; i
< (size_t) max_allocno
; i
++)
583 allocno_order
[i
] = i
;
585 /* Default the size to 1, since allocno_compare uses it to divide by.
586 Also convert allocno_live_length of zero to -1. A length of zero
587 can occur when all the registers for that allocno have reg_live_length
588 equal to -2. In this case, we want to make an allocno, but not
589 allocate it. So avoid the divide-by-zero and set it to a low
592 for (i
= 0; i
< (size_t) max_allocno
; i
++)
594 if (allocno
[i
].size
== 0)
596 if (allocno
[i
].live_length
== 0)
597 allocno
[i
].live_length
= -1;
600 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
602 prune_preferences ();
605 dump_conflicts (dump_file
);
607 /* Try allocating them, one by one, in that order,
608 except for parameters marked with reg_live_length[regno] == -2. */
610 for (i
= 0; i
< (size_t) max_allocno
; i
++)
611 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] < 0
612 && REG_LIVE_LENGTH (allocno
[allocno_order
[i
]].reg
) >= 0)
614 /* If we have more than one register class,
615 first try allocating in the class that is cheapest
616 for this pseudo-reg. If that fails, try any reg. */
617 if (N_REG_CLASSES
> 1)
619 find_reg (allocno_order
[i
], 0, 0, 0, 0);
620 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
623 if (reg_alternate_class (allocno
[allocno_order
[i
]].reg
) != NO_REGS
)
624 find_reg (allocno_order
[i
], 0, 1, 0, 0);
627 free (allocno_order
);
630 /* Do the reloads now while the allocno data still exists, so that we can
631 try to assign new hard regs to any pseudo regs that are spilled. */
633 #if 0 /* We need to eliminate regs even if there is no rtl code,
634 for the sake of debugging information. */
635 if (n_basic_blocks
> NUM_FIXED_BLOCKS
)
638 build_insn_chain (get_insns ());
639 retval
= reload (get_insns (), 1);
644 free (reg_may_share
);
647 free (allocnos_live
);
652 /* Sort predicate for ordering the allocnos.
653 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
656 allocno_compare (const void *v1p
, const void *v2p
)
658 int v1
= *(const int *)v1p
, v2
= *(const int *)v2p
;
659 /* Note that the quotient will never be bigger than
660 the value of floor_log2 times the maximum number of
661 times a register can occur in one insn (surely less than 100)
662 weighted by the frequency (maximally REG_FREQ_MAX).
663 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
665 = (((double) (floor_log2 (allocno
[v1
].n_refs
) * allocno
[v1
].freq
)
666 / allocno
[v1
].live_length
)
667 * (10000 / REG_FREQ_MAX
) * allocno
[v1
].size
);
669 = (((double) (floor_log2 (allocno
[v2
].n_refs
) * allocno
[v2
].freq
)
670 / allocno
[v2
].live_length
)
671 * (10000 / REG_FREQ_MAX
) * allocno
[v2
].size
);
675 /* If regs are equally good, sort by allocno,
676 so that the results of qsort leave nothing to chance. */
680 /* Scan the rtl code and record all conflicts and register preferences in the
681 conflict matrices and preference tables. */
684 global_conflicts (void)
689 int *block_start_allocnos
;
691 /* Make a vector that mark_reg_{store,clobber} will store in. */
692 regs_set
= XNEWVEC (rtx
, max_parallel
* 2);
694 block_start_allocnos
= XNEWVEC (int, max_allocno
);
698 memset (allocnos_live
, 0, allocno_row_words
* sizeof (INT_TYPE
));
700 /* Initialize table of registers currently live
701 to the state at the beginning of this basic block.
702 This also marks the conflicts among hard registers
703 and any allocnos that are live.
705 For pseudo-regs, there is only one bit for each one
706 no matter how many hard regs it occupies.
707 This is ok; we know the size from PSEUDO_REGNO_SIZE.
708 For explicit hard regs, we cannot know the size that way
709 since one hard reg can be used with various sizes.
710 Therefore, we must require that all the hard regs
711 implicitly live as part of a multi-word hard reg
712 be explicitly marked in basic_block_live_at_start. */
715 regset old
= b
->il
.rtl
->global_live_at_start
;
717 reg_set_iterator rsi
;
719 REG_SET_TO_HARD_REG_SET (hard_regs_live
, old
);
720 EXECUTE_IF_SET_IN_REG_SET (old
, FIRST_PSEUDO_REGISTER
, i
, rsi
)
722 int a
= reg_allocno
[i
];
725 SET_ALLOCNO_LIVE (a
);
726 block_start_allocnos
[ax
++] = a
;
728 else if ((a
= reg_renumber
[i
]) >= 0)
729 add_to_hard_reg_set (&hard_regs_live
, PSEUDO_REGNO_MODE (i
), a
);
732 /* Record that each allocno now live conflicts with each hard reg
735 It is not necessary to mark any conflicts between pseudos at
736 this point, even for pseudos which are live at the start of
739 Given two pseudos X and Y and any point in the CFG P.
741 On any path to point P where X and Y are live one of the
742 following conditions must be true:
744 1. X is live at some instruction on the path that
747 2. Y is live at some instruction on the path that
750 3. Either X or Y is not evaluated on the path to P
751 (i.e. it is used uninitialized) and thus the
752 conflict can be ignored.
754 In cases #1 and #2 the conflict will be recorded when we
755 scan the instruction that makes either X or Y become live. */
756 record_conflicts (block_start_allocnos
, ax
);
758 #ifdef EH_RETURN_DATA_REGNO
759 if (bb_has_eh_pred (b
))
765 unsigned int regno
= EH_RETURN_DATA_REGNO (i
);
766 if (regno
== INVALID_REGNUM
)
768 record_one_conflict (regno
);
773 /* Pseudos can't go in stack regs at the start of a basic block that
774 is reached by an abnormal edge. Likewise for call clobbered regs,
775 because caller-save, fixup_abnormal_edges and possibly the table
776 driven EH machinery are not quite ready to handle such regs live
777 across such edges. */
782 FOR_EACH_EDGE (e
, ei
, b
->preds
)
783 if (e
->flags
& EDGE_ABNORMAL
)
789 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, ax
,
791 allocno
[ax
].no_stack_reg
= 1;
793 for (ax
= FIRST_STACK_REG
; ax
<= LAST_STACK_REG
; ax
++)
794 record_one_conflict (ax
);
797 /* No need to record conflicts for call clobbered regs if we have
798 nonlocal labels around, as we don't ever try to allocate such
799 regs in this case. */
800 if (! current_function_has_nonlocal_label
)
801 for (ax
= 0; ax
< FIRST_PSEUDO_REGISTER
; ax
++)
802 if (call_used_regs
[ax
])
803 record_one_conflict (ax
);
810 /* Scan the code of this basic block, noting which allocnos
811 and hard regs are born or die. When one is born,
812 record a conflict with all others currently live. */
816 RTX_CODE code
= GET_CODE (insn
);
819 /* Make regs_set an empty set. */
823 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
828 for (link
= REG_NOTES (insn
);
829 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
830 link
= XEXP (link
, 1))
831 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
833 no_conflict_pairs
[i
].allocno1
834 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
835 no_conflict_pairs
[i
].allocno2
836 = reg_allocno
[REGNO (XEXP (link
, 0))];
841 /* Mark any registers clobbered by INSN as live,
842 so they conflict with the inputs. */
844 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
846 /* Mark any registers dead after INSN as dead now. */
848 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
849 if (REG_NOTE_KIND (link
) == REG_DEAD
)
850 mark_reg_death (XEXP (link
, 0));
852 /* Mark any registers set in INSN as live,
853 and mark them as conflicting with all other live regs.
854 Clobbers are processed again, so they conflict with
855 the registers that are set. */
857 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
860 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
861 if (REG_NOTE_KIND (link
) == REG_INC
)
862 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
865 /* If INSN has multiple outputs, then any reg that dies here
866 and is used inside of an output
867 must conflict with the other outputs.
869 It is unsafe to use !single_set here since it will ignore an
870 unused output. Just because an output is unused does not mean
871 the compiler can assume the side effect will not occur.
872 Consider if REG appears in the address of an output and we
873 reload the output. If we allocate REG to the same hard
874 register as an unused output we could set the hard register
875 before the output reload insn. */
876 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
877 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
878 if (REG_NOTE_KIND (link
) == REG_DEAD
)
880 int used_in_output
= 0;
882 rtx reg
= XEXP (link
, 0);
884 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
886 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
887 if (GET_CODE (set
) == SET
888 && !REG_P (SET_DEST (set
))
889 && !rtx_equal_p (reg
, SET_DEST (set
))
890 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
894 mark_reg_conflicts (reg
);
897 /* Mark any registers set in INSN and then never used. */
899 while (n_regs_set
-- > 0)
901 rtx note
= find_regno_note (insn
, REG_UNUSED
,
902 REGNO (regs_set
[n_regs_set
]));
904 mark_reg_death (XEXP (note
, 0));
908 if (insn
== BB_END (b
))
910 insn
= NEXT_INSN (insn
);
915 free (block_start_allocnos
);
918 /* Expand the preference information by looking for cases where one allocno
919 dies in an insn that sets an allocno. If those two allocnos don't conflict,
920 merge any preferences between those allocnos. */
923 expand_preferences (void)
929 /* We only try to handle the most common cases here. Most of the cases
930 where this wins are reg-reg copies. */
932 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
934 && (set
= single_set (insn
)) != 0
935 && REG_P (SET_DEST (set
))
936 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
937 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
938 if (REG_NOTE_KIND (link
) == REG_DEAD
939 && REG_P (XEXP (link
, 0))
940 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
941 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
942 reg_allocno
[REGNO (XEXP (link
, 0))]))
944 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
945 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
947 if (XEXP (link
, 0) == SET_SRC (set
))
949 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_copy_preferences
,
950 allocno
[a2
].hard_reg_copy_preferences
);
951 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_copy_preferences
,
952 allocno
[a1
].hard_reg_copy_preferences
);
955 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_preferences
,
956 allocno
[a2
].hard_reg_preferences
);
957 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_preferences
,
958 allocno
[a1
].hard_reg_preferences
);
959 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_full_preferences
,
960 allocno
[a2
].hard_reg_full_preferences
);
961 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_full_preferences
,
962 allocno
[a1
].hard_reg_full_preferences
);
966 /* Prune the preferences for global registers to exclude registers that cannot
969 Compute `regs_someone_prefers', which is a bitmask of the hard registers
970 that are preferred by conflicting registers of lower priority. If possible,
971 we will avoid using these registers. */
974 prune_preferences (void)
978 int *allocno_to_order
= XNEWVEC (int, max_allocno
);
980 /* Scan least most important to most important.
981 For each allocno, remove from preferences registers that cannot be used,
982 either because of conflicts or register type. Then compute all registers
983 preferred by each lower-priority register that conflicts. */
985 for (i
= max_allocno
- 1; i
>= 0; i
--)
989 num
= allocno_order
[i
];
990 allocno_to_order
[num
] = i
;
991 COPY_HARD_REG_SET (temp
, allocno
[num
].hard_reg_conflicts
);
993 if (allocno
[num
].calls_crossed
== 0)
994 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
996 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
998 IOR_COMPL_HARD_REG_SET
1000 reg_class_contents
[(int) reg_preferred_class (allocno
[num
].reg
)]);
1002 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, temp
);
1003 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, temp
);
1004 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_full_preferences
, temp
);
1007 for (i
= max_allocno
- 1; i
>= 0; i
--)
1009 /* Merge in the preferences of lower-priority registers (they have
1010 already been pruned). If we also prefer some of those registers,
1011 don't exclude them unless we are of a smaller size (in which case
1012 we want to give the lower-priority allocno the first chance for
1013 these registers). */
1014 HARD_REG_SET temp
, temp2
;
1017 num
= allocno_order
[i
];
1019 CLEAR_HARD_REG_SET (temp
);
1020 CLEAR_HARD_REG_SET (temp2
);
1022 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ num
* allocno_row_words
,
1025 if (allocno_to_order
[allocno2
] > i
)
1027 if (allocno
[allocno2
].size
<= allocno
[num
].size
)
1028 IOR_HARD_REG_SET (temp
,
1029 allocno
[allocno2
].hard_reg_full_preferences
);
1031 IOR_HARD_REG_SET (temp2
,
1032 allocno
[allocno2
].hard_reg_full_preferences
);
1036 AND_COMPL_HARD_REG_SET (temp
, allocno
[num
].hard_reg_full_preferences
);
1037 IOR_HARD_REG_SET (temp
, temp2
);
1038 COPY_HARD_REG_SET (allocno
[num
].regs_someone_prefers
, temp
);
1040 free (allocno_to_order
);
1043 /* Assign a hard register to allocno NUM; look for one that is the beginning
1044 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
1045 The registers marked in PREFREGS are tried first.
1047 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
1048 be used for this allocation.
1050 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
1051 Otherwise ignore that preferred class and use the alternate class.
1053 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
1054 will have to be saved and restored at calls.
1056 RETRYING is nonzero if this is called from retry_global_alloc.
1058 If we find one, record it in reg_renumber.
1059 If not, do nothing. */
1062 find_reg (int num
, HARD_REG_SET losers
, int alt_regs_p
, int accept_call_clobbered
, int retrying
)
1064 int i
, best_reg
, pass
;
1065 HARD_REG_SET used
, used1
, used2
;
1067 enum reg_class
class = (alt_regs_p
1068 ? reg_alternate_class (allocno
[num
].reg
)
1069 : reg_preferred_class (allocno
[num
].reg
));
1070 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno
[num
].reg
);
1072 if (accept_call_clobbered
)
1073 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
1074 else if (allocno
[num
].calls_crossed
== 0)
1075 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
1077 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
1079 /* Some registers should not be allocated in global-alloc. */
1080 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
1082 IOR_HARD_REG_SET (used1
, losers
);
1084 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
1085 COPY_HARD_REG_SET (used2
, used1
);
1087 IOR_HARD_REG_SET (used1
, allocno
[num
].hard_reg_conflicts
);
1089 #ifdef CANNOT_CHANGE_MODE_CLASS
1090 cannot_change_mode_set_regs (&used1
, mode
, allocno
[num
].reg
);
1093 /* Try each hard reg to see if it fits. Do this in two passes.
1094 In the first pass, skip registers that are preferred by some other pseudo
1095 to give it a better chance of getting one of those registers. Only if
1096 we can't get a register when excluding those do we take one of them.
1097 However, we never allocate a register for the first time in pass 0. */
1099 COPY_HARD_REG_SET (used
, used1
);
1100 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
1101 IOR_HARD_REG_SET (used
, allocno
[num
].regs_someone_prefers
);
1104 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
1105 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
1109 COPY_HARD_REG_SET (used
, used1
);
1110 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1112 #ifdef REG_ALLOC_ORDER
1113 int regno
= reg_alloc_order
[i
];
1117 if (! TEST_HARD_REG_BIT (used
, regno
)
1118 && HARD_REGNO_MODE_OK (regno
, mode
)
1119 && (allocno
[num
].calls_crossed
== 0
1120 || accept_call_clobbered
1121 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
)))
1124 int lim
= end_hard_regno (mode
, regno
);
1127 && ! TEST_HARD_REG_BIT (used
, j
));
1134 #ifndef REG_ALLOC_ORDER
1135 i
= j
; /* Skip starting points we know will lose */
1141 /* See if there is a preferred register with the same class as the register
1142 we allocated above. Making this restriction prevents register
1143 preferencing from creating worse register allocation.
1145 Remove from the preferred registers and conflicting registers. Note that
1146 additional conflicts may have been added after `prune_preferences' was
1149 First do this for those register with copy preferences, then all
1150 preferred registers. */
1152 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, used
);
1153 if (!hard_reg_set_empty_p (allocno
[num
].hard_reg_copy_preferences
)
1156 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1157 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_copy_preferences
, i
)
1158 && HARD_REGNO_MODE_OK (i
, mode
)
1159 && (allocno
[num
].calls_crossed
== 0
1160 || accept_call_clobbered
1161 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1162 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1163 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1164 REGNO_REG_CLASS (best_reg
))
1165 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1166 REGNO_REG_CLASS (i
))))
1169 int lim
= end_hard_regno (mode
, i
);
1172 && ! TEST_HARD_REG_BIT (used
, j
)
1173 && (REGNO_REG_CLASS (j
)
1174 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1175 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1176 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1177 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1178 REGNO_REG_CLASS (j
))));
1188 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, used
);
1189 if (!hard_reg_set_empty_p (allocno
[num
].hard_reg_preferences
)
1192 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1193 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_preferences
, i
)
1194 && HARD_REGNO_MODE_OK (i
, mode
)
1195 && (allocno
[num
].calls_crossed
== 0
1196 || accept_call_clobbered
1197 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1198 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1199 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1200 REGNO_REG_CLASS (best_reg
))
1201 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1202 REGNO_REG_CLASS (i
))))
1205 int lim
= end_hard_regno (mode
, i
);
1208 && ! TEST_HARD_REG_BIT (used
, j
)
1209 && (REGNO_REG_CLASS (j
)
1210 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1211 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1212 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1213 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1214 REGNO_REG_CLASS (j
))));
1225 /* If we haven't succeeded yet, try with caller-saves.
1226 We need not check to see if the current function has nonlocal
1227 labels because we don't put any pseudos that are live over calls in
1228 registers in that case. */
1230 if (flag_caller_saves
&& best_reg
< 0)
1232 /* Did not find a register. If it would be profitable to
1233 allocate a call-clobbered register and save and restore it
1234 around calls, do that. Don't do this if it crosses any calls
1235 that might throw. */
1236 if (! accept_call_clobbered
1237 && allocno
[num
].calls_crossed
!= 0
1238 && allocno
[num
].throwing_calls_crossed
== 0
1239 && CALLER_SAVE_PROFITABLE (allocno
[num
].n_refs
,
1240 allocno
[num
].calls_crossed
))
1242 HARD_REG_SET new_losers
;
1244 CLEAR_HARD_REG_SET (new_losers
);
1246 COPY_HARD_REG_SET (new_losers
, losers
);
1248 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1249 find_reg (num
, new_losers
, alt_regs_p
, 1, retrying
);
1250 if (reg_renumber
[allocno
[num
].reg
] >= 0)
1252 caller_save_needed
= 1;
1258 /* If we haven't succeeded yet,
1259 see if some hard reg that conflicts with us
1260 was utilized poorly by local-alloc.
1261 If so, kick out the regs that were put there by local-alloc
1262 so we can use it instead. */
1263 if (best_reg
< 0 && !retrying
1264 /* Let's not bother with multi-reg allocnos. */
1265 && allocno
[num
].size
== 1
1266 && REG_BASIC_BLOCK (allocno
[num
].reg
) == REG_BLOCK_GLOBAL
)
1268 /* Count from the end, to find the least-used ones first. */
1269 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1271 #ifdef REG_ALLOC_ORDER
1272 int regno
= reg_alloc_order
[i
];
1277 if (local_reg_n_refs
[regno
] != 0
1278 /* Don't use a reg no good for this pseudo. */
1279 && ! TEST_HARD_REG_BIT (used2
, regno
)
1280 && HARD_REGNO_MODE_OK (regno
, mode
)
1281 /* The code below assumes that we need only a single
1282 register, but the check of allocno[num].size above
1283 was not enough. Sometimes we need more than one
1284 register for a single-word value. */
1285 && hard_regno_nregs
[regno
][mode
] == 1
1286 && (allocno
[num
].calls_crossed
== 0
1287 || accept_call_clobbered
1288 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
))
1289 #ifdef CANNOT_CHANGE_MODE_CLASS
1290 && ! invalid_mode_change_p (regno
, REGNO_REG_CLASS (regno
),
1294 && (!allocno
[num
].no_stack_reg
1295 || regno
< FIRST_STACK_REG
|| regno
> LAST_STACK_REG
)
1299 /* We explicitly evaluate the divide results into temporary
1300 variables so as to avoid excess precision problems that occur
1301 on an i386-unknown-sysv4.2 (unixware) host. */
1303 double tmp1
= ((double) local_reg_freq
[regno
] * local_reg_n_refs
[regno
]
1304 / local_reg_live_length
[regno
]);
1305 double tmp2
= ((double) allocno
[num
].freq
* allocno
[num
].n_refs
1306 / allocno
[num
].live_length
);
1310 /* Hard reg REGNO was used less in total by local regs
1311 than it would be used by this one allocno! */
1315 fprintf (dump_file
, "Regno %d better for global %d, ",
1316 regno
, allocno
[num
].reg
);
1317 fprintf (dump_file
, "fr:%d, ll:%d, nr:%d ",
1318 allocno
[num
].freq
, allocno
[num
].live_length
,
1319 allocno
[num
].n_refs
);
1320 fprintf (dump_file
, "(was: fr:%d, ll:%d, nr:%d)\n",
1321 local_reg_freq
[regno
],
1322 local_reg_live_length
[regno
],
1323 local_reg_n_refs
[regno
]);
1326 for (k
= 0; k
< max_regno
; k
++)
1327 if (reg_renumber
[k
] >= 0)
1329 int r
= reg_renumber
[k
];
1331 = end_hard_regno (PSEUDO_REGNO_MODE (k
), r
);
1333 if (regno
>= r
&& regno
< endregno
)
1337 "Local Reg %d now on stack\n", k
);
1338 reg_renumber
[k
] = -1;
1349 /* Did we find a register? */
1354 HARD_REG_SET this_reg
;
1356 /* Yes. Record it as the hard register of this pseudo-reg. */
1357 reg_renumber
[allocno
[num
].reg
] = best_reg
;
1358 /* Also of any pseudo-regs that share with it. */
1359 if (reg_may_share
[allocno
[num
].reg
])
1360 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1361 if (reg_allocno
[j
] == num
)
1362 reg_renumber
[j
] = best_reg
;
1364 /* Make a set of the hard regs being allocated. */
1365 CLEAR_HARD_REG_SET (this_reg
);
1366 lim
= end_hard_regno (mode
, best_reg
);
1367 for (j
= best_reg
; j
< lim
; j
++)
1369 SET_HARD_REG_BIT (this_reg
, j
);
1370 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1371 /* This is no longer a reg used just by local regs. */
1372 local_reg_n_refs
[j
] = 0;
1373 local_reg_freq
[j
] = 0;
1375 /* For each other pseudo-reg conflicting with this one,
1376 mark it as conflicting with the hard regs this one occupies. */
1378 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ lim
* allocno_row_words
, j
,
1380 IOR_HARD_REG_SET (allocno
[j
].hard_reg_conflicts
, this_reg
);
1385 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1386 Perhaps it had previously seemed not worth a hard reg,
1387 or perhaps its old hard reg has been commandeered for reloads.
1388 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1389 they do not appear to be allocated.
1390 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1393 retry_global_alloc (int regno
, HARD_REG_SET forbidden_regs
)
1395 int alloc_no
= reg_allocno
[regno
];
1398 /* If we have more than one register class,
1399 first try allocating in the class that is cheapest
1400 for this pseudo-reg. If that fails, try any reg. */
1401 if (N_REG_CLASSES
> 1)
1402 find_reg (alloc_no
, forbidden_regs
, 0, 0, 1);
1403 if (reg_renumber
[regno
] < 0
1404 && reg_alternate_class (regno
) != NO_REGS
)
1405 find_reg (alloc_no
, forbidden_regs
, 1, 0, 1);
1407 /* If we found a register, modify the RTL for the register to
1408 show the hard register, and mark that register live. */
1409 if (reg_renumber
[regno
] >= 0)
1411 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1412 mark_home_live (regno
);
1417 /* Record a conflict between register REGNO
1418 and everything currently live.
1419 REGNO must not be a pseudo reg that was allocated
1420 by local_alloc; such numbers must be translated through
1421 reg_renumber before calling here. */
1424 record_one_conflict (int regno
)
1428 if (regno
< FIRST_PSEUDO_REGISTER
)
1429 /* When a hard register becomes live,
1430 record conflicts with live pseudo regs. */
1431 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, j
,
1433 SET_HARD_REG_BIT (allocno
[j
].hard_reg_conflicts
, regno
);
1436 /* When a pseudo-register becomes live,
1437 record conflicts first with hard regs,
1438 then with other pseudo regs. */
1440 int ialloc
= reg_allocno
[regno
];
1441 int ialloc_prod
= ialloc
* allocno_row_words
;
1443 IOR_HARD_REG_SET (allocno
[ialloc
].hard_reg_conflicts
, hard_regs_live
);
1444 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1445 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1449 /* Record all allocnos currently live as conflicting
1450 with all hard regs currently live.
1452 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1453 are currently live. Their bits are also flagged in allocnos_live. */
1456 record_conflicts (int *allocno_vec
, int len
)
1459 IOR_HARD_REG_SET (allocno
[allocno_vec
[len
]].hard_reg_conflicts
,
1463 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1465 mirror_conflicts (void)
1468 int rw
= allocno_row_words
;
1469 int rwb
= rw
* INT_BITS
;
1470 INT_TYPE
*p
= conflicts
;
1471 INT_TYPE
*q0
= conflicts
, *q1
, *q2
;
1472 unsigned INT_TYPE mask
;
1474 for (i
= max_allocno
- 1, mask
= 1; i
>= 0; i
--, mask
<<= 1)
1481 for (j
= allocno_row_words
- 1, q1
= q0
; j
>= 0; j
--, q1
+= rwb
)
1483 unsigned INT_TYPE word
;
1485 for (word
= (unsigned INT_TYPE
) *p
++, q2
= q1
; word
;
1486 word
>>= 1, q2
+= rw
)
1495 /* Handle the case where REG is set by the insn being scanned,
1496 during the forward scan to accumulate conflicts.
1497 Store a 1 in regs_live or allocnos_live for this register, record how many
1498 consecutive hardware registers it actually needs,
1499 and record a conflict with all other registers already live.
1501 Note that even if REG does not remain alive after this insn,
1502 we must mark it here as live, to ensure a conflict between
1503 REG and any other regs set in this insn that really do live.
1504 This is because those other regs could be considered after this.
1506 REG might actually be something other than a register;
1507 if so, we do nothing.
1509 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1510 a REG_INC note was found for it). */
1513 mark_reg_store (rtx reg
, rtx setter
, void *data ATTRIBUTE_UNUSED
)
1517 if (GET_CODE (reg
) == SUBREG
)
1518 reg
= SUBREG_REG (reg
);
1523 regs_set
[n_regs_set
++] = reg
;
1525 if (setter
&& GET_CODE (setter
) != CLOBBER
)
1526 set_preference (reg
, SET_SRC (setter
));
1528 regno
= REGNO (reg
);
1530 /* Either this is one of the max_allocno pseudo regs not allocated,
1531 or it is or has a hardware reg. First handle the pseudo-regs. */
1532 if (regno
>= FIRST_PSEUDO_REGISTER
)
1534 if (reg_allocno
[regno
] >= 0)
1536 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1537 record_one_conflict (regno
);
1541 if (reg_renumber
[regno
] >= 0)
1542 regno
= reg_renumber
[regno
];
1544 /* Handle hardware regs (and pseudos allocated to hard regs). */
1545 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1547 int last
= end_hard_regno (GET_MODE (reg
), regno
);
1548 while (regno
< last
)
1550 record_one_conflict (regno
);
1551 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1557 /* Like mark_reg_store except notice just CLOBBERs; ignore SETs. */
1560 mark_reg_clobber (rtx reg
, rtx setter
, void *data
)
1562 if (GET_CODE (setter
) == CLOBBER
)
1563 mark_reg_store (reg
, setter
, data
);
1566 /* Record that REG has conflicts with all the regs currently live.
1567 Do not mark REG itself as live. */
1570 mark_reg_conflicts (rtx reg
)
1574 if (GET_CODE (reg
) == SUBREG
)
1575 reg
= SUBREG_REG (reg
);
1580 regno
= REGNO (reg
);
1582 /* Either this is one of the max_allocno pseudo regs not allocated,
1583 or it is or has a hardware reg. First handle the pseudo-regs. */
1584 if (regno
>= FIRST_PSEUDO_REGISTER
)
1586 if (reg_allocno
[regno
] >= 0)
1587 record_one_conflict (regno
);
1590 if (reg_renumber
[regno
] >= 0)
1591 regno
= reg_renumber
[regno
];
1593 /* Handle hardware regs (and pseudos allocated to hard regs). */
1594 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1596 int last
= end_hard_regno (GET_MODE (reg
), regno
);
1597 while (regno
< last
)
1599 record_one_conflict (regno
);
1605 /* Mark REG as being dead (following the insn being scanned now).
1606 Store a 0 in regs_live or allocnos_live for this register. */
1609 mark_reg_death (rtx reg
)
1611 int regno
= REGNO (reg
);
1613 /* Either this is one of the max_allocno pseudo regs not allocated,
1614 or it is a hardware reg. First handle the pseudo-regs. */
1615 if (regno
>= FIRST_PSEUDO_REGISTER
)
1617 if (reg_allocno
[regno
] >= 0)
1618 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1621 /* For pseudo reg, see if it has been assigned a hardware reg. */
1622 if (reg_renumber
[regno
] >= 0)
1623 regno
= reg_renumber
[regno
];
1625 /* Handle hardware regs (and pseudos allocated to hard regs). */
1626 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1627 /* Pseudo regs already assigned hardware regs are treated
1628 almost the same as explicit hardware regs. */
1629 remove_from_hard_reg_set (&hard_regs_live
, GET_MODE (reg
), regno
);
1632 /* Try to set a preference for an allocno to a hard register.
1633 We are passed DEST and SRC which are the operands of a SET. It is known
1634 that SRC is a register. If SRC or the first operand of SRC is a register,
1635 try to set a preference. If one of the two is a hard register and the other
1636 is a pseudo-register, mark the preference.
1638 Note that we are not as aggressive as local-alloc in trying to tie a
1639 pseudo-register to a hard register. */
1642 set_preference (rtx dest
, rtx src
)
1644 unsigned int src_regno
, dest_regno
, end_regno
;
1645 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1646 to compensate for subregs in SRC or DEST. */
1651 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1652 src
= XEXP (src
, 0), copy
= 0;
1654 /* Get the reg number for both SRC and DEST.
1655 If neither is a reg, give up. */
1658 src_regno
= REGNO (src
);
1659 else if (GET_CODE (src
) == SUBREG
&& REG_P (SUBREG_REG (src
)))
1661 src_regno
= REGNO (SUBREG_REG (src
));
1663 if (REGNO (SUBREG_REG (src
)) < FIRST_PSEUDO_REGISTER
)
1664 offset
+= subreg_regno_offset (REGNO (SUBREG_REG (src
)),
1665 GET_MODE (SUBREG_REG (src
)),
1669 offset
+= (SUBREG_BYTE (src
)
1670 / REGMODE_NATURAL_SIZE (GET_MODE (src
)));
1676 dest_regno
= REGNO (dest
);
1677 else if (GET_CODE (dest
) == SUBREG
&& REG_P (SUBREG_REG (dest
)))
1679 dest_regno
= REGNO (SUBREG_REG (dest
));
1681 if (REGNO (SUBREG_REG (dest
)) < FIRST_PSEUDO_REGISTER
)
1682 offset
-= subreg_regno_offset (REGNO (SUBREG_REG (dest
)),
1683 GET_MODE (SUBREG_REG (dest
)),
1687 offset
-= (SUBREG_BYTE (dest
)
1688 / REGMODE_NATURAL_SIZE (GET_MODE (dest
)));
1693 /* Convert either or both to hard reg numbers. */
1695 if (reg_renumber
[src_regno
] >= 0)
1696 src_regno
= reg_renumber
[src_regno
];
1698 if (reg_renumber
[dest_regno
] >= 0)
1699 dest_regno
= reg_renumber
[dest_regno
];
1701 /* Now if one is a hard reg and the other is a global pseudo
1702 then give the other a preference. */
1704 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1705 && reg_allocno
[src_regno
] >= 0)
1707 dest_regno
-= offset
;
1708 if (dest_regno
< FIRST_PSEUDO_REGISTER
)
1711 SET_REGBIT (hard_reg_copy_preferences
,
1712 reg_allocno
[src_regno
], dest_regno
);
1714 SET_REGBIT (hard_reg_preferences
,
1715 reg_allocno
[src_regno
], dest_regno
);
1716 end_regno
= end_hard_regno (GET_MODE (dest
), dest_regno
);
1717 for (i
= dest_regno
; i
< end_regno
; i
++)
1718 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1722 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1723 && reg_allocno
[dest_regno
] >= 0)
1725 src_regno
+= offset
;
1726 if (src_regno
< FIRST_PSEUDO_REGISTER
)
1729 SET_REGBIT (hard_reg_copy_preferences
,
1730 reg_allocno
[dest_regno
], src_regno
);
1732 SET_REGBIT (hard_reg_preferences
,
1733 reg_allocno
[dest_regno
], src_regno
);
1734 end_regno
= end_hard_regno (GET_MODE (src
), src_regno
);
1735 for (i
= src_regno
; i
< end_regno
; i
++)
1736 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1741 /* Indicate that hard register number FROM was eliminated and replaced with
1742 an offset from hard register number TO. The status of hard registers live
1743 at the start of a basic block is updated by replacing a use of FROM with
1747 mark_elimination (int from
, int to
)
1753 regset r
= bb
->il
.rtl
->global_live_at_start
;
1754 if (REGNO_REG_SET_P (r
, from
))
1756 CLEAR_REGNO_REG_SET (r
, from
);
1757 SET_REGNO_REG_SET (r
, to
);
1762 /* Used for communication between the following functions. Holds the
1763 current life information. */
1764 static regset live_relevant_regs
;
1766 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1767 This is called via note_stores. */
1769 reg_becomes_live (rtx reg
, rtx setter ATTRIBUTE_UNUSED
, void *regs_set
)
1773 if (GET_CODE (reg
) == SUBREG
)
1774 reg
= SUBREG_REG (reg
);
1779 regno
= REGNO (reg
);
1780 if (regno
< FIRST_PSEUDO_REGISTER
)
1782 int nregs
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1785 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1786 if (! fixed_regs
[regno
])
1787 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1791 else if (reg_renumber
[regno
] >= 0)
1793 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1794 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1798 /* Record in live_relevant_regs that register REGNO died. */
1800 reg_dies (int regno
, enum machine_mode mode
, struct insn_chain
*chain
)
1802 if (regno
< FIRST_PSEUDO_REGISTER
)
1804 int nregs
= hard_regno_nregs
[regno
][mode
];
1807 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1808 if (! fixed_regs
[regno
])
1809 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1815 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1816 if (reg_renumber
[regno
] >= 0)
1817 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1821 /* Walk the insns of the current function and build reload_insn_chain,
1822 and record register life information. */
1824 build_insn_chain (rtx first
)
1826 struct insn_chain
**p
= &reload_insn_chain
;
1827 struct insn_chain
*prev
= 0;
1828 basic_block b
= ENTRY_BLOCK_PTR
->next_bb
;
1830 live_relevant_regs
= ALLOC_REG_SET (®_obstack
);
1832 for (; first
; first
= NEXT_INSN (first
))
1834 struct insn_chain
*c
;
1836 if (first
== BB_HEAD (b
))
1841 CLEAR_REG_SET (live_relevant_regs
);
1843 EXECUTE_IF_SET_IN_BITMAP (b
->il
.rtl
->global_live_at_start
, 0, i
, bi
)
1845 if (i
< FIRST_PSEUDO_REGISTER
1846 ? ! TEST_HARD_REG_BIT (eliminable_regset
, i
)
1847 : reg_renumber
[i
] >= 0)
1848 SET_REGNO_REG_SET (live_relevant_regs
, i
);
1852 if (!NOTE_P (first
) && !BARRIER_P (first
))
1854 c
= new_insn_chain ();
1860 c
->block
= b
->index
;
1866 /* Mark the death of everything that dies in this instruction. */
1868 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1869 if (REG_NOTE_KIND (link
) == REG_DEAD
1870 && REG_P (XEXP (link
, 0)))
1871 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1874 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1876 /* Mark everything born in this instruction as live. */
1878 note_stores (PATTERN (first
), reg_becomes_live
,
1882 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1888 /* Mark anything that is set in this insn and then unused as dying. */
1890 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1891 if (REG_NOTE_KIND (link
) == REG_UNUSED
1892 && REG_P (XEXP (link
, 0)))
1893 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1898 if (first
== BB_END (b
))
1901 /* Stop after we pass the end of the last basic block. Verify that
1902 no real insns are after the end of the last basic block.
1904 We may want to reorganize the loop somewhat since this test should
1905 always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if
1906 the previous real insn is a JUMP_INSN. */
1907 if (b
== EXIT_BLOCK_PTR
)
1909 #ifdef ENABLE_CHECKING
1910 for (first
= NEXT_INSN (first
); first
; first
= NEXT_INSN (first
))
1911 gcc_assert (!INSN_P (first
)
1912 || GET_CODE (PATTERN (first
)) == USE
1913 || ((GET_CODE (PATTERN (first
)) == ADDR_VEC
1914 || GET_CODE (PATTERN (first
)) == ADDR_DIFF_VEC
)
1915 && prev_real_insn (first
) != 0
1916 && JUMP_P (prev_real_insn (first
))));
1921 FREE_REG_SET (live_relevant_regs
);
1925 /* Print debugging trace information if -dg switch is given,
1926 showing the information on which the allocation decisions are based. */
1929 dump_conflicts (FILE *file
)
1932 int has_preferences
;
1935 for (i
= 0; i
< max_allocno
; i
++)
1937 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1941 fprintf (file
, ";; %d regs to allocate:", nregs
);
1942 for (i
= 0; i
< max_allocno
; i
++)
1945 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1947 fprintf (file
, " %d", allocno
[allocno_order
[i
]].reg
);
1948 for (j
= 0; j
< max_regno
; j
++)
1949 if (reg_allocno
[j
] == allocno_order
[i
]
1950 && j
!= allocno
[allocno_order
[i
]].reg
)
1951 fprintf (file
, "+%d", j
);
1952 if (allocno
[allocno_order
[i
]].size
!= 1)
1953 fprintf (file
, " (%d)", allocno
[allocno_order
[i
]].size
);
1955 fprintf (file
, "\n");
1957 for (i
= 0; i
< max_allocno
; i
++)
1960 fprintf (file
, ";; %d conflicts:", allocno
[i
].reg
);
1961 for (j
= 0; j
< max_allocno
; j
++)
1962 if (CONFLICTP (j
, i
))
1963 fprintf (file
, " %d", allocno
[j
].reg
);
1964 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1965 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_conflicts
, j
))
1966 fprintf (file
, " %d", j
);
1967 fprintf (file
, "\n");
1969 has_preferences
= 0;
1970 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1971 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1972 has_preferences
= 1;
1974 if (! has_preferences
)
1976 fprintf (file
, ";; %d preferences:", allocno
[i
].reg
);
1977 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1978 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1979 fprintf (file
, " %d", j
);
1980 fprintf (file
, "\n");
1982 fprintf (file
, "\n");
1986 dump_global_regs (FILE *file
)
1990 fprintf (file
, ";; Register dispositions:\n");
1991 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1992 if (reg_renumber
[i
] >= 0)
1994 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1996 fprintf (file
, "\n");
1999 fprintf (file
, "\n\n;; Hard regs used: ");
2000 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2001 if (regs_ever_live
[i
])
2002 fprintf (file
, " %d", i
);
2003 fprintf (file
, "\n\n");
2008 /* This page contains code to make live information more accurate.
2009 The accurate register liveness at program point P means:
2010 o there is a path from P to usage of the register and the
2011 register is not redefined or killed on the path.
2012 o register at P is partially available, i.e. there is a path from
2013 a register definition to the point P and the register is not
2014 killed (clobbered) on the path
2016 The standard GCC live information means only the first condition.
2017 Without the partial availability, there will be more register
2018 conflicts and as a consequence worse register allocation. The
2019 typical example where the information can be different is a
2020 register initialized in the loop at the basic block preceding the
2023 /* The following structure contains basic block data flow information
2024 used to calculate partial availability of registers. */
2028 /* The basic block reverse post-order number. */
2030 /* Registers used uninitialized in an insn in which there is an
2031 early clobbered register might get the same hard register. */
2032 bitmap earlyclobber
;
2033 /* Registers correspondingly killed (clobbered) and defined but not
2034 killed afterward in the basic block. */
2035 bitmap killed
, avloc
;
2036 /* Registers partially available and living (in other words whose
2037 values were calculated and used) correspondingly at the start
2038 and end of the basic block. */
2039 bitmap live_pavin
, live_pavout
;
2042 /* Macros for accessing data flow information of basic blocks. */
2044 #define BB_INFO(BB) ((struct bb_info *) (BB)->aux)
2045 #define BB_INFO_BY_INDEX(N) BB_INFO (BASIC_BLOCK(N))
2047 static struct bitmap_obstack greg_obstack
;
2048 /* The function allocates the info structures of each basic block. It
2049 also initialized LIVE_PAVIN and LIVE_PAVOUT as if all hard
2050 registers were partially available. */
2053 allocate_bb_info (void)
2057 struct bb_info
*bb_info
;
2060 alloc_aux_for_blocks (sizeof (struct bb_info
));
2061 init
= BITMAP_ALLOC (NULL
);
2062 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2063 bitmap_set_bit (init
, i
);
2064 bitmap_obstack_initialize (&greg_obstack
);
2068 bb_info
->earlyclobber
= BITMAP_ALLOC (&greg_obstack
);
2069 bb_info
->avloc
= BITMAP_ALLOC (&greg_obstack
);
2070 bb_info
->killed
= BITMAP_ALLOC (&greg_obstack
);
2071 bb_info
->live_pavin
= BITMAP_ALLOC (&greg_obstack
);
2072 bb_info
->live_pavout
= BITMAP_ALLOC (&greg_obstack
);
2073 bitmap_copy (bb_info
->live_pavin
, init
);
2074 bitmap_copy (bb_info
->live_pavout
, init
);
2079 /* The function frees the allocated info of all basic blocks. */
2084 bitmap_obstack_release (&greg_obstack
);
2085 free_aux_for_blocks ();
2088 /* The function modifies local info for register REG being changed in
2089 SETTER. DATA is used to pass the current basic block info. */
2092 mark_reg_change (rtx reg
, rtx setter
, void *data
)
2095 basic_block bb
= data
;
2096 struct bb_info
*bb_info
= BB_INFO (bb
);
2098 if (GET_CODE (reg
) == SUBREG
)
2099 reg
= SUBREG_REG (reg
);
2104 regno
= REGNO (reg
);
2105 bitmap_set_bit (bb_info
->killed
, regno
);
2107 if (GET_CODE (setter
) != CLOBBER
)
2108 bitmap_set_bit (bb_info
->avloc
, regno
);
2110 bitmap_clear_bit (bb_info
->avloc
, regno
);
2113 /* Classes of registers which could be early clobbered in the current
2116 static VEC(int,heap
) *earlyclobber_regclass
;
2118 /* This function finds and stores register classes that could be early
2119 clobbered in INSN. If any earlyclobber classes are found, the function
2120 returns TRUE, in all other cases it returns FALSE. */
2123 check_earlyclobber (rtx insn
)
2128 extract_insn (insn
);
2130 VEC_truncate (int, earlyclobber_regclass
, 0);
2131 for (opno
= 0; opno
< recog_data
.n_operands
; opno
++)
2136 enum reg_class
class;
2137 const char *p
= recog_data
.constraints
[opno
];
2146 case '=': case '+': case '?':
2149 case 'm': case '<': case '>': case 'V': case 'o':
2150 case 'E': case 'F': case 'G': case 'H':
2151 case 's': case 'i': case 'n':
2152 case 'I': case 'J': case 'K': case 'L':
2153 case 'M': case 'N': case 'O': case 'P':
2155 case '0': case '1': case '2': case '3': case '4':
2156 case '5': case '6': case '7': case '8': case '9':
2157 /* These don't say anything we care about. */
2165 if (amp_p
&& class != NO_REGS
)
2171 VEC_iterate (int, earlyclobber_regclass
, i
, rc
);
2174 if (rc
== (int) class)
2178 /* We use VEC_quick_push here because
2179 earlyclobber_regclass holds no more than
2180 N_REG_CLASSES elements. */
2181 VEC_quick_push (int, earlyclobber_regclass
, (int) class);
2191 class = GENERAL_REGS
;
2195 class = REG_CLASS_FROM_CONSTRAINT (c
, p
);
2200 p
+= CONSTRAINT_LEN (c
, p
);
2207 /* The function checks that pseudo-register *X has a class
2208 intersecting with the class of pseudo-register could be early
2209 clobbered in the same insn.
2210 This function is a no-op if earlyclobber_regclass is empty. */
2213 mark_reg_use_for_earlyclobber (rtx
*x
, void *data ATTRIBUTE_UNUSED
)
2215 enum reg_class pref_class
, alt_class
;
2217 basic_block bb
= data
;
2218 struct bb_info
*bb_info
= BB_INFO (bb
);
2220 if (REG_P (*x
) && REGNO (*x
) >= FIRST_PSEUDO_REGISTER
)
2225 if (bitmap_bit_p (bb_info
->killed
, regno
)
2226 || bitmap_bit_p (bb_info
->avloc
, regno
))
2228 pref_class
= reg_preferred_class (regno
);
2229 alt_class
= reg_alternate_class (regno
);
2230 for (i
= 0; VEC_iterate (int, earlyclobber_regclass
, i
, rc
); i
++)
2232 if (reg_classes_intersect_p (rc
, pref_class
)
2234 && reg_classes_intersect_p (rc
, alt_class
)))
2236 bitmap_set_bit (bb_info
->earlyclobber
, regno
);
2244 /* The function processes all pseudo-registers in *X with the aid of
2245 previous function. */
2248 mark_reg_use_for_earlyclobber_1 (rtx
*x
, void *data
)
2250 for_each_rtx (x
, mark_reg_use_for_earlyclobber
, data
);
2253 /* The function calculates local info for each basic block. */
2256 calculate_local_reg_bb_info (void)
2261 /* We know that earlyclobber_regclass holds no more than
2262 N_REG_CLASSES elements. See check_earlyclobber. */
2263 earlyclobber_regclass
= VEC_alloc (int, heap
, N_REG_CLASSES
);
2266 bound
= NEXT_INSN (BB_END (bb
));
2267 for (insn
= BB_HEAD (bb
); insn
!= bound
; insn
= NEXT_INSN (insn
))
2270 note_stores (PATTERN (insn
), mark_reg_change
, bb
);
2271 if (check_earlyclobber (insn
))
2272 note_uses (&PATTERN (insn
), mark_reg_use_for_earlyclobber_1
, bb
);
2275 VEC_free (int, heap
, earlyclobber_regclass
);
2278 /* The function sets up reverse post-order number of each basic
2282 set_up_bb_rts_numbers (void)
2287 rts_order
= XNEWVEC (int, n_basic_blocks
- NUM_FIXED_BLOCKS
);
2288 post_order_compute (rts_order
, false);
2289 for (i
= 0; i
< n_basic_blocks
- NUM_FIXED_BLOCKS
; i
++)
2290 BB_INFO_BY_INDEX (rts_order
[i
])->rts_number
= i
;
2294 /* Compare function for sorting blocks in reverse postorder. */
2297 rpost_cmp (const void *bb1
, const void *bb2
)
2299 basic_block b1
= *(basic_block
*) bb1
, b2
= *(basic_block
*) bb2
;
2301 return BB_INFO (b2
)->rts_number
- BB_INFO (b1
)->rts_number
;
2304 /* Temporary bitmap used for live_pavin, live_pavout calculation. */
2305 static bitmap temp_bitmap
;
2307 /* The function calculates partial register availability according to
2308 the following equations:
2311 = empty for entry block
2312 | union (live_pavout of predecessors) & global_live_at_start
2313 bb.live_pavout = union (bb.live_pavin - bb.killed, bb.avloc)
2314 & global_live_at_end */
2317 calculate_reg_pav (void)
2319 basic_block bb
, succ
;
2322 VEC(basic_block
,heap
) *bbs
, *new_bbs
, *temp
;
2323 basic_block
*bb_array
;
2326 bbs
= VEC_alloc (basic_block
, heap
, n_basic_blocks
);
2327 new_bbs
= VEC_alloc (basic_block
, heap
, n_basic_blocks
);
2328 temp_bitmap
= BITMAP_ALLOC (NULL
);
2331 VEC_quick_push (basic_block
, bbs
, bb
);
2333 wset
= sbitmap_alloc (n_basic_blocks
+ 1);
2334 while (VEC_length (basic_block
, bbs
))
2336 bb_array
= VEC_address (basic_block
, bbs
);
2337 nel
= VEC_length (basic_block
, bbs
);
2338 qsort (bb_array
, nel
, sizeof (basic_block
), rpost_cmp
);
2339 sbitmap_zero (wset
);
2340 for (i
= 0; i
< nel
; i
++)
2343 struct bb_info
*bb_info
;
2344 bitmap bb_live_pavin
, bb_live_pavout
;
2347 bb_info
= BB_INFO (bb
);
2348 bb_live_pavin
= bb_info
->live_pavin
;
2349 bb_live_pavout
= bb_info
->live_pavout
;
2350 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2352 basic_block pred
= e
->src
;
2354 if (pred
->index
!= ENTRY_BLOCK
)
2355 bitmap_ior_into (bb_live_pavin
, BB_INFO (pred
)->live_pavout
);
2357 bitmap_and_into (bb_live_pavin
, bb
->il
.rtl
->global_live_at_start
);
2358 bitmap_ior_and_compl (temp_bitmap
, bb_info
->avloc
,
2359 bb_live_pavin
, bb_info
->killed
);
2360 bitmap_and_into (temp_bitmap
, bb
->il
.rtl
->global_live_at_end
);
2361 if (! bitmap_equal_p (temp_bitmap
, bb_live_pavout
))
2363 bitmap_copy (bb_live_pavout
, temp_bitmap
);
2364 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2367 if (succ
->index
!= EXIT_BLOCK
2368 && !TEST_BIT (wset
, succ
->index
))
2370 SET_BIT (wset
, succ
->index
);
2371 VEC_quick_push (basic_block
, new_bbs
, succ
);
2379 VEC_truncate (basic_block
, new_bbs
, 0);
2381 sbitmap_free (wset
);
2382 BITMAP_FREE (temp_bitmap
);
2383 VEC_free (basic_block
, heap
, new_bbs
);
2384 VEC_free (basic_block
, heap
, bbs
);
2387 /* The function modifies partial availability information for two
2388 special cases to prevent incorrect work of the subsequent passes
2389 with the accurate live information based on the partial
2393 modify_reg_pav (void)
2396 struct bb_info
*bb_info
;
2399 HARD_REG_SET stack_hard_regs
, used
;
2402 CLEAR_HARD_REG_SET (stack_hard_regs
);
2403 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
2404 SET_HARD_REG_BIT(stack_hard_regs
, i
);
2405 stack_regs
= BITMAP_ALLOC (&greg_obstack
);
2406 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
2408 COPY_HARD_REG_SET (used
, reg_class_contents
[reg_preferred_class (i
)]);
2409 IOR_HARD_REG_SET (used
, reg_class_contents
[reg_alternate_class (i
)]);
2410 AND_HARD_REG_SET (used
, stack_hard_regs
);
2411 if (!hard_reg_set_empty_p (used
))
2412 bitmap_set_bit (stack_regs
, i
);
2417 bb_info
= BB_INFO (bb
);
2419 /* Reload can assign the same hard register to uninitialized
2420 pseudo-register and early clobbered pseudo-register in an
2421 insn if the pseudo-register is used first time in given BB
2422 and not lived at the BB start. To prevent this we don't
2423 change life information for such pseudo-registers. */
2424 bitmap_ior_into (bb_info
->live_pavin
, bb_info
->earlyclobber
);
2426 /* We can not use the same stack register for uninitialized
2427 pseudo-register and another living pseudo-register because if the
2428 uninitialized pseudo-register dies, subsequent pass reg-stack
2429 will be confused (it will believe that the other register
2431 bitmap_ior_into (bb_info
->live_pavin
, stack_regs
);
2435 BITMAP_FREE (stack_regs
);
2439 /* The following function makes live information more accurate by
2440 modifying global_live_at_start and global_live_at_end of basic
2443 The standard GCC life analysis permits registers to live
2444 uninitialized, for example:
2453 With normal life_analysis, R would be live before "Loop:".
2454 The result is that R causes many interferences that do not
2457 After the function call a register lives at a program point
2458 only if it is initialized on a path from CFG entry to the
2462 make_accurate_live_analysis (void)
2465 struct bb_info
*bb_info
;
2467 max_regno
= max_reg_num ();
2469 allocate_bb_info ();
2470 calculate_local_reg_bb_info ();
2471 set_up_bb_rts_numbers ();
2472 calculate_reg_pav ();
2476 bb_info
= BB_INFO (bb
);
2478 bitmap_and_into (bb
->il
.rtl
->global_live_at_start
, bb_info
->live_pavin
);
2479 bitmap_and_into (bb
->il
.rtl
->global_live_at_end
, bb_info
->live_pavout
);
2483 /* Run old register allocator. Return TRUE if we must exit
2484 rest_of_compilation upon return. */
2486 rest_of_handle_global_alloc (void)
2490 /* If optimizing, allocate remaining pseudo-regs. Do the reload
2491 pass fixing up any insns that are invalid. */
2494 failure
= global_alloc ();
2497 compute_regsets (regs_asm_clobbered
, regs_ever_live
,
2498 &eliminable_regset
, &no_global_alloc_regs
);
2499 build_insn_chain (get_insns ());
2500 failure
= reload (get_insns (), 0);
2503 if (dump_enabled_p (pass_global_alloc
.static_pass_number
))
2505 timevar_push (TV_DUMP
);
2506 dump_global_regs (dump_file
);
2507 timevar_pop (TV_DUMP
);
2510 gcc_assert (reload_completed
|| failure
);
2511 reload_completed
= !failure
;
2515 struct tree_opt_pass pass_global_alloc
=
2519 rest_of_handle_global_alloc
, /* execute */
2522 0, /* static_pass_number */
2523 TV_GLOBAL_ALLOC
, /* tv_id */
2524 0, /* properties_required */
2525 0, /* properties_provided */
2526 0, /* properties_destroyed */
2527 0, /* todo_flags_start */
2529 TODO_ggc_collect
, /* todo_flags_finish */