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"
42 /* This pass of the compiler performs global register allocation.
43 It assigns hard register numbers to all the pseudo registers
44 that were not handled in local_alloc. Assignments are recorded
45 in the vector reg_renumber, not by changing the rtl code.
46 (Such changes are made by final). The entry point is
47 the function global_alloc.
49 After allocation is complete, the reload pass is run as a subroutine
50 of this pass, so that when a pseudo reg loses its hard reg due to
51 spilling it is possible to make a second attempt to find a hard
52 reg for it. The reload pass is independent in other respects
53 and it is run even when stupid register allocation is in use.
55 1. Assign allocation-numbers (allocnos) to the pseudo-registers
56 still needing allocations and to the pseudo-registers currently
57 allocated by local-alloc which may be spilled by reload.
58 Set up tables reg_allocno and allocno_reg to map
59 reg numbers to allocnos and vice versa.
60 max_allocno gets the number of allocnos in use.
62 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
63 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
64 for conflicts between allocnos and explicit hard register use
65 (which includes use of pseudo-registers allocated by local_alloc).
67 3. For each basic block
68 walk forward through the block, recording which
69 pseudo-registers and which hardware registers are live.
70 Build the conflict matrix between the pseudo-registers
71 and another of pseudo-registers versus hardware registers.
72 Also record the preferred hardware registers
73 for each pseudo-register.
75 4. Sort a table of the allocnos into order of
76 desirability of the variables.
78 5. Allocate the variables in that order; each if possible into
79 a preferred register, else into another register. */
81 /* Number of pseudo-registers which are candidates for allocation. */
83 static int max_allocno
;
85 /* Indexed by (pseudo) reg number, gives the allocno, or -1
86 for pseudo registers which are not to be allocated. */
88 static int *reg_allocno
;
93 /* Gives the number of consecutive hard registers needed by that
97 /* Number of calls crossed by each allocno. */
100 /* Number of refs to each allocno. */
103 /* Frequency of uses of each allocno. */
106 /* Guess at live length of each allocno.
107 This is actually the max of the live lengths of the regs. */
110 /* Set of hard regs conflicting with allocno N. */
112 HARD_REG_SET hard_reg_conflicts
;
114 /* Set of hard regs preferred by allocno N.
115 This is used to make allocnos go into regs that are copied to or from them,
116 when possible, to reduce register shuffling. */
118 HARD_REG_SET hard_reg_preferences
;
120 /* Similar, but just counts register preferences made in simple copy
121 operations, rather than arithmetic. These are given priority because
122 we can always eliminate an insn by using these, but using a register
123 in the above list won't always eliminate an insn. */
125 HARD_REG_SET hard_reg_copy_preferences
;
127 /* Similar to hard_reg_preferences, but includes bits for subsequent
128 registers when an allocno is multi-word. The above variable is used for
129 allocation while this is used to build reg_someone_prefers, below. */
131 HARD_REG_SET hard_reg_full_preferences
;
133 /* Set of hard registers that some later allocno has a preference for. */
135 HARD_REG_SET regs_someone_prefers
;
138 /* Set to true if allocno can't be allocated in the stack register. */
143 static struct allocno
*allocno
;
145 /* A vector of the integers from 0 to max_allocno-1,
146 sorted in the order of first-to-be-allocated first. */
148 static int *allocno_order
;
150 /* Indexed by (pseudo) reg number, gives the number of another
151 lower-numbered pseudo reg which can share a hard reg with this pseudo
152 *even if the two pseudos would otherwise appear to conflict*. */
154 static int *reg_may_share
;
156 /* Define the number of bits in each element of `conflicts' and what
157 type that element has. We use the largest integer format on the
160 #define INT_BITS HOST_BITS_PER_WIDE_INT
161 #define INT_TYPE HOST_WIDE_INT
163 /* max_allocno by max_allocno array of bits,
164 recording whether two allocno's conflict (can't go in the same
167 `conflicts' is symmetric after the call to mirror_conflicts. */
169 static INT_TYPE
*conflicts
;
171 /* Number of ints require to hold max_allocno bits.
172 This is the length of a row in `conflicts'. */
174 static int allocno_row_words
;
176 /* Two macros to test or store 1 in an element of `conflicts'. */
178 #define CONFLICTP(I, J) \
179 (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS] \
180 & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS)))
182 /* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
184 #define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
188 INT_TYPE *p_ = (ALLOCNO_SET); \
190 for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
191 i_--, allocno_ += INT_BITS) \
193 unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
195 for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
203 /* This doesn't work for non-GNU C due to the way CODE is macro expanded. */
205 /* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to
206 the conflicting allocno, and execute CODE. This macro assumes that
207 mirror_conflicts has been run. */
208 #define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\
209 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\
213 /* Set of hard regs currently live (during scan of all insns). */
215 static HARD_REG_SET hard_regs_live
;
217 /* Set of registers that global-alloc isn't supposed to use. */
219 static HARD_REG_SET no_global_alloc_regs
;
221 /* Set of registers used so far. */
223 static HARD_REG_SET regs_used_so_far
;
225 /* Number of refs to each hard reg, as used by local alloc.
226 It is zero for a reg that contains global pseudos or is explicitly used. */
228 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
230 /* Frequency of uses of given hard reg. */
231 static int local_reg_freq
[FIRST_PSEUDO_REGISTER
];
233 /* Guess at live length of each hard reg, as used by local alloc.
234 This is actually the sum of the live lengths of the specific regs. */
236 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
238 /* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
239 element I, and hard register number J. */
241 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
243 /* Bit mask for allocnos live at current point in the scan. */
245 static INT_TYPE
*allocnos_live
;
247 /* Test, set or clear bit number I in allocnos_live,
248 a bit vector indexed by allocno. */
250 #define SET_ALLOCNO_LIVE(I) \
251 (allocnos_live[(unsigned) (I) / INT_BITS] \
252 |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
254 #define CLEAR_ALLOCNO_LIVE(I) \
255 (allocnos_live[(unsigned) (I) / INT_BITS] \
256 &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
258 /* This is turned off because it doesn't work right for DImode.
259 (And it is only used for DImode, so the other cases are worthless.)
260 The problem is that it isn't true that there is NO possibility of conflict;
261 only that there is no conflict if the two pseudos get the exact same regs.
262 If they were allocated with a partial overlap, there would be a conflict.
263 We can't safely turn off the conflict unless we have another way to
264 prevent the partial overlap.
266 Idea: change hard_reg_conflicts so that instead of recording which
267 hard regs the allocno may not overlap, it records where the allocno
268 may not start. Change both where it is used and where it is updated.
269 Then there is a way to record that (reg:DI 108) may start at 10
270 but not at 9 or 11. There is still the question of how to record
271 this semi-conflict between two pseudos. */
273 /* Reg pairs for which conflict after the current insn
274 is inhibited by a REG_NO_CONFLICT note.
275 If the table gets full, we ignore any other notes--that is conservative. */
276 #define NUM_NO_CONFLICT_PAIRS 4
277 /* Number of pairs in use in this insn. */
278 int n_no_conflict_pairs
;
279 static struct { int allocno1
, allocno2
;}
280 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
283 /* Record all regs that are set in any one insn.
284 Communication from mark_reg_{store,clobber} and global_conflicts. */
286 static rtx
*regs_set
;
287 static int n_regs_set
;
289 /* All registers that can be eliminated. */
291 static HARD_REG_SET eliminable_regset
;
293 static int allocno_compare (const void *, const void *);
294 static void global_conflicts (void);
295 static void mirror_conflicts (void);
296 static void expand_preferences (void);
297 static void prune_preferences (void);
298 static void find_reg (int, HARD_REG_SET
, int, int, int);
299 static void record_one_conflict (int);
300 static void record_conflicts (int *, int);
301 static void mark_reg_store (rtx
, rtx
, void *);
302 static void mark_reg_clobber (rtx
, rtx
, void *);
303 static void mark_reg_conflicts (rtx
);
304 static void mark_reg_death (rtx
);
305 static void mark_reg_live_nc (int, enum machine_mode
);
306 static void set_preference (rtx
, rtx
);
307 static void dump_conflicts (FILE *);
308 static void reg_becomes_live (rtx
, rtx
, void *);
309 static void reg_dies (int, enum machine_mode
, struct insn_chain
*);
311 static void allocate_bb_info (void);
312 static void free_bb_info (void);
313 static bool check_earlyclobber (rtx
);
314 static void mark_reg_use_for_earlyclobber_1 (rtx
*, void *);
315 static int mark_reg_use_for_earlyclobber (rtx
*, void *);
316 static void calculate_local_reg_bb_info (void);
317 static void set_up_bb_rts_numbers (void);
318 static int rpost_cmp (const void *, const void *);
319 static void calculate_reg_pav (void);
320 static void modify_reg_pav (void);
321 static void make_accurate_live_analysis (void);
325 /* Perform allocation of pseudo-registers not allocated by local_alloc.
326 FILE is a file to output debugging information on,
327 or zero if such output is not desired.
329 Return value is nonzero if reload failed
330 and we must not do any more for this function. */
333 global_alloc (FILE *file
)
336 #ifdef ELIMINABLE_REGS
337 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
340 = (! flag_omit_frame_pointer
341 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
342 || FRAME_POINTER_REQUIRED
);
347 make_accurate_live_analysis ();
351 /* A machine may have certain hard registers that
352 are safe to use only within a basic block. */
354 CLEAR_HARD_REG_SET (no_global_alloc_regs
);
356 /* Build the regset of all eliminable registers and show we can't use those
357 that we already know won't be eliminated. */
358 #ifdef ELIMINABLE_REGS
359 for (i
= 0; i
< ARRAY_SIZE (eliminables
); i
++)
362 = (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
363 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
));
365 if (!regs_asm_clobbered
[eliminables
[i
].from
])
367 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
370 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
372 else if (cannot_elim
)
373 error ("%s cannot be used in asm here",
374 reg_names
[eliminables
[i
].from
]);
376 regs_ever_live
[eliminables
[i
].from
] = 1;
378 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
379 if (!regs_asm_clobbered
[HARD_FRAME_POINTER_REGNUM
])
381 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
383 SET_HARD_REG_BIT (no_global_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
386 error ("%s cannot be used in asm here",
387 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
389 regs_ever_live
[HARD_FRAME_POINTER_REGNUM
] = 1;
393 if (!regs_asm_clobbered
[FRAME_POINTER_REGNUM
])
395 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
397 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
400 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
402 regs_ever_live
[FRAME_POINTER_REGNUM
] = 1;
405 /* Track which registers have already been used. Start with registers
406 explicitly in the rtl, then registers allocated by local register
409 CLEAR_HARD_REG_SET (regs_used_so_far
);
410 #ifdef LEAF_REGISTERS
411 /* If we are doing the leaf function optimization, and this is a leaf
412 function, it means that the registers that take work to save are those
413 that need a register window. So prefer the ones that can be used in
416 const char *cheap_regs
;
417 const char *const leaf_regs
= LEAF_REGISTERS
;
419 if (only_leaf_regs_used () && leaf_function_p ())
420 cheap_regs
= leaf_regs
;
422 cheap_regs
= call_used_regs
;
423 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
424 if (regs_ever_live
[i
] || cheap_regs
[i
])
425 SET_HARD_REG_BIT (regs_used_so_far
, i
);
428 /* We consider registers that do not have to be saved over calls as if
429 they were already used since there is no cost in using them. */
430 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
431 if (regs_ever_live
[i
] || call_used_regs
[i
])
432 SET_HARD_REG_BIT (regs_used_so_far
, i
);
435 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
436 if (reg_renumber
[i
] >= 0)
437 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
439 /* Establish mappings from register number to allocation number
440 and vice versa. In the process, count the allocnos. */
442 reg_allocno
= xmalloc (max_regno
* sizeof (int));
444 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
447 /* Initialize the shared-hard-reg mapping
448 from the list of pairs that may share. */
449 reg_may_share
= xcalloc (max_regno
, sizeof (int));
450 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
452 int r1
= REGNO (XEXP (x
, 0));
453 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
455 reg_may_share
[r1
] = r2
;
457 reg_may_share
[r2
] = r1
;
460 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
461 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
462 that we are supposed to refrain from putting in a hard reg.
463 -2 means do make an allocno but don't allocate it. */
464 if (REG_N_REFS (i
) != 0 && REG_LIVE_LENGTH (i
) != -1
465 /* Don't allocate pseudos that cross calls,
466 if this function receives a nonlocal goto. */
467 && (! current_function_has_nonlocal_label
468 || REG_N_CALLS_CROSSED (i
) == 0))
470 if (reg_renumber
[i
] < 0
471 && reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
472 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
474 reg_allocno
[i
] = max_allocno
++;
475 gcc_assert (REG_LIVE_LENGTH (i
));
480 allocno
= xcalloc (max_allocno
, sizeof (struct allocno
));
482 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
483 if (reg_allocno
[i
] >= 0)
485 int num
= reg_allocno
[i
];
486 allocno
[num
].reg
= i
;
487 allocno
[num
].size
= PSEUDO_REGNO_SIZE (i
);
488 allocno
[num
].calls_crossed
+= REG_N_CALLS_CROSSED (i
);
489 allocno
[num
].n_refs
+= REG_N_REFS (i
);
490 allocno
[num
].freq
+= REG_FREQ (i
);
491 if (allocno
[num
].live_length
< REG_LIVE_LENGTH (i
))
492 allocno
[num
].live_length
= REG_LIVE_LENGTH (i
);
495 /* Calculate amount of usage of each hard reg by pseudos
496 allocated by local-alloc. This is to see if we want to
498 memset (local_reg_live_length
, 0, sizeof local_reg_live_length
);
499 memset (local_reg_n_refs
, 0, sizeof local_reg_n_refs
);
500 memset (local_reg_freq
, 0, sizeof local_reg_freq
);
501 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
502 if (reg_renumber
[i
] >= 0)
504 int regno
= reg_renumber
[i
];
505 int endregno
= regno
+ hard_regno_nregs
[regno
][PSEUDO_REGNO_MODE (i
)];
508 for (j
= regno
; j
< endregno
; j
++)
510 local_reg_n_refs
[j
] += REG_N_REFS (i
);
511 local_reg_freq
[j
] += REG_FREQ (i
);
512 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
516 /* We can't override local-alloc for a reg used not just by local-alloc. */
517 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
518 if (regs_ever_live
[i
])
519 local_reg_n_refs
[i
] = 0, local_reg_freq
[i
] = 0;
521 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
523 /* We used to use alloca here, but the size of what it would try to
524 allocate would occasionally cause it to exceed the stack limit and
525 cause unpredictable core dumps. Some examples were > 2Mb in size. */
526 conflicts
= xcalloc (max_allocno
* allocno_row_words
, sizeof (INT_TYPE
));
528 allocnos_live
= xmalloc (allocno_row_words
* sizeof (INT_TYPE
));
530 /* If there is work to be done (at least one reg to allocate),
531 perform global conflict analysis and allocate the regs. */
535 /* Scan all the insns and compute the conflicts among allocnos
536 and between allocnos and hard regs. */
542 /* Eliminate conflicts between pseudos and eliminable registers. If
543 the register is not eliminated, the pseudo won't really be able to
544 live in the eliminable register, so the conflict doesn't matter.
545 If we do eliminate the register, the conflict will no longer exist.
546 So in either case, we can ignore the conflict. Likewise for
549 for (i
= 0; i
< (size_t) max_allocno
; i
++)
551 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_conflicts
,
553 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_copy_preferences
,
555 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_preferences
,
559 /* Try to expand the preferences by merging them between allocnos. */
561 expand_preferences ();
563 /* Determine the order to allocate the remaining pseudo registers. */
565 allocno_order
= xmalloc (max_allocno
* sizeof (int));
566 for (i
= 0; i
< (size_t) max_allocno
; i
++)
567 allocno_order
[i
] = i
;
569 /* Default the size to 1, since allocno_compare uses it to divide by.
570 Also convert allocno_live_length of zero to -1. A length of zero
571 can occur when all the registers for that allocno have reg_live_length
572 equal to -2. In this case, we want to make an allocno, but not
573 allocate it. So avoid the divide-by-zero and set it to a low
576 for (i
= 0; i
< (size_t) max_allocno
; i
++)
578 if (allocno
[i
].size
== 0)
580 if (allocno
[i
].live_length
== 0)
581 allocno
[i
].live_length
= -1;
584 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
586 prune_preferences ();
589 dump_conflicts (file
);
591 /* Try allocating them, one by one, in that order,
592 except for parameters marked with reg_live_length[regno] == -2. */
594 for (i
= 0; i
< (size_t) max_allocno
; i
++)
595 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] < 0
596 && REG_LIVE_LENGTH (allocno
[allocno_order
[i
]].reg
) >= 0)
598 /* If we have more than one register class,
599 first try allocating in the class that is cheapest
600 for this pseudo-reg. If that fails, try any reg. */
601 if (N_REG_CLASSES
> 1)
603 find_reg (allocno_order
[i
], 0, 0, 0, 0);
604 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
607 if (reg_alternate_class (allocno
[allocno_order
[i
]].reg
) != NO_REGS
)
608 find_reg (allocno_order
[i
], 0, 1, 0, 0);
611 free (allocno_order
);
614 /* Do the reloads now while the allocno data still exist, so that we can
615 try to assign new hard regs to any pseudo regs that are spilled. */
617 #if 0 /* We need to eliminate regs even if there is no rtl code,
618 for the sake of debugging information. */
619 if (n_basic_blocks
> 0)
622 build_insn_chain (get_insns ());
623 retval
= reload (get_insns (), 1);
628 free (reg_may_share
);
631 free (allocnos_live
);
636 /* Sort predicate for ordering the allocnos.
637 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
640 allocno_compare (const void *v1p
, const void *v2p
)
642 int v1
= *(const int *)v1p
, v2
= *(const int *)v2p
;
643 /* Note that the quotient will never be bigger than
644 the value of floor_log2 times the maximum number of
645 times a register can occur in one insn (surely less than 100)
646 weighted by the frequency (maximally REG_FREQ_MAX).
647 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
649 = (((double) (floor_log2 (allocno
[v1
].n_refs
) * allocno
[v1
].freq
)
650 / allocno
[v1
].live_length
)
651 * (10000 / REG_FREQ_MAX
) * allocno
[v1
].size
);
653 = (((double) (floor_log2 (allocno
[v2
].n_refs
) * allocno
[v2
].freq
)
654 / allocno
[v2
].live_length
)
655 * (10000 / REG_FREQ_MAX
) * allocno
[v2
].size
);
659 /* If regs are equally good, sort by allocno,
660 so that the results of qsort leave nothing to chance. */
664 /* Scan the rtl code and record all conflicts and register preferences in the
665 conflict matrices and preference tables. */
668 global_conflicts (void)
673 int *block_start_allocnos
;
675 /* Make a vector that mark_reg_{store,clobber} will store in. */
676 regs_set
= xmalloc (max_parallel
* sizeof (rtx
) * 2);
678 block_start_allocnos
= xmalloc (max_allocno
* sizeof (int));
682 memset (allocnos_live
, 0, allocno_row_words
* sizeof (INT_TYPE
));
684 /* Initialize table of registers currently live
685 to the state at the beginning of this basic block.
686 This also marks the conflicts among hard registers
687 and any allocnos that are live.
689 For pseudo-regs, there is only one bit for each one
690 no matter how many hard regs it occupies.
691 This is ok; we know the size from PSEUDO_REGNO_SIZE.
692 For explicit hard regs, we cannot know the size that way
693 since one hard reg can be used with various sizes.
694 Therefore, we must require that all the hard regs
695 implicitly live as part of a multi-word hard reg
696 be explicitly marked in basic_block_live_at_start. */
699 regset old
= b
->il
.rtl
->global_live_at_start
;
701 reg_set_iterator rsi
;
703 REG_SET_TO_HARD_REG_SET (hard_regs_live
, old
);
704 EXECUTE_IF_SET_IN_REG_SET (old
, FIRST_PSEUDO_REGISTER
, i
, rsi
)
706 int a
= reg_allocno
[i
];
709 SET_ALLOCNO_LIVE (a
);
710 block_start_allocnos
[ax
++] = a
;
712 else if ((a
= reg_renumber
[i
]) >= 0)
713 mark_reg_live_nc (a
, PSEUDO_REGNO_MODE (i
));
716 /* Record that each allocno now live conflicts with each hard reg
719 It is not necessary to mark any conflicts between pseudos as
720 this point, even for pseudos which are live at the start of
723 Given two pseudos X and Y and any point in the CFG P.
725 On any path to point P where X and Y are live one of the
726 following conditions must be true:
728 1. X is live at some instruction on the path that
731 2. Y is live at some instruction on the path that
734 3. Either X or Y is not evaluated on the path to P
735 (i.e. it is used uninitialized) and thus the
736 conflict can be ignored.
738 In cases #1 and #2 the conflict will be recorded when we
739 scan the instruction that makes either X or Y become live. */
740 record_conflicts (block_start_allocnos
, ax
);
742 /* Pseudos can't go in stack regs at the start of a basic block that
743 is reached by an abnormal edge. Likewise for call clobbered regs,
744 because because caller-save, fixup_abnormal_edges, and possibly
745 the table driven EH machinery are not quite ready to handle such
746 regs live across such edges. */
751 FOR_EACH_EDGE (e
, ei
, b
->preds
)
752 if (e
->flags
& EDGE_ABNORMAL
)
758 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, ax
,
760 allocno
[ax
].no_stack_reg
= 1;
762 for (ax
= FIRST_STACK_REG
; ax
<= LAST_STACK_REG
; ax
++)
763 record_one_conflict (ax
);
766 /* No need to record conflicts for call clobbered regs if we have
767 nonlocal labels around, as we don't ever try to allocate such
768 regs in this case. */
769 if (! current_function_has_nonlocal_label
)
770 for (ax
= 0; ax
< FIRST_PSEUDO_REGISTER
; ax
++)
771 if (call_used_regs
[ax
])
772 record_one_conflict (ax
);
779 /* Scan the code of this basic block, noting which allocnos
780 and hard regs are born or die. When one is born,
781 record a conflict with all others currently live. */
785 RTX_CODE code
= GET_CODE (insn
);
788 /* Make regs_set an empty set. */
792 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
797 for (link
= REG_NOTES (insn
);
798 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
799 link
= XEXP (link
, 1))
800 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
802 no_conflict_pairs
[i
].allocno1
803 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
804 no_conflict_pairs
[i
].allocno2
805 = reg_allocno
[REGNO (XEXP (link
, 0))];
810 /* Mark any registers clobbered by INSN as live,
811 so they conflict with the inputs. */
813 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
815 /* Mark any registers dead after INSN as dead now. */
817 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
818 if (REG_NOTE_KIND (link
) == REG_DEAD
)
819 mark_reg_death (XEXP (link
, 0));
821 /* Mark any registers set in INSN as live,
822 and mark them as conflicting with all other live regs.
823 Clobbers are processed again, so they conflict with
824 the registers that are set. */
826 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
829 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
830 if (REG_NOTE_KIND (link
) == REG_INC
)
831 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
834 /* If INSN has multiple outputs, then any reg that dies here
835 and is used inside of an output
836 must conflict with the other outputs.
838 It is unsafe to use !single_set here since it will ignore an
839 unused output. Just because an output is unused does not mean
840 the compiler can assume the side effect will not occur.
841 Consider if REG appears in the address of an output and we
842 reload the output. If we allocate REG to the same hard
843 register as an unused output we could set the hard register
844 before the output reload insn. */
845 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
846 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
847 if (REG_NOTE_KIND (link
) == REG_DEAD
)
849 int used_in_output
= 0;
851 rtx reg
= XEXP (link
, 0);
853 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
855 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
856 if (GET_CODE (set
) == SET
857 && !REG_P (SET_DEST (set
))
858 && !rtx_equal_p (reg
, SET_DEST (set
))
859 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
863 mark_reg_conflicts (reg
);
866 /* Mark any registers set in INSN and then never used. */
868 while (n_regs_set
-- > 0)
870 rtx note
= find_regno_note (insn
, REG_UNUSED
,
871 REGNO (regs_set
[n_regs_set
]));
873 mark_reg_death (XEXP (note
, 0));
877 if (insn
== BB_END (b
))
879 insn
= NEXT_INSN (insn
);
884 free (block_start_allocnos
);
887 /* Expand the preference information by looking for cases where one allocno
888 dies in an insn that sets an allocno. If those two allocnos don't conflict,
889 merge any preferences between those allocnos. */
892 expand_preferences (void)
898 /* We only try to handle the most common cases here. Most of the cases
899 where this wins are reg-reg copies. */
901 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
903 && (set
= single_set (insn
)) != 0
904 && REG_P (SET_DEST (set
))
905 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
906 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
907 if (REG_NOTE_KIND (link
) == REG_DEAD
908 && REG_P (XEXP (link
, 0))
909 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
910 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
911 reg_allocno
[REGNO (XEXP (link
, 0))]))
913 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
914 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
916 if (XEXP (link
, 0) == SET_SRC (set
))
918 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_copy_preferences
,
919 allocno
[a2
].hard_reg_copy_preferences
);
920 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_copy_preferences
,
921 allocno
[a1
].hard_reg_copy_preferences
);
924 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_preferences
,
925 allocno
[a2
].hard_reg_preferences
);
926 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_preferences
,
927 allocno
[a1
].hard_reg_preferences
);
928 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_full_preferences
,
929 allocno
[a2
].hard_reg_full_preferences
);
930 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_full_preferences
,
931 allocno
[a1
].hard_reg_full_preferences
);
935 /* Prune the preferences for global registers to exclude registers that cannot
938 Compute `regs_someone_prefers', which is a bitmask of the hard registers
939 that are preferred by conflicting registers of lower priority. If possible,
940 we will avoid using these registers. */
943 prune_preferences (void)
947 int *allocno_to_order
= xmalloc (max_allocno
* sizeof (int));
949 /* Scan least most important to most important.
950 For each allocno, remove from preferences registers that cannot be used,
951 either because of conflicts or register type. Then compute all registers
952 preferred by each lower-priority register that conflicts. */
954 for (i
= max_allocno
- 1; i
>= 0; i
--)
958 num
= allocno_order
[i
];
959 allocno_to_order
[num
] = i
;
960 COPY_HARD_REG_SET (temp
, allocno
[num
].hard_reg_conflicts
);
962 if (allocno
[num
].calls_crossed
== 0)
963 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
965 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
967 IOR_COMPL_HARD_REG_SET
969 reg_class_contents
[(int) reg_preferred_class (allocno
[num
].reg
)]);
971 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, temp
);
972 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, temp
);
973 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_full_preferences
, temp
);
976 for (i
= max_allocno
- 1; i
>= 0; i
--)
978 /* Merge in the preferences of lower-priority registers (they have
979 already been pruned). If we also prefer some of those registers,
980 don't exclude them unless we are of a smaller size (in which case
981 we want to give the lower-priority allocno the first chance for
983 HARD_REG_SET temp
, temp2
;
986 num
= allocno_order
[i
];
988 CLEAR_HARD_REG_SET (temp
);
989 CLEAR_HARD_REG_SET (temp2
);
991 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ num
* allocno_row_words
,
994 if (allocno_to_order
[allocno2
] > i
)
996 if (allocno
[allocno2
].size
<= allocno
[num
].size
)
997 IOR_HARD_REG_SET (temp
,
998 allocno
[allocno2
].hard_reg_full_preferences
);
1000 IOR_HARD_REG_SET (temp2
,
1001 allocno
[allocno2
].hard_reg_full_preferences
);
1005 AND_COMPL_HARD_REG_SET (temp
, allocno
[num
].hard_reg_full_preferences
);
1006 IOR_HARD_REG_SET (temp
, temp2
);
1007 COPY_HARD_REG_SET (allocno
[num
].regs_someone_prefers
, temp
);
1009 free (allocno_to_order
);
1012 /* Assign a hard register to allocno NUM; look for one that is the beginning
1013 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
1014 The registers marked in PREFREGS are tried first.
1016 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
1017 be used for this allocation.
1019 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
1020 Otherwise ignore that preferred class and use the alternate class.
1022 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
1023 will have to be saved and restored at calls.
1025 RETRYING is nonzero if this is called from retry_global_alloc.
1027 If we find one, record it in reg_renumber.
1028 If not, do nothing. */
1031 find_reg (int num
, HARD_REG_SET losers
, int alt_regs_p
, int accept_call_clobbered
, int retrying
)
1033 int i
, best_reg
, pass
;
1034 HARD_REG_SET used
, used1
, used2
;
1036 enum reg_class
class = (alt_regs_p
1037 ? reg_alternate_class (allocno
[num
].reg
)
1038 : reg_preferred_class (allocno
[num
].reg
));
1039 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno
[num
].reg
);
1041 if (accept_call_clobbered
)
1042 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
1043 else if (allocno
[num
].calls_crossed
== 0)
1044 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
1046 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
1048 /* Some registers should not be allocated in global-alloc. */
1049 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
1051 IOR_HARD_REG_SET (used1
, losers
);
1053 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
1054 COPY_HARD_REG_SET (used2
, used1
);
1056 IOR_HARD_REG_SET (used1
, allocno
[num
].hard_reg_conflicts
);
1058 #ifdef CANNOT_CHANGE_MODE_CLASS
1059 cannot_change_mode_set_regs (&used1
, mode
, allocno
[num
].reg
);
1062 /* Try each hard reg to see if it fits. Do this in two passes.
1063 In the first pass, skip registers that are preferred by some other pseudo
1064 to give it a better chance of getting one of those registers. Only if
1065 we can't get a register when excluding those do we take one of them.
1066 However, we never allocate a register for the first time in pass 0. */
1068 COPY_HARD_REG_SET (used
, used1
);
1069 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
1070 IOR_HARD_REG_SET (used
, allocno
[num
].regs_someone_prefers
);
1073 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
1074 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
1078 COPY_HARD_REG_SET (used
, used1
);
1079 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1081 #ifdef REG_ALLOC_ORDER
1082 int regno
= reg_alloc_order
[i
];
1086 if (! TEST_HARD_REG_BIT (used
, regno
)
1087 && HARD_REGNO_MODE_OK (regno
, mode
)
1088 && (allocno
[num
].calls_crossed
== 0
1089 || accept_call_clobbered
1090 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
)))
1093 int lim
= regno
+ hard_regno_nregs
[regno
][mode
];
1096 && ! TEST_HARD_REG_BIT (used
, j
));
1103 #ifndef REG_ALLOC_ORDER
1104 i
= j
; /* Skip starting points we know will lose */
1110 /* See if there is a preferred register with the same class as the register
1111 we allocated above. Making this restriction prevents register
1112 preferencing from creating worse register allocation.
1114 Remove from the preferred registers and conflicting registers. Note that
1115 additional conflicts may have been added after `prune_preferences' was
1118 First do this for those register with copy preferences, then all
1119 preferred registers. */
1121 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, used
);
1122 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_copy_preferences
,
1123 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
1127 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1128 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_copy_preferences
, i
)
1129 && HARD_REGNO_MODE_OK (i
, mode
)
1130 && (allocno
[num
].calls_crossed
== 0
1131 || accept_call_clobbered
1132 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1133 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1134 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1135 REGNO_REG_CLASS (best_reg
))
1136 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1137 REGNO_REG_CLASS (i
))))
1140 int lim
= i
+ hard_regno_nregs
[i
][mode
];
1143 && ! TEST_HARD_REG_BIT (used
, j
)
1144 && (REGNO_REG_CLASS (j
)
1145 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1146 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1147 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1148 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1149 REGNO_REG_CLASS (j
))));
1160 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, used
);
1161 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_preferences
,
1162 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1166 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1167 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_preferences
, i
)
1168 && HARD_REGNO_MODE_OK (i
, mode
)
1169 && (allocno
[num
].calls_crossed
== 0
1170 || accept_call_clobbered
1171 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1172 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1173 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1174 REGNO_REG_CLASS (best_reg
))
1175 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1176 REGNO_REG_CLASS (i
))))
1179 int lim
= i
+ hard_regno_nregs
[i
][mode
];
1182 && ! TEST_HARD_REG_BIT (used
, j
)
1183 && (REGNO_REG_CLASS (j
)
1184 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1185 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1186 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1187 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1188 REGNO_REG_CLASS (j
))));
1199 /* If we haven't succeeded yet, try with caller-saves.
1200 We need not check to see if the current function has nonlocal
1201 labels because we don't put any pseudos that are live over calls in
1202 registers in that case. */
1204 if (flag_caller_saves
&& best_reg
< 0)
1206 /* Did not find a register. If it would be profitable to
1207 allocate a call-clobbered register and save and restore it
1208 around calls, do that. */
1209 if (! accept_call_clobbered
1210 && allocno
[num
].calls_crossed
!= 0
1211 && CALLER_SAVE_PROFITABLE (allocno
[num
].n_refs
,
1212 allocno
[num
].calls_crossed
))
1214 HARD_REG_SET new_losers
;
1216 CLEAR_HARD_REG_SET (new_losers
);
1218 COPY_HARD_REG_SET (new_losers
, losers
);
1220 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1221 find_reg (num
, new_losers
, alt_regs_p
, 1, retrying
);
1222 if (reg_renumber
[allocno
[num
].reg
] >= 0)
1224 caller_save_needed
= 1;
1230 /* If we haven't succeeded yet,
1231 see if some hard reg that conflicts with us
1232 was utilized poorly by local-alloc.
1233 If so, kick out the regs that were put there by local-alloc
1234 so we can use it instead. */
1235 if (best_reg
< 0 && !retrying
1236 /* Let's not bother with multi-reg allocnos. */
1237 && allocno
[num
].size
== 1)
1239 /* Count from the end, to find the least-used ones first. */
1240 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1242 #ifdef REG_ALLOC_ORDER
1243 int regno
= reg_alloc_order
[i
];
1248 if (local_reg_n_refs
[regno
] != 0
1249 /* Don't use a reg no good for this pseudo. */
1250 && ! TEST_HARD_REG_BIT (used2
, regno
)
1251 && HARD_REGNO_MODE_OK (regno
, mode
)
1252 /* The code below assumes that we need only a single
1253 register, but the check of allocno[num].size above
1254 was not enough. Sometimes we need more than one
1255 register for a single-word value. */
1256 && hard_regno_nregs
[regno
][mode
] == 1
1257 && (allocno
[num
].calls_crossed
== 0
1258 || accept_call_clobbered
1259 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
))
1260 #ifdef CANNOT_CHANGE_MODE_CLASS
1261 && ! invalid_mode_change_p (regno
, REGNO_REG_CLASS (regno
),
1265 && (!allocno
[num
].no_stack_reg
1266 || regno
< FIRST_STACK_REG
|| regno
> LAST_STACK_REG
)
1270 /* We explicitly evaluate the divide results into temporary
1271 variables so as to avoid excess precision problems that occur
1272 on an i386-unknown-sysv4.2 (unixware) host. */
1274 double tmp1
= ((double) local_reg_freq
[regno
]
1275 / local_reg_live_length
[regno
]);
1276 double tmp2
= ((double) allocno
[num
].freq
1277 / allocno
[num
].live_length
);
1281 /* Hard reg REGNO was used less in total by local regs
1282 than it would be used by this one allocno! */
1284 for (k
= 0; k
< max_regno
; k
++)
1285 if (reg_renumber
[k
] >= 0)
1287 int r
= reg_renumber
[k
];
1289 = r
+ hard_regno_nregs
[r
][PSEUDO_REGNO_MODE (k
)];
1291 if (regno
>= r
&& regno
< endregno
)
1292 reg_renumber
[k
] = -1;
1302 /* Did we find a register? */
1307 HARD_REG_SET this_reg
;
1309 /* Yes. Record it as the hard register of this pseudo-reg. */
1310 reg_renumber
[allocno
[num
].reg
] = best_reg
;
1311 /* Also of any pseudo-regs that share with it. */
1312 if (reg_may_share
[allocno
[num
].reg
])
1313 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1314 if (reg_allocno
[j
] == num
)
1315 reg_renumber
[j
] = best_reg
;
1317 /* Make a set of the hard regs being allocated. */
1318 CLEAR_HARD_REG_SET (this_reg
);
1319 lim
= best_reg
+ hard_regno_nregs
[best_reg
][mode
];
1320 for (j
= best_reg
; j
< lim
; j
++)
1322 SET_HARD_REG_BIT (this_reg
, j
);
1323 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1324 /* This is no longer a reg used just by local regs. */
1325 local_reg_n_refs
[j
] = 0;
1326 local_reg_freq
[j
] = 0;
1328 /* For each other pseudo-reg conflicting with this one,
1329 mark it as conflicting with the hard regs this one occupies. */
1331 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ lim
* allocno_row_words
, j
,
1333 IOR_HARD_REG_SET (allocno
[j
].hard_reg_conflicts
, this_reg
);
1338 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1339 Perhaps it had previously seemed not worth a hard reg,
1340 or perhaps its old hard reg has been commandeered for reloads.
1341 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1342 they do not appear to be allocated.
1343 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1346 retry_global_alloc (int regno
, HARD_REG_SET forbidden_regs
)
1348 int alloc_no
= reg_allocno
[regno
];
1351 /* If we have more than one register class,
1352 first try allocating in the class that is cheapest
1353 for this pseudo-reg. If that fails, try any reg. */
1354 if (N_REG_CLASSES
> 1)
1355 find_reg (alloc_no
, forbidden_regs
, 0, 0, 1);
1356 if (reg_renumber
[regno
] < 0
1357 && reg_alternate_class (regno
) != NO_REGS
)
1358 find_reg (alloc_no
, forbidden_regs
, 1, 0, 1);
1360 /* If we found a register, modify the RTL for the register to
1361 show the hard register, and mark that register live. */
1362 if (reg_renumber
[regno
] >= 0)
1364 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1365 mark_home_live (regno
);
1370 /* Record a conflict between register REGNO
1371 and everything currently live.
1372 REGNO must not be a pseudo reg that was allocated
1373 by local_alloc; such numbers must be translated through
1374 reg_renumber before calling here. */
1377 record_one_conflict (int regno
)
1381 if (regno
< FIRST_PSEUDO_REGISTER
)
1382 /* When a hard register becomes live,
1383 record conflicts with live pseudo regs. */
1384 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, j
,
1386 SET_HARD_REG_BIT (allocno
[j
].hard_reg_conflicts
, regno
);
1389 /* When a pseudo-register becomes live,
1390 record conflicts first with hard regs,
1391 then with other pseudo regs. */
1393 int ialloc
= reg_allocno
[regno
];
1394 int ialloc_prod
= ialloc
* allocno_row_words
;
1396 IOR_HARD_REG_SET (allocno
[ialloc
].hard_reg_conflicts
, hard_regs_live
);
1397 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1398 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1402 /* Record all allocnos currently live as conflicting
1403 with all hard regs currently live.
1405 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1406 are currently live. Their bits are also flagged in allocnos_live. */
1409 record_conflicts (int *allocno_vec
, int len
)
1412 IOR_HARD_REG_SET (allocno
[allocno_vec
[len
]].hard_reg_conflicts
,
1416 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1418 mirror_conflicts (void)
1421 int rw
= allocno_row_words
;
1422 int rwb
= rw
* INT_BITS
;
1423 INT_TYPE
*p
= conflicts
;
1424 INT_TYPE
*q0
= conflicts
, *q1
, *q2
;
1425 unsigned INT_TYPE mask
;
1427 for (i
= max_allocno
- 1, mask
= 1; i
>= 0; i
--, mask
<<= 1)
1434 for (j
= allocno_row_words
- 1, q1
= q0
; j
>= 0; j
--, q1
+= rwb
)
1436 unsigned INT_TYPE word
;
1438 for (word
= (unsigned INT_TYPE
) *p
++, q2
= q1
; word
;
1439 word
>>= 1, q2
+= rw
)
1448 /* Handle the case where REG is set by the insn being scanned,
1449 during the forward scan to accumulate conflicts.
1450 Store a 1 in regs_live or allocnos_live for this register, record how many
1451 consecutive hardware registers it actually needs,
1452 and record a conflict with all other registers already live.
1454 Note that even if REG does not remain alive after this insn,
1455 we must mark it here as live, to ensure a conflict between
1456 REG and any other regs set in this insn that really do live.
1457 This is because those other regs could be considered after this.
1459 REG might actually be something other than a register;
1460 if so, we do nothing.
1462 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1463 a REG_INC note was found for it). */
1466 mark_reg_store (rtx reg
, rtx setter
, void *data ATTRIBUTE_UNUSED
)
1470 if (GET_CODE (reg
) == SUBREG
)
1471 reg
= SUBREG_REG (reg
);
1476 regs_set
[n_regs_set
++] = reg
;
1478 if (setter
&& GET_CODE (setter
) != CLOBBER
)
1479 set_preference (reg
, SET_SRC (setter
));
1481 regno
= REGNO (reg
);
1483 /* Either this is one of the max_allocno pseudo regs not allocated,
1484 or it is or has a hardware reg. First handle the pseudo-regs. */
1485 if (regno
>= FIRST_PSEUDO_REGISTER
)
1487 if (reg_allocno
[regno
] >= 0)
1489 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1490 record_one_conflict (regno
);
1494 if (reg_renumber
[regno
] >= 0)
1495 regno
= reg_renumber
[regno
];
1497 /* Handle hardware regs (and pseudos allocated to hard regs). */
1498 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1500 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1501 while (regno
< last
)
1503 record_one_conflict (regno
);
1504 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1510 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1513 mark_reg_clobber (rtx reg
, rtx setter
, void *data
)
1515 if (GET_CODE (setter
) == CLOBBER
)
1516 mark_reg_store (reg
, setter
, data
);
1519 /* Record that REG has conflicts with all the regs currently live.
1520 Do not mark REG itself as live. */
1523 mark_reg_conflicts (rtx reg
)
1527 if (GET_CODE (reg
) == SUBREG
)
1528 reg
= SUBREG_REG (reg
);
1533 regno
= REGNO (reg
);
1535 /* Either this is one of the max_allocno pseudo regs not allocated,
1536 or it is or has a hardware reg. First handle the pseudo-regs. */
1537 if (regno
>= FIRST_PSEUDO_REGISTER
)
1539 if (reg_allocno
[regno
] >= 0)
1540 record_one_conflict (regno
);
1543 if (reg_renumber
[regno
] >= 0)
1544 regno
= reg_renumber
[regno
];
1546 /* Handle hardware regs (and pseudos allocated to hard regs). */
1547 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1549 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1550 while (regno
< last
)
1552 record_one_conflict (regno
);
1558 /* Mark REG as being dead (following the insn being scanned now).
1559 Store a 0 in regs_live or allocnos_live for this register. */
1562 mark_reg_death (rtx reg
)
1564 int regno
= REGNO (reg
);
1566 /* Either this is one of the max_allocno pseudo regs not allocated,
1567 or it is a hardware reg. First handle the pseudo-regs. */
1568 if (regno
>= FIRST_PSEUDO_REGISTER
)
1570 if (reg_allocno
[regno
] >= 0)
1571 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1574 /* For pseudo reg, see if it has been assigned a hardware reg. */
1575 if (reg_renumber
[regno
] >= 0)
1576 regno
= reg_renumber
[regno
];
1578 /* Handle hardware regs (and pseudos allocated to hard regs). */
1579 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1581 /* Pseudo regs already assigned hardware regs are treated
1582 almost the same as explicit hardware regs. */
1583 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1584 while (regno
< last
)
1586 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1592 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1593 for the value stored in it. MODE determines how many consecutive
1594 registers are actually in use. Do not record conflicts;
1595 it is assumed that the caller will do that. */
1598 mark_reg_live_nc (int regno
, enum machine_mode mode
)
1600 int last
= regno
+ hard_regno_nregs
[regno
][mode
];
1601 while (regno
< last
)
1603 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1608 /* Try to set a preference for an allocno to a hard register.
1609 We are passed DEST and SRC which are the operands of a SET. It is known
1610 that SRC is a register. If SRC or the first operand of SRC is a register,
1611 try to set a preference. If one of the two is a hard register and the other
1612 is a pseudo-register, mark the preference.
1614 Note that we are not as aggressive as local-alloc in trying to tie a
1615 pseudo-register to a hard register. */
1618 set_preference (rtx dest
, rtx src
)
1620 unsigned int src_regno
, dest_regno
;
1621 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1622 to compensate for subregs in SRC or DEST. */
1627 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1628 src
= XEXP (src
, 0), copy
= 0;
1630 /* Get the reg number for both SRC and DEST.
1631 If neither is a reg, give up. */
1634 src_regno
= REGNO (src
);
1635 else if (GET_CODE (src
) == SUBREG
&& REG_P (SUBREG_REG (src
)))
1637 src_regno
= REGNO (SUBREG_REG (src
));
1639 if (REGNO (SUBREG_REG (src
)) < FIRST_PSEUDO_REGISTER
)
1640 offset
+= subreg_regno_offset (REGNO (SUBREG_REG (src
)),
1641 GET_MODE (SUBREG_REG (src
)),
1645 offset
+= (SUBREG_BYTE (src
)
1646 / REGMODE_NATURAL_SIZE (GET_MODE (src
)));
1652 dest_regno
= REGNO (dest
);
1653 else if (GET_CODE (dest
) == SUBREG
&& REG_P (SUBREG_REG (dest
)))
1655 dest_regno
= REGNO (SUBREG_REG (dest
));
1657 if (REGNO (SUBREG_REG (dest
)) < FIRST_PSEUDO_REGISTER
)
1658 offset
-= subreg_regno_offset (REGNO (SUBREG_REG (dest
)),
1659 GET_MODE (SUBREG_REG (dest
)),
1663 offset
-= (SUBREG_BYTE (dest
)
1664 / REGMODE_NATURAL_SIZE (GET_MODE (dest
)));
1669 /* Convert either or both to hard reg numbers. */
1671 if (reg_renumber
[src_regno
] >= 0)
1672 src_regno
= reg_renumber
[src_regno
];
1674 if (reg_renumber
[dest_regno
] >= 0)
1675 dest_regno
= reg_renumber
[dest_regno
];
1677 /* Now if one is a hard reg and the other is a global pseudo
1678 then give the other a preference. */
1680 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1681 && reg_allocno
[src_regno
] >= 0)
1683 dest_regno
-= offset
;
1684 if (dest_regno
< FIRST_PSEUDO_REGISTER
)
1687 SET_REGBIT (hard_reg_copy_preferences
,
1688 reg_allocno
[src_regno
], dest_regno
);
1690 SET_REGBIT (hard_reg_preferences
,
1691 reg_allocno
[src_regno
], dest_regno
);
1692 for (i
= dest_regno
;
1693 i
< dest_regno
+ hard_regno_nregs
[dest_regno
][GET_MODE (dest
)];
1695 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1699 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1700 && reg_allocno
[dest_regno
] >= 0)
1702 src_regno
+= offset
;
1703 if (src_regno
< FIRST_PSEUDO_REGISTER
)
1706 SET_REGBIT (hard_reg_copy_preferences
,
1707 reg_allocno
[dest_regno
], src_regno
);
1709 SET_REGBIT (hard_reg_preferences
,
1710 reg_allocno
[dest_regno
], src_regno
);
1712 i
< src_regno
+ hard_regno_nregs
[src_regno
][GET_MODE (src
)];
1714 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1719 /* Indicate that hard register number FROM was eliminated and replaced with
1720 an offset from hard register number TO. The status of hard registers live
1721 at the start of a basic block is updated by replacing a use of FROM with
1725 mark_elimination (int from
, int to
)
1731 regset r
= bb
->il
.rtl
->global_live_at_start
;
1732 if (REGNO_REG_SET_P (r
, from
))
1734 CLEAR_REGNO_REG_SET (r
, from
);
1735 SET_REGNO_REG_SET (r
, to
);
1740 /* Used for communication between the following functions. Holds the
1741 current life information. */
1742 static regset live_relevant_regs
;
1744 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1745 This is called via note_stores. */
1747 reg_becomes_live (rtx reg
, rtx setter ATTRIBUTE_UNUSED
, void *regs_set
)
1751 if (GET_CODE (reg
) == SUBREG
)
1752 reg
= SUBREG_REG (reg
);
1757 regno
= REGNO (reg
);
1758 if (regno
< FIRST_PSEUDO_REGISTER
)
1760 int nregs
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1763 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1764 if (! fixed_regs
[regno
])
1765 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1769 else if (reg_renumber
[regno
] >= 0)
1771 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1772 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1776 /* Record in live_relevant_regs that register REGNO died. */
1778 reg_dies (int regno
, enum machine_mode mode
, struct insn_chain
*chain
)
1780 if (regno
< FIRST_PSEUDO_REGISTER
)
1782 int nregs
= hard_regno_nregs
[regno
][mode
];
1785 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1786 if (! fixed_regs
[regno
])
1787 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1793 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1794 if (reg_renumber
[regno
] >= 0)
1795 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1799 /* Walk the insns of the current function and build reload_insn_chain,
1800 and record register life information. */
1802 build_insn_chain (rtx first
)
1804 struct insn_chain
**p
= &reload_insn_chain
;
1805 struct insn_chain
*prev
= 0;
1806 basic_block b
= ENTRY_BLOCK_PTR
->next_bb
;
1808 live_relevant_regs
= ALLOC_REG_SET (®_obstack
);
1810 for (; first
; first
= NEXT_INSN (first
))
1812 struct insn_chain
*c
;
1814 if (first
== BB_HEAD (b
))
1819 CLEAR_REG_SET (live_relevant_regs
);
1821 EXECUTE_IF_SET_IN_BITMAP (b
->il
.rtl
->global_live_at_start
, 0, i
, bi
)
1823 if (i
< FIRST_PSEUDO_REGISTER
1824 ? ! TEST_HARD_REG_BIT (eliminable_regset
, i
)
1825 : reg_renumber
[i
] >= 0)
1826 SET_REGNO_REG_SET (live_relevant_regs
, i
);
1830 if (!NOTE_P (first
) && !BARRIER_P (first
))
1832 c
= new_insn_chain ();
1838 c
->block
= b
->index
;
1844 /* Mark the death of everything that dies in this instruction. */
1846 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1847 if (REG_NOTE_KIND (link
) == REG_DEAD
1848 && REG_P (XEXP (link
, 0)))
1849 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1852 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1854 /* Mark everything born in this instruction as live. */
1856 note_stores (PATTERN (first
), reg_becomes_live
,
1860 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1866 /* Mark anything that is set in this insn and then unused as dying. */
1868 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1869 if (REG_NOTE_KIND (link
) == REG_UNUSED
1870 && REG_P (XEXP (link
, 0)))
1871 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1876 if (first
== BB_END (b
))
1879 /* Stop after we pass the end of the last basic block. Verify that
1880 no real insns are after the end of the last basic block.
1882 We may want to reorganize the loop somewhat since this test should
1883 always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if
1884 the previous real insn is a JUMP_INSN. */
1885 if (b
== EXIT_BLOCK_PTR
)
1887 #ifdef ENABLE_CHECKING
1888 for (first
= NEXT_INSN (first
); first
; first
= NEXT_INSN (first
))
1889 gcc_assert (!INSN_P (first
)
1890 || GET_CODE (PATTERN (first
)) == USE
1891 || ((GET_CODE (PATTERN (first
)) == ADDR_VEC
1892 || GET_CODE (PATTERN (first
)) == ADDR_DIFF_VEC
)
1893 && prev_real_insn (first
) != 0
1894 && JUMP_P (prev_real_insn (first
))));
1899 FREE_REG_SET (live_relevant_regs
);
1903 /* Print debugging trace information if -dg switch is given,
1904 showing the information on which the allocation decisions are based. */
1907 dump_conflicts (FILE *file
)
1910 int has_preferences
;
1913 for (i
= 0; i
< max_allocno
; i
++)
1915 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1919 fprintf (file
, ";; %d regs to allocate:", nregs
);
1920 for (i
= 0; i
< max_allocno
; i
++)
1923 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1925 fprintf (file
, " %d", allocno
[allocno_order
[i
]].reg
);
1926 for (j
= 0; j
< max_regno
; j
++)
1927 if (reg_allocno
[j
] == allocno_order
[i
]
1928 && j
!= allocno
[allocno_order
[i
]].reg
)
1929 fprintf (file
, "+%d", j
);
1930 if (allocno
[allocno_order
[i
]].size
!= 1)
1931 fprintf (file
, " (%d)", allocno
[allocno_order
[i
]].size
);
1933 fprintf (file
, "\n");
1935 for (i
= 0; i
< max_allocno
; i
++)
1938 fprintf (file
, ";; %d conflicts:", allocno
[i
].reg
);
1939 for (j
= 0; j
< max_allocno
; j
++)
1940 if (CONFLICTP (j
, i
))
1941 fprintf (file
, " %d", allocno
[j
].reg
);
1942 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1943 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_conflicts
, j
))
1944 fprintf (file
, " %d", j
);
1945 fprintf (file
, "\n");
1947 has_preferences
= 0;
1948 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1949 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1950 has_preferences
= 1;
1952 if (! has_preferences
)
1954 fprintf (file
, ";; %d preferences:", allocno
[i
].reg
);
1955 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1956 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1957 fprintf (file
, " %d", j
);
1958 fprintf (file
, "\n");
1960 fprintf (file
, "\n");
1964 dump_global_regs (FILE *file
)
1968 fprintf (file
, ";; Register dispositions:\n");
1969 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1970 if (reg_renumber
[i
] >= 0)
1972 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1974 fprintf (file
, "\n");
1977 fprintf (file
, "\n\n;; Hard regs used: ");
1978 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1979 if (regs_ever_live
[i
])
1980 fprintf (file
, " %d", i
);
1981 fprintf (file
, "\n\n");
1986 /* This page contains code to make live information more accurate.
1987 The accurate register liveness at program point P means:
1988 o there is a path from P to usage of the register and the
1989 register is not redefined or killed on the path.
1990 o register at P is partially available, i.e. there is a path from
1991 a register definition to the point P and the register is not
1992 killed (clobbered) on the path
1994 The standard GCC live information means only the first condition.
1995 Without the partial availability, there will be more register
1996 conflicts and as a consequence worse register allocation. The
1997 typical example where the information can be different is a
1998 register initialized in the loop at the basic block preceding the
2001 /* The following structure contains basic block data flow information
2002 used to calculate partial availability of registers. */
2006 /* The basic block reverse post-order number. */
2008 /* Registers used uninitialized in an insn in which there is an
2009 early clobbered register might get the same hard register. */
2010 bitmap earlyclobber
;
2011 /* Registers correspondingly killed (clobbered) and defined but not
2012 killed afterward in the basic block. */
2013 bitmap killed
, avloc
;
2014 /* Registers partially available and living (in other words whose
2015 values were calculated and used) correspondingly at the start
2016 and end of the basic block. */
2017 bitmap live_pavin
, live_pavout
;
2020 /* Macros for accessing data flow information of basic blocks. */
2022 #define BB_INFO(BB) ((struct bb_info *) (BB)->aux)
2023 #define BB_INFO_BY_INDEX(N) BB_INFO (BASIC_BLOCK(N))
2025 /* The function allocates the info structures of each basic block. It
2026 also initialized LIVE_PAVIN and LIVE_PAVOUT as if all hard
2027 registers were partially available. */
2030 allocate_bb_info (void)
2034 struct bb_info
*bb_info
;
2037 alloc_aux_for_blocks (sizeof (struct bb_info
));
2038 init
= BITMAP_ALLOC (NULL
);
2039 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2040 bitmap_set_bit (init
, i
);
2044 bb_info
->earlyclobber
= BITMAP_ALLOC (NULL
);
2045 bb_info
->avloc
= BITMAP_ALLOC (NULL
);
2046 bb_info
->killed
= BITMAP_ALLOC (NULL
);
2047 bb_info
->live_pavin
= BITMAP_ALLOC (NULL
);
2048 bb_info
->live_pavout
= BITMAP_ALLOC (NULL
);
2049 bitmap_copy (bb_info
->live_pavin
, init
);
2050 bitmap_copy (bb_info
->live_pavout
, init
);
2055 /* The function frees the allocated info of all basic blocks. */
2061 struct bb_info
*bb_info
;
2065 bb_info
= BB_INFO (bb
);
2066 BITMAP_FREE (bb_info
->live_pavout
);
2067 BITMAP_FREE (bb_info
->live_pavin
);
2068 BITMAP_FREE (bb_info
->killed
);
2069 BITMAP_FREE (bb_info
->avloc
);
2070 BITMAP_FREE (bb_info
->earlyclobber
);
2072 free_aux_for_blocks ();
2075 /* The function modifies local info for register REG being changed in
2076 SETTER. DATA is used to pass the current basic block info. */
2079 mark_reg_change (rtx reg
, rtx setter
, void *data
)
2082 basic_block bb
= data
;
2083 struct bb_info
*bb_info
= BB_INFO (bb
);
2085 if (GET_CODE (reg
) == SUBREG
)
2086 reg
= SUBREG_REG (reg
);
2091 regno
= REGNO (reg
);
2092 bitmap_set_bit (bb_info
->killed
, regno
);
2094 if (GET_CODE (setter
) != CLOBBER
)
2095 bitmap_set_bit (bb_info
->avloc
, regno
);
2097 bitmap_clear_bit (bb_info
->avloc
, regno
);
2100 /* Classes of registers which could be early clobbered in the current
2104 DEF_VEC_ALLOC_I(int,heap
);
2106 static VEC(int,heap
) *earlyclobber_regclass
;
2108 /* This function finds and stores register classes that could be early
2109 clobbered in INSN. If any earlyclobber classes are found, the function
2110 returns TRUE, in all other cases it returns FALSE. */
2113 check_earlyclobber (rtx insn
)
2118 extract_insn (insn
);
2120 VEC_truncate (int, earlyclobber_regclass
, 0);
2121 for (opno
= 0; opno
< recog_data
.n_operands
; opno
++)
2126 enum reg_class
class;
2127 const char *p
= recog_data
.constraints
[opno
];
2136 case '=': case '+': case '?':
2139 case 'm': case '<': case '>': case 'V': case 'o':
2140 case 'E': case 'F': case 'G': case 'H':
2141 case 's': case 'i': case 'n':
2142 case 'I': case 'J': case 'K': case 'L':
2143 case 'M': case 'N': case 'O': case 'P':
2145 case '0': case '1': case '2': case '3': case '4':
2146 case '5': case '6': case '7': case '8': case '9':
2147 /* These don't say anything we care about. */
2155 if (amp_p
&& class != NO_REGS
)
2161 VEC_iterate (int, earlyclobber_regclass
, i
, rc
);
2164 if (rc
== (int) class)
2168 /* We use VEC_quick_push here because
2169 earlyclobber_regclass holds no more than
2170 N_REG_CLASSES elements. */
2171 VEC_quick_push (int, earlyclobber_regclass
, (int) class);
2181 class = GENERAL_REGS
;
2185 class = REG_CLASS_FROM_CONSTRAINT (c
, p
);
2190 p
+= CONSTRAINT_LEN (c
, p
);
2197 /* The function checks that pseudo-register *X has a class
2198 intersecting with the class of pseudo-register could be early
2199 clobbered in the same insn.
2200 This function is a no-op if earlyclobber_regclass is empty. */
2203 mark_reg_use_for_earlyclobber (rtx
*x
, void *data ATTRIBUTE_UNUSED
)
2205 enum reg_class pref_class
, alt_class
;
2207 basic_block bb
= data
;
2208 struct bb_info
*bb_info
= BB_INFO (bb
);
2210 if (REG_P (*x
) && REGNO (*x
) >= FIRST_PSEUDO_REGISTER
)
2215 if (bitmap_bit_p (bb_info
->killed
, regno
)
2216 || bitmap_bit_p (bb_info
->avloc
, regno
))
2218 pref_class
= reg_preferred_class (regno
);
2219 alt_class
= reg_alternate_class (regno
);
2220 for (i
= 0; VEC_iterate (int, earlyclobber_regclass
, i
, rc
); i
++)
2222 if (reg_classes_intersect_p (rc
, pref_class
)
2224 && reg_classes_intersect_p (rc
, alt_class
)))
2226 bitmap_set_bit (bb_info
->earlyclobber
, regno
);
2234 /* The function processes all pseudo-registers in *X with the aid of
2235 previous function. */
2238 mark_reg_use_for_earlyclobber_1 (rtx
*x
, void *data
)
2240 for_each_rtx (x
, mark_reg_use_for_earlyclobber
, data
);
2243 /* The function calculates local info for each basic block. */
2246 calculate_local_reg_bb_info (void)
2251 /* We know that earlyclobber_regclass holds no more than
2252 N_REG_CLASSES elements. See check_earlyclobber. */
2253 earlyclobber_regclass
= VEC_alloc (int, heap
, N_REG_CLASSES
);
2256 bound
= NEXT_INSN (BB_END (bb
));
2257 for (insn
= BB_HEAD (bb
); insn
!= bound
; insn
= NEXT_INSN (insn
))
2260 note_stores (PATTERN (insn
), mark_reg_change
, bb
);
2261 if (check_earlyclobber (insn
))
2262 note_uses (&PATTERN (insn
), mark_reg_use_for_earlyclobber_1
, bb
);
2265 VEC_free (int, heap
, earlyclobber_regclass
);
2268 /* The function sets up reverse post-order number of each basic
2272 set_up_bb_rts_numbers (void)
2277 rts_order
= xmalloc (sizeof (int) * n_basic_blocks
);
2278 flow_reverse_top_sort_order_compute (rts_order
);
2279 for (i
= 0; i
< n_basic_blocks
; i
++)
2280 BB_INFO_BY_INDEX (rts_order
[i
])->rts_number
= i
;
2284 /* Compare function for sorting blocks in reverse postorder. */
2287 rpost_cmp (const void *bb1
, const void *bb2
)
2289 basic_block b1
= *(basic_block
*) bb1
, b2
= *(basic_block
*) bb2
;
2291 return BB_INFO (b2
)->rts_number
- BB_INFO (b1
)->rts_number
;
2294 /* Temporary bitmap used for live_pavin, live_pavout calculation. */
2295 static bitmap temp_bitmap
;
2297 DEF_VEC_P(basic_block
);
2298 DEF_VEC_ALLOC_P(basic_block
,heap
);
2300 /* The function calculates partial register availability according to
2301 the following equations:
2304 = empty for entry block
2305 | union (live_pavout of predecessors) & global_live_at_start
2306 bb.live_pavout = union (bb.live_pavin - bb.killed, bb.avloc)
2307 & global_live_at_end */
2310 calculate_reg_pav (void)
2312 basic_block bb
, succ
;
2315 VEC(basic_block
,heap
) *bbs
, *new_bbs
, *temp
;
2316 basic_block
*bb_array
;
2319 bbs
= VEC_alloc (basic_block
, heap
, n_basic_blocks
);
2320 new_bbs
= VEC_alloc (basic_block
, heap
, n_basic_blocks
);
2321 temp_bitmap
= BITMAP_ALLOC (NULL
);
2324 VEC_quick_push (basic_block
, bbs
, bb
);
2326 wset
= sbitmap_alloc (n_basic_blocks
+ 1);
2327 while (VEC_length (basic_block
, bbs
))
2329 bb_array
= VEC_address (basic_block
, bbs
);
2330 nel
= VEC_length (basic_block
, bbs
);
2331 qsort (bb_array
, nel
, sizeof (basic_block
), rpost_cmp
);
2332 sbitmap_zero (wset
);
2333 for (i
= 0; i
< nel
; i
++)
2336 struct bb_info
*bb_info
;
2337 bitmap bb_live_pavin
, bb_live_pavout
;
2340 bb_info
= BB_INFO (bb
);
2341 bb_live_pavin
= bb_info
->live_pavin
;
2342 bb_live_pavout
= bb_info
->live_pavout
;
2343 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2345 basic_block pred
= e
->src
;
2347 if (pred
->index
!= ENTRY_BLOCK
)
2348 bitmap_ior_into (bb_live_pavin
, BB_INFO (pred
)->live_pavout
);
2350 bitmap_and_into (bb_live_pavin
, bb
->il
.rtl
->global_live_at_start
);
2351 bitmap_ior_and_compl (temp_bitmap
, bb_info
->avloc
,
2352 bb_live_pavin
, bb_info
->killed
);
2353 bitmap_and_into (temp_bitmap
, bb
->il
.rtl
->global_live_at_end
);
2354 if (! bitmap_equal_p (temp_bitmap
, bb_live_pavout
))
2356 bitmap_copy (bb_live_pavout
, temp_bitmap
);
2357 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2360 if (succ
->index
!= EXIT_BLOCK
2361 && !TEST_BIT (wset
, succ
->index
))
2363 SET_BIT (wset
, succ
->index
);
2364 VEC_quick_push (basic_block
, new_bbs
, succ
);
2372 VEC_truncate (basic_block
, new_bbs
, 0);
2374 sbitmap_free (wset
);
2375 BITMAP_FREE (temp_bitmap
);
2376 VEC_free (basic_block
, heap
, new_bbs
);
2377 VEC_free (basic_block
, heap
, bbs
);
2380 /* The function modifies partial availability information for two
2381 special cases to prevent incorrect work of the subsequent passes
2382 with the accurate live information based on the partial
2386 modify_reg_pav (void)
2389 struct bb_info
*bb_info
;
2392 HARD_REG_SET zero
, stack_hard_regs
, used
;
2395 CLEAR_HARD_REG_SET (zero
);
2396 CLEAR_HARD_REG_SET (stack_hard_regs
);
2397 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
2398 SET_HARD_REG_BIT(stack_hard_regs
, i
);
2399 stack_regs
= BITMAP_ALLOC (NULL
);
2400 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
2402 COPY_HARD_REG_SET (used
, reg_class_contents
[reg_preferred_class (i
)]);
2403 IOR_HARD_REG_SET (used
, reg_class_contents
[reg_alternate_class (i
)]);
2404 AND_HARD_REG_SET (used
, stack_hard_regs
);
2405 GO_IF_HARD_REG_EQUAL(used
, zero
, skip
);
2406 bitmap_set_bit (stack_regs
, i
);
2413 bb_info
= BB_INFO (bb
);
2415 /* Reload can assign the same hard register to uninitialized
2416 pseudo-register and early clobbered pseudo-register in an
2417 insn if the pseudo-register is used first time in given BB
2418 and not lived at the BB start. To prevent this we don't
2419 change life information for such pseudo-registers. */
2420 bitmap_ior_into (bb_info
->live_pavin
, bb_info
->earlyclobber
);
2422 /* We can not use the same stack register for uninitialized
2423 pseudo-register and another living pseudo-register because if the
2424 uninitialized pseudo-register dies, subsequent pass reg-stack
2425 will be confused (it will believe that the other register
2427 bitmap_ior_into (bb_info
->live_pavin
, stack_regs
);
2431 BITMAP_FREE (stack_regs
);
2435 /* The following function makes live information more accurate by
2436 modifying global_live_at_start and global_live_at_end of basic
2439 The standard GCC life analysis permits registers to live
2440 uninitialized, for example:
2449 With normal life_analysis, R would be live before "Loop:".
2450 The result is that R causes many interferences that do not
2453 After the function call a register lives at a program point
2454 only if it is initialized on a path from CFG entry to the
2458 make_accurate_live_analysis (void)
2461 struct bb_info
*bb_info
;
2463 max_regno
= max_reg_num ();
2465 allocate_bb_info ();
2466 calculate_local_reg_bb_info ();
2467 set_up_bb_rts_numbers ();
2468 calculate_reg_pav ();
2472 bb_info
= BB_INFO (bb
);
2474 bitmap_and_into (bb
->il
.rtl
->global_live_at_start
, bb_info
->live_pavin
);
2475 bitmap_and_into (bb
->il
.rtl
->global_live_at_end
, bb_info
->live_pavout
);
2479 /* Run old register allocator. Return TRUE if we must exit
2480 rest_of_compilation upon return. */
2482 rest_of_handle_global_alloc (void)
2486 /* If optimizing, allocate remaining pseudo-regs. Do the reload
2487 pass fixing up any insns that are invalid. */
2490 failure
= global_alloc (dump_file
);
2493 build_insn_chain (get_insns ());
2494 failure
= reload (get_insns (), 0);
2497 if (dump_enabled_p (pass_global_alloc
.static_pass_number
))
2499 timevar_push (TV_DUMP
);
2500 dump_global_regs (dump_file
);
2501 timevar_pop (TV_DUMP
);
2504 gcc_assert (reload_completed
|| failure
);
2505 reload_completed
= !failure
;
2508 struct tree_opt_pass pass_global_alloc
=
2512 rest_of_handle_global_alloc
, /* execute */
2515 0, /* static_pass_number */
2516 TV_GLOBAL_ALLOC
, /* tv_id */
2517 0, /* properties_required */
2518 0, /* properties_provided */
2519 0, /* properties_destroyed */
2520 0, /* todo_flags_start */
2522 TODO_ggc_collect
, /* todo_flags_finish */