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 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
25 #include "coretypes.h"
29 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "insn-config.h"
41 /* This pass of the compiler performs global register allocation.
42 It assigns hard register numbers to all the pseudo registers
43 that were not handled in local_alloc. Assignments are recorded
44 in the vector reg_renumber, not by changing the rtl code.
45 (Such changes are made by final). The entry point is
46 the function global_alloc.
48 After allocation is complete, the reload pass is run as a subroutine
49 of this pass, so that when a pseudo reg loses its hard reg due to
50 spilling it is possible to make a second attempt to find a hard
51 reg for it. The reload pass is independent in other respects
52 and it is run even when stupid register allocation is in use.
54 1. Assign allocation-numbers (allocnos) to the pseudo-registers
55 still needing allocations and to the pseudo-registers currently
56 allocated by local-alloc which may be spilled by reload.
57 Set up tables reg_allocno and allocno_reg to map
58 reg numbers to allocnos and vice versa.
59 max_allocno gets the number of allocnos in use.
61 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
62 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
63 for conflicts between allocnos and explicit hard register use
64 (which includes use of pseudo-registers allocated by local_alloc).
66 3. For each basic block
67 walk forward through the block, recording which
68 pseudo-registers and which hardware registers are live.
69 Build the conflict matrix between the pseudo-registers
70 and another of pseudo-registers versus hardware registers.
71 Also record the preferred hardware registers
72 for each pseudo-register.
74 4. Sort a table of the allocnos into order of
75 desirability of the variables.
77 5. Allocate the variables in that order; each if possible into
78 a preferred register, else into another register. */
80 /* Number of pseudo-registers which are candidates for allocation. */
82 static int max_allocno
;
84 /* Indexed by (pseudo) reg number, gives the allocno, or -1
85 for pseudo registers which are not to be allocated. */
87 static int *reg_allocno
;
92 /* Gives the number of consecutive hard registers needed by that
96 /* Number of calls crossed by each allocno. */
99 /* Number of refs to each allocno. */
102 /* Frequency of uses of each allocno. */
105 /* Guess at live length of each allocno.
106 This is actually the max of the live lengths of the regs. */
109 /* Set of hard regs conflicting with allocno N. */
111 HARD_REG_SET hard_reg_conflicts
;
113 /* Set of hard regs preferred by allocno N.
114 This is used to make allocnos go into regs that are copied to or from them,
115 when possible, to reduce register shuffling. */
117 HARD_REG_SET hard_reg_preferences
;
119 /* Similar, but just counts register preferences made in simple copy
120 operations, rather than arithmetic. These are given priority because
121 we can always eliminate an insn by using these, but using a register
122 in the above list won't always eliminate an insn. */
124 HARD_REG_SET hard_reg_copy_preferences
;
126 /* Similar to hard_reg_preferences, but includes bits for subsequent
127 registers when an allocno is multi-word. The above variable is used for
128 allocation while this is used to build reg_someone_prefers, below. */
130 HARD_REG_SET hard_reg_full_preferences
;
132 /* Set of hard registers that some later allocno has a preference for. */
134 HARD_REG_SET regs_someone_prefers
;
137 /* Set to true if allocno can't be allocated in the stack register. */
142 static struct allocno
*allocno
;
144 /* A vector of the integers from 0 to max_allocno-1,
145 sorted in the order of first-to-be-allocated first. */
147 static int *allocno_order
;
149 /* Indexed by (pseudo) reg number, gives the number of another
150 lower-numbered pseudo reg which can share a hard reg with this pseudo
151 *even if the two pseudos would otherwise appear to conflict*. */
153 static int *reg_may_share
;
155 /* Define the number of bits in each element of `conflicts' and what
156 type that element has. We use the largest integer format on the
159 #define INT_BITS HOST_BITS_PER_WIDE_INT
160 #define INT_TYPE HOST_WIDE_INT
162 /* max_allocno by max_allocno array of bits,
163 recording whether two allocno's conflict (can't go in the same
166 `conflicts' is symmetric after the call to mirror_conflicts. */
168 static INT_TYPE
*conflicts
;
170 /* Number of ints require to hold max_allocno bits.
171 This is the length of a row in `conflicts'. */
173 static int allocno_row_words
;
175 /* Two macros to test or store 1 in an element of `conflicts'. */
177 #define CONFLICTP(I, J) \
178 (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS] \
179 & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS)))
181 /* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
183 #define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
187 INT_TYPE *p_ = (ALLOCNO_SET); \
189 for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
190 i_--, allocno_ += INT_BITS) \
192 unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
194 for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
202 /* This doesn't work for non-GNU C due to the way CODE is macro expanded. */
204 /* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to
205 the conflicting allocno, and execute CODE. This macro assumes that
206 mirror_conflicts has been run. */
207 #define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\
208 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\
212 /* Set of hard regs currently live (during scan of all insns). */
214 static HARD_REG_SET hard_regs_live
;
216 /* Set of registers that global-alloc isn't supposed to use. */
218 static HARD_REG_SET no_global_alloc_regs
;
220 /* Set of registers used so far. */
222 static HARD_REG_SET regs_used_so_far
;
224 /* Number of refs to each hard reg, as used by local alloc.
225 It is zero for a reg that contains global pseudos or is explicitly used. */
227 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
229 /* Frequency of uses of given hard reg. */
230 static int local_reg_freq
[FIRST_PSEUDO_REGISTER
];
232 /* Guess at live length of each hard reg, as used by local alloc.
233 This is actually the sum of the live lengths of the specific regs. */
235 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
237 /* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
238 element I, and hard register number J. */
240 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
242 /* Bit mask for allocnos live at current point in the scan. */
244 static INT_TYPE
*allocnos_live
;
246 /* Test, set or clear bit number I in allocnos_live,
247 a bit vector indexed by allocno. */
249 #define SET_ALLOCNO_LIVE(I) \
250 (allocnos_live[(unsigned) (I) / INT_BITS] \
251 |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
253 #define CLEAR_ALLOCNO_LIVE(I) \
254 (allocnos_live[(unsigned) (I) / INT_BITS] \
255 &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
257 /* This is turned off because it doesn't work right for DImode.
258 (And it is only used for DImode, so the other cases are worthless.)
259 The problem is that it isn't true that there is NO possibility of conflict;
260 only that there is no conflict if the two pseudos get the exact same regs.
261 If they were allocated with a partial overlap, there would be a conflict.
262 We can't safely turn off the conflict unless we have another way to
263 prevent the partial overlap.
265 Idea: change hard_reg_conflicts so that instead of recording which
266 hard regs the allocno may not overlap, it records where the allocno
267 may not start. Change both where it is used and where it is updated.
268 Then there is a way to record that (reg:DI 108) may start at 10
269 but not at 9 or 11. There is still the question of how to record
270 this semi-conflict between two pseudos. */
272 /* Reg pairs for which conflict after the current insn
273 is inhibited by a REG_NO_CONFLICT note.
274 If the table gets full, we ignore any other notes--that is conservative. */
275 #define NUM_NO_CONFLICT_PAIRS 4
276 /* Number of pairs in use in this insn. */
277 int n_no_conflict_pairs
;
278 static struct { int allocno1
, allocno2
;}
279 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
282 /* Record all regs that are set in any one insn.
283 Communication from mark_reg_{store,clobber} and global_conflicts. */
285 static rtx
*regs_set
;
286 static int n_regs_set
;
288 /* All registers that can be eliminated. */
290 static HARD_REG_SET eliminable_regset
;
292 static int allocno_compare (const void *, const void *);
293 static void global_conflicts (void);
294 static void mirror_conflicts (void);
295 static void expand_preferences (void);
296 static void prune_preferences (void);
297 static void find_reg (int, HARD_REG_SET
, int, int, int);
298 static void record_one_conflict (int);
299 static void record_conflicts (int *, int);
300 static void mark_reg_store (rtx
, rtx
, void *);
301 static void mark_reg_clobber (rtx
, rtx
, void *);
302 static void mark_reg_conflicts (rtx
);
303 static void mark_reg_death (rtx
);
304 static void mark_reg_live_nc (int, enum machine_mode
);
305 static void set_preference (rtx
, rtx
);
306 static void dump_conflicts (FILE *);
307 static void reg_becomes_live (rtx
, rtx
, void *);
308 static void reg_dies (int, enum machine_mode
, struct insn_chain
*);
310 static void allocate_bb_info (void);
311 static void free_bb_info (void);
312 static void calculate_local_reg_bb_info (void);
313 static void set_up_bb_rts_numbers (void);
314 static int rpost_cmp (const void *, const void *);
315 static bool modify_bb_reg_pav (basic_block
, basic_block
, bool);
316 static void calculate_reg_pav (void);
317 static void make_accurate_live_analysis (void);
321 /* Perform allocation of pseudo-registers not allocated by local_alloc.
322 FILE is a file to output debugging information on,
323 or zero if such output is not desired.
325 Return value is nonzero if reload failed
326 and we must not do any more for this function. */
329 global_alloc (FILE *file
)
332 #ifdef ELIMINABLE_REGS
333 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
336 = (! flag_omit_frame_pointer
337 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
338 || FRAME_POINTER_REQUIRED
);
343 make_accurate_live_analysis ();
347 /* A machine may have certain hard registers that
348 are safe to use only within a basic block. */
350 CLEAR_HARD_REG_SET (no_global_alloc_regs
);
352 /* Build the regset of all eliminable registers and show we can't use those
353 that we already know won't be eliminated. */
354 #ifdef ELIMINABLE_REGS
355 for (i
= 0; i
< ARRAY_SIZE (eliminables
); i
++)
358 = (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
359 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
));
361 if (!regs_asm_clobbered
[eliminables
[i
].from
])
363 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
366 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
368 else if (cannot_elim
)
369 error ("%s cannot be used in asm here",
370 reg_names
[eliminables
[i
].from
]);
372 regs_ever_live
[eliminables
[i
].from
] = 1;
374 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
375 if (!regs_asm_clobbered
[HARD_FRAME_POINTER_REGNUM
])
377 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
379 SET_HARD_REG_BIT (no_global_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
382 error ("%s cannot be used in asm here",
383 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
385 regs_ever_live
[HARD_FRAME_POINTER_REGNUM
] = 1;
389 if (!regs_asm_clobbered
[FRAME_POINTER_REGNUM
])
391 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
393 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
396 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
398 regs_ever_live
[FRAME_POINTER_REGNUM
] = 1;
401 /* Track which registers have already been used. Start with registers
402 explicitly in the rtl, then registers allocated by local register
405 CLEAR_HARD_REG_SET (regs_used_so_far
);
406 #ifdef LEAF_REGISTERS
407 /* If we are doing the leaf function optimization, and this is a leaf
408 function, it means that the registers that take work to save are those
409 that need a register window. So prefer the ones that can be used in
412 const char *cheap_regs
;
413 const char *const leaf_regs
= LEAF_REGISTERS
;
415 if (only_leaf_regs_used () && leaf_function_p ())
416 cheap_regs
= leaf_regs
;
418 cheap_regs
= call_used_regs
;
419 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
420 if (regs_ever_live
[i
] || cheap_regs
[i
])
421 SET_HARD_REG_BIT (regs_used_so_far
, i
);
424 /* We consider registers that do not have to be saved over calls as if
425 they were already used since there is no cost in using them. */
426 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
427 if (regs_ever_live
[i
] || call_used_regs
[i
])
428 SET_HARD_REG_BIT (regs_used_so_far
, i
);
431 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
432 if (reg_renumber
[i
] >= 0)
433 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
435 /* Establish mappings from register number to allocation number
436 and vice versa. In the process, count the allocnos. */
438 reg_allocno
= xmalloc (max_regno
* sizeof (int));
440 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
443 /* Initialize the shared-hard-reg mapping
444 from the list of pairs that may share. */
445 reg_may_share
= xcalloc (max_regno
, sizeof (int));
446 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
448 int r1
= REGNO (XEXP (x
, 0));
449 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
451 reg_may_share
[r1
] = r2
;
453 reg_may_share
[r2
] = r1
;
456 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
457 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
458 that we are supposed to refrain from putting in a hard reg.
459 -2 means do make an allocno but don't allocate it. */
460 if (REG_N_REFS (i
) != 0 && REG_LIVE_LENGTH (i
) != -1
461 /* Don't allocate pseudos that cross calls,
462 if this function receives a nonlocal goto. */
463 && (! current_function_has_nonlocal_label
464 || REG_N_CALLS_CROSSED (i
) == 0))
466 if (reg_renumber
[i
] < 0 && reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
467 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
469 reg_allocno
[i
] = max_allocno
++;
470 if (REG_LIVE_LENGTH (i
) == 0)
476 allocno
= xcalloc (max_allocno
, sizeof (struct allocno
));
478 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
479 if (reg_allocno
[i
] >= 0)
481 int num
= reg_allocno
[i
];
482 allocno
[num
].reg
= i
;
483 allocno
[num
].size
= PSEUDO_REGNO_SIZE (i
);
484 allocno
[num
].calls_crossed
+= REG_N_CALLS_CROSSED (i
);
485 allocno
[num
].n_refs
+= REG_N_REFS (i
);
486 allocno
[num
].freq
+= REG_FREQ (i
);
487 if (allocno
[num
].live_length
< REG_LIVE_LENGTH (i
))
488 allocno
[num
].live_length
= REG_LIVE_LENGTH (i
);
491 /* Calculate amount of usage of each hard reg by pseudos
492 allocated by local-alloc. This is to see if we want to
494 memset (local_reg_live_length
, 0, sizeof local_reg_live_length
);
495 memset (local_reg_n_refs
, 0, sizeof local_reg_n_refs
);
496 memset (local_reg_freq
, 0, sizeof local_reg_freq
);
497 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
498 if (reg_renumber
[i
] >= 0)
500 int regno
= reg_renumber
[i
];
501 int endregno
= regno
+ hard_regno_nregs
[regno
][PSEUDO_REGNO_MODE (i
)];
504 for (j
= regno
; j
< endregno
; j
++)
506 local_reg_n_refs
[j
] += REG_N_REFS (i
);
507 local_reg_freq
[j
] += REG_FREQ (i
);
508 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
512 /* We can't override local-alloc for a reg used not just by local-alloc. */
513 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
514 if (regs_ever_live
[i
])
515 local_reg_n_refs
[i
] = 0, local_reg_freq
[i
] = 0;
517 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
519 /* We used to use alloca here, but the size of what it would try to
520 allocate would occasionally cause it to exceed the stack limit and
521 cause unpredictable core dumps. Some examples were > 2Mb in size. */
522 conflicts
= xcalloc (max_allocno
* allocno_row_words
, sizeof (INT_TYPE
));
524 allocnos_live
= xmalloc (allocno_row_words
* sizeof (INT_TYPE
));
526 /* If there is work to be done (at least one reg to allocate),
527 perform global conflict analysis and allocate the regs. */
531 /* Scan all the insns and compute the conflicts among allocnos
532 and between allocnos and hard regs. */
538 /* Eliminate conflicts between pseudos and eliminable registers. If
539 the register is not eliminated, the pseudo won't really be able to
540 live in the eliminable register, so the conflict doesn't matter.
541 If we do eliminate the register, the conflict will no longer exist.
542 So in either case, we can ignore the conflict. Likewise for
545 for (i
= 0; i
< (size_t) max_allocno
; i
++)
547 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_conflicts
,
549 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_copy_preferences
,
551 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_preferences
,
555 /* Try to expand the preferences by merging them between allocnos. */
557 expand_preferences ();
559 /* Determine the order to allocate the remaining pseudo registers. */
561 allocno_order
= xmalloc (max_allocno
* sizeof (int));
562 for (i
= 0; i
< (size_t) max_allocno
; i
++)
563 allocno_order
[i
] = i
;
565 /* Default the size to 1, since allocno_compare uses it to divide by.
566 Also convert allocno_live_length of zero to -1. A length of zero
567 can occur when all the registers for that allocno have reg_live_length
568 equal to -2. In this case, we want to make an allocno, but not
569 allocate it. So avoid the divide-by-zero and set it to a low
572 for (i
= 0; i
< (size_t) max_allocno
; i
++)
574 if (allocno
[i
].size
== 0)
576 if (allocno
[i
].live_length
== 0)
577 allocno
[i
].live_length
= -1;
580 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
582 prune_preferences ();
585 dump_conflicts (file
);
587 /* Try allocating them, one by one, in that order,
588 except for parameters marked with reg_live_length[regno] == -2. */
590 for (i
= 0; i
< (size_t) max_allocno
; i
++)
591 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] < 0
592 && REG_LIVE_LENGTH (allocno
[allocno_order
[i
]].reg
) >= 0)
594 /* If we have more than one register class,
595 first try allocating in the class that is cheapest
596 for this pseudo-reg. If that fails, try any reg. */
597 if (N_REG_CLASSES
> 1)
599 find_reg (allocno_order
[i
], 0, 0, 0, 0);
600 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
603 if (reg_alternate_class (allocno
[allocno_order
[i
]].reg
) != NO_REGS
)
604 find_reg (allocno_order
[i
], 0, 1, 0, 0);
607 free (allocno_order
);
610 /* Do the reloads now while the allocno data still exist, so that we can
611 try to assign new hard regs to any pseudo regs that are spilled. */
613 #if 0 /* We need to eliminate regs even if there is no rtl code,
614 for the sake of debugging information. */
615 if (n_basic_blocks
> 0)
618 build_insn_chain (get_insns ());
619 retval
= reload (get_insns (), 1);
624 free (reg_may_share
);
627 free (allocnos_live
);
632 /* Sort predicate for ordering the allocnos.
633 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
636 allocno_compare (const void *v1p
, const void *v2p
)
638 int v1
= *(const int *)v1p
, v2
= *(const int *)v2p
;
639 /* Note that the quotient will never be bigger than
640 the value of floor_log2 times the maximum number of
641 times a register can occur in one insn (surely less than 100)
642 weighted by the frequency (maximally REG_FREQ_MAX).
643 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
645 = (((double) (floor_log2 (allocno
[v1
].n_refs
) * allocno
[v1
].freq
)
646 / allocno
[v1
].live_length
)
647 * (10000 / REG_FREQ_MAX
) * allocno
[v1
].size
);
649 = (((double) (floor_log2 (allocno
[v2
].n_refs
) * allocno
[v2
].freq
)
650 / allocno
[v2
].live_length
)
651 * (10000 / REG_FREQ_MAX
) * allocno
[v2
].size
);
655 /* If regs are equally good, sort by allocno,
656 so that the results of qsort leave nothing to chance. */
660 /* Scan the rtl code and record all conflicts and register preferences in the
661 conflict matrices and preference tables. */
664 global_conflicts (void)
669 int *block_start_allocnos
;
671 /* Make a vector that mark_reg_{store,clobber} will store in. */
672 regs_set
= xmalloc (max_parallel
* sizeof (rtx
) * 2);
674 block_start_allocnos
= xmalloc (max_allocno
* sizeof (int));
678 memset (allocnos_live
, 0, allocno_row_words
* sizeof (INT_TYPE
));
680 /* Initialize table of registers currently live
681 to the state at the beginning of this basic block.
682 This also marks the conflicts among hard registers
683 and any allocnos that are live.
685 For pseudo-regs, there is only one bit for each one
686 no matter how many hard regs it occupies.
687 This is ok; we know the size from PSEUDO_REGNO_SIZE.
688 For explicit hard regs, we cannot know the size that way
689 since one hard reg can be used with various sizes.
690 Therefore, we must require that all the hard regs
691 implicitly live as part of a multi-word hard reg
692 are explicitly marked in basic_block_live_at_start. */
695 regset old
= b
->global_live_at_start
;
698 REG_SET_TO_HARD_REG_SET (hard_regs_live
, old
);
699 EXECUTE_IF_SET_IN_REG_SET (old
, FIRST_PSEUDO_REGISTER
, i
,
701 int a
= reg_allocno
[i
];
704 SET_ALLOCNO_LIVE (a
);
705 block_start_allocnos
[ax
++] = a
;
707 else if ((a
= reg_renumber
[i
]) >= 0)
709 (a
, PSEUDO_REGNO_MODE (i
));
712 /* Record that each allocno now live conflicts with each hard reg
715 It is not necessary to mark any conflicts between pseudos as
716 this point, even for pseudos which are live at the start of
719 Given two pseudos X and Y and any point in the CFG P.
721 On any path to point P where X and Y are live one of the
722 following conditions must be true:
724 1. X is live at some instruction on the path that
727 2. Y is live at some instruction on the path that
730 3. Either X or Y is not evaluated on the path to P
731 (ie it is used uninitialized) and thus the
732 conflict can be ignored.
734 In cases #1 and #2 the conflict will be recorded when we
735 scan the instruction that makes either X or Y become live. */
736 record_conflicts (block_start_allocnos
, ax
);
738 /* Pseudos can't go in stack regs at the start of a basic block that
739 is reached by an abnormal edge. Likewise for call clobbered regs,
740 because because caller-save, fixup_abnormal_edges, and possibly
741 the table driven EH machinery are not quite ready to handle such
742 regs live across such edges. */
746 for (e
= b
->pred
; e
; e
= e
->pred_next
)
747 if (e
->flags
& EDGE_ABNORMAL
)
753 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, ax
,
755 allocno
[ax
].no_stack_reg
= 1;
757 for (ax
= FIRST_STACK_REG
; ax
<= LAST_STACK_REG
; ax
++)
758 record_one_conflict (ax
);
761 /* No need to record conflicts for call clobbered regs if we have
762 nonlocal labels around, as we don't ever try to allocate such
763 regs in this case. */
764 if (! current_function_has_nonlocal_label
)
765 for (ax
= 0; ax
< FIRST_PSEUDO_REGISTER
; ax
++)
766 if (call_used_regs
[ax
])
767 record_one_conflict (ax
);
774 /* Scan the code of this basic block, noting which allocnos
775 and hard regs are born or die. When one is born,
776 record a conflict with all others currently live. */
780 RTX_CODE code
= GET_CODE (insn
);
783 /* Make regs_set an empty set. */
787 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
792 for (link
= REG_NOTES (insn
);
793 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
794 link
= XEXP (link
, 1))
795 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
797 no_conflict_pairs
[i
].allocno1
798 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
799 no_conflict_pairs
[i
].allocno2
800 = reg_allocno
[REGNO (XEXP (link
, 0))];
805 /* Mark any registers clobbered by INSN as live,
806 so they conflict with the inputs. */
808 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
810 /* Mark any registers dead after INSN as dead now. */
812 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
813 if (REG_NOTE_KIND (link
) == REG_DEAD
)
814 mark_reg_death (XEXP (link
, 0));
816 /* Mark any registers set in INSN as live,
817 and mark them as conflicting with all other live regs.
818 Clobbers are processed again, so they conflict with
819 the registers that are set. */
821 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
824 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
825 if (REG_NOTE_KIND (link
) == REG_INC
)
826 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
829 /* If INSN has multiple outputs, then any reg that dies here
830 and is used inside of an output
831 must conflict with the other outputs.
833 It is unsafe to use !single_set here since it will ignore an
834 unused output. Just because an output is unused does not mean
835 the compiler can assume the side effect will not occur.
836 Consider if REG appears in the address of an output and we
837 reload the output. If we allocate REG to the same hard
838 register as an unused output we could set the hard register
839 before the output reload insn. */
840 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
841 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
842 if (REG_NOTE_KIND (link
) == REG_DEAD
)
844 int used_in_output
= 0;
846 rtx reg
= XEXP (link
, 0);
848 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
850 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
851 if (GET_CODE (set
) == SET
852 && GET_CODE (SET_DEST (set
)) != REG
853 && !rtx_equal_p (reg
, SET_DEST (set
))
854 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
858 mark_reg_conflicts (reg
);
861 /* Mark any registers set in INSN and then never used. */
863 while (n_regs_set
-- > 0)
865 rtx note
= find_regno_note (insn
, REG_UNUSED
,
866 REGNO (regs_set
[n_regs_set
]));
868 mark_reg_death (XEXP (note
, 0));
872 if (insn
== BB_END (b
))
874 insn
= NEXT_INSN (insn
);
879 free (block_start_allocnos
);
882 /* Expand the preference information by looking for cases where one allocno
883 dies in an insn that sets an allocno. If those two allocnos don't conflict,
884 merge any preferences between those allocnos. */
887 expand_preferences (void)
893 /* We only try to handle the most common cases here. Most of the cases
894 where this wins are reg-reg copies. */
896 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
898 && (set
= single_set (insn
)) != 0
899 && GET_CODE (SET_DEST (set
)) == REG
900 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
901 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
902 if (REG_NOTE_KIND (link
) == REG_DEAD
903 && GET_CODE (XEXP (link
, 0)) == REG
904 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
905 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
906 reg_allocno
[REGNO (XEXP (link
, 0))]))
908 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
909 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
911 if (XEXP (link
, 0) == SET_SRC (set
))
913 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_copy_preferences
,
914 allocno
[a2
].hard_reg_copy_preferences
);
915 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_copy_preferences
,
916 allocno
[a1
].hard_reg_copy_preferences
);
919 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_preferences
,
920 allocno
[a2
].hard_reg_preferences
);
921 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_preferences
,
922 allocno
[a1
].hard_reg_preferences
);
923 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_full_preferences
,
924 allocno
[a2
].hard_reg_full_preferences
);
925 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_full_preferences
,
926 allocno
[a1
].hard_reg_full_preferences
);
930 /* Prune the preferences for global registers to exclude registers that cannot
933 Compute `regs_someone_prefers', which is a bitmask of the hard registers
934 that are preferred by conflicting registers of lower priority. If possible,
935 we will avoid using these registers. */
938 prune_preferences (void)
942 int *allocno_to_order
= xmalloc (max_allocno
* sizeof (int));
944 /* Scan least most important to most important.
945 For each allocno, remove from preferences registers that cannot be used,
946 either because of conflicts or register type. Then compute all registers
947 preferred by each lower-priority register that conflicts. */
949 for (i
= max_allocno
- 1; i
>= 0; i
--)
953 num
= allocno_order
[i
];
954 allocno_to_order
[num
] = i
;
955 COPY_HARD_REG_SET (temp
, allocno
[num
].hard_reg_conflicts
);
957 if (allocno
[num
].calls_crossed
== 0)
958 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
960 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
962 IOR_COMPL_HARD_REG_SET
964 reg_class_contents
[(int) reg_preferred_class (allocno
[num
].reg
)]);
966 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, temp
);
967 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, temp
);
968 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_full_preferences
, temp
);
971 for (i
= max_allocno
- 1; i
>= 0; i
--)
973 /* Merge in the preferences of lower-priority registers (they have
974 already been pruned). If we also prefer some of those registers,
975 don't exclude them unless we are of a smaller size (in which case
976 we want to give the lower-priority allocno the first chance for
978 HARD_REG_SET temp
, temp2
;
981 num
= allocno_order
[i
];
983 CLEAR_HARD_REG_SET (temp
);
984 CLEAR_HARD_REG_SET (temp2
);
986 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ num
* allocno_row_words
,
989 if (allocno_to_order
[allocno2
] > i
)
991 if (allocno
[allocno2
].size
<= allocno
[num
].size
)
992 IOR_HARD_REG_SET (temp
,
993 allocno
[allocno2
].hard_reg_full_preferences
);
995 IOR_HARD_REG_SET (temp2
,
996 allocno
[allocno2
].hard_reg_full_preferences
);
1000 AND_COMPL_HARD_REG_SET (temp
, allocno
[num
].hard_reg_full_preferences
);
1001 IOR_HARD_REG_SET (temp
, temp2
);
1002 COPY_HARD_REG_SET (allocno
[num
].regs_someone_prefers
, temp
);
1004 free (allocno_to_order
);
1007 /* Assign a hard register to allocno NUM; look for one that is the beginning
1008 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
1009 The registers marked in PREFREGS are tried first.
1011 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
1012 be used for this allocation.
1014 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
1015 Otherwise ignore that preferred class and use the alternate class.
1017 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
1018 will have to be saved and restored at calls.
1020 RETRYING is nonzero if this is called from retry_global_alloc.
1022 If we find one, record it in reg_renumber.
1023 If not, do nothing. */
1026 find_reg (int num
, HARD_REG_SET losers
, int alt_regs_p
, int accept_call_clobbered
, int retrying
)
1028 int i
, best_reg
, pass
;
1029 HARD_REG_SET used
, used1
, used2
;
1031 enum reg_class
class = (alt_regs_p
1032 ? reg_alternate_class (allocno
[num
].reg
)
1033 : reg_preferred_class (allocno
[num
].reg
));
1034 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno
[num
].reg
);
1036 if (accept_call_clobbered
)
1037 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
1038 else if (allocno
[num
].calls_crossed
== 0)
1039 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
1041 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
1043 /* Some registers should not be allocated in global-alloc. */
1044 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
1046 IOR_HARD_REG_SET (used1
, losers
);
1048 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
1049 COPY_HARD_REG_SET (used2
, used1
);
1051 IOR_HARD_REG_SET (used1
, allocno
[num
].hard_reg_conflicts
);
1053 #ifdef CANNOT_CHANGE_MODE_CLASS
1054 cannot_change_mode_set_regs (&used1
, mode
, allocno
[num
].reg
);
1057 /* Try each hard reg to see if it fits. Do this in two passes.
1058 In the first pass, skip registers that are preferred by some other pseudo
1059 to give it a better chance of getting one of those registers. Only if
1060 we can't get a register when excluding those do we take one of them.
1061 However, we never allocate a register for the first time in pass 0. */
1063 COPY_HARD_REG_SET (used
, used1
);
1064 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
1065 IOR_HARD_REG_SET (used
, allocno
[num
].regs_someone_prefers
);
1068 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
1069 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
1073 COPY_HARD_REG_SET (used
, used1
);
1074 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1076 #ifdef REG_ALLOC_ORDER
1077 int regno
= reg_alloc_order
[i
];
1081 if (! TEST_HARD_REG_BIT (used
, regno
)
1082 && HARD_REGNO_MODE_OK (regno
, mode
)
1083 && (allocno
[num
].calls_crossed
== 0
1084 || accept_call_clobbered
1085 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
)))
1088 int lim
= regno
+ hard_regno_nregs
[regno
][mode
];
1091 && ! TEST_HARD_REG_BIT (used
, j
));
1098 #ifndef REG_ALLOC_ORDER
1099 i
= j
; /* Skip starting points we know will lose */
1105 /* See if there is a preferred register with the same class as the register
1106 we allocated above. Making this restriction prevents register
1107 preferencing from creating worse register allocation.
1109 Remove from the preferred registers and conflicting registers. Note that
1110 additional conflicts may have been added after `prune_preferences' was
1113 First do this for those register with copy preferences, then all
1114 preferred registers. */
1116 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, used
);
1117 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_copy_preferences
,
1118 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
1122 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1123 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_copy_preferences
, i
)
1124 && HARD_REGNO_MODE_OK (i
, mode
)
1125 && (allocno
[num
].calls_crossed
== 0
1126 || accept_call_clobbered
1127 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1128 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1129 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1130 REGNO_REG_CLASS (best_reg
))
1131 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1132 REGNO_REG_CLASS (i
))))
1135 int lim
= i
+ hard_regno_nregs
[i
][mode
];
1138 && ! TEST_HARD_REG_BIT (used
, j
)
1139 && (REGNO_REG_CLASS (j
)
1140 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1141 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1142 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1143 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1144 REGNO_REG_CLASS (j
))));
1155 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, used
);
1156 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_preferences
,
1157 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1161 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1162 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_preferences
, i
)
1163 && HARD_REGNO_MODE_OK (i
, mode
)
1164 && (allocno
[num
].calls_crossed
== 0
1165 || accept_call_clobbered
1166 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1167 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1168 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1169 REGNO_REG_CLASS (best_reg
))
1170 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1171 REGNO_REG_CLASS (i
))))
1174 int lim
= i
+ hard_regno_nregs
[i
][mode
];
1177 && ! TEST_HARD_REG_BIT (used
, j
)
1178 && (REGNO_REG_CLASS (j
)
1179 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1180 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1181 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1182 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1183 REGNO_REG_CLASS (j
))));
1194 /* If we haven't succeeded yet, try with caller-saves.
1195 We need not check to see if the current function has nonlocal
1196 labels because we don't put any pseudos that are live over calls in
1197 registers in that case. */
1199 if (flag_caller_saves
&& best_reg
< 0)
1201 /* Did not find a register. If it would be profitable to
1202 allocate a call-clobbered register and save and restore it
1203 around calls, do that. */
1204 if (! accept_call_clobbered
1205 && allocno
[num
].calls_crossed
!= 0
1206 && CALLER_SAVE_PROFITABLE (allocno
[num
].n_refs
,
1207 allocno
[num
].calls_crossed
))
1209 HARD_REG_SET new_losers
;
1211 CLEAR_HARD_REG_SET (new_losers
);
1213 COPY_HARD_REG_SET (new_losers
, losers
);
1215 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1216 find_reg (num
, new_losers
, alt_regs_p
, 1, retrying
);
1217 if (reg_renumber
[allocno
[num
].reg
] >= 0)
1219 caller_save_needed
= 1;
1225 /* If we haven't succeeded yet,
1226 see if some hard reg that conflicts with us
1227 was utilized poorly by local-alloc.
1228 If so, kick out the regs that were put there by local-alloc
1229 so we can use it instead. */
1230 if (best_reg
< 0 && !retrying
1231 /* Let's not bother with multi-reg allocnos. */
1232 && allocno
[num
].size
== 1)
1234 /* Count from the end, to find the least-used ones first. */
1235 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1237 #ifdef REG_ALLOC_ORDER
1238 int regno
= reg_alloc_order
[i
];
1243 if (local_reg_n_refs
[regno
] != 0
1244 /* Don't use a reg no good for this pseudo. */
1245 && ! TEST_HARD_REG_BIT (used2
, regno
)
1246 && HARD_REGNO_MODE_OK (regno
, mode
)
1247 /* The code below assumes that we need only a single
1248 register, but the check of allocno[num].size above
1249 was not enough. Sometimes we need more than one
1250 register for a single-word value. */
1251 && hard_regno_nregs
[regno
][mode
] == 1
1252 && (allocno
[num
].calls_crossed
== 0
1253 || accept_call_clobbered
1254 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
))
1255 #ifdef CANNOT_CHANGE_MODE_CLASS
1256 && ! invalid_mode_change_p (regno
, REGNO_REG_CLASS (regno
),
1260 && (!allocno
[num
].no_stack_reg
1261 || regno
< FIRST_STACK_REG
|| regno
> LAST_STACK_REG
)
1265 /* We explicitly evaluate the divide results into temporary
1266 variables so as to avoid excess precision problems that occur
1267 on an i386-unknown-sysv4.2 (unixware) host. */
1269 double tmp1
= ((double) local_reg_freq
[regno
]
1270 / local_reg_live_length
[regno
]);
1271 double tmp2
= ((double) allocno
[num
].freq
1272 / allocno
[num
].live_length
);
1276 /* Hard reg REGNO was used less in total by local regs
1277 than it would be used by this one allocno! */
1279 for (k
= 0; k
< max_regno
; k
++)
1280 if (reg_renumber
[k
] >= 0)
1282 int r
= reg_renumber
[k
];
1284 = r
+ hard_regno_nregs
[r
][PSEUDO_REGNO_MODE (k
)];
1286 if (regno
>= r
&& regno
< endregno
)
1287 reg_renumber
[k
] = -1;
1297 /* Did we find a register? */
1302 HARD_REG_SET this_reg
;
1304 /* Yes. Record it as the hard register of this pseudo-reg. */
1305 reg_renumber
[allocno
[num
].reg
] = best_reg
;
1306 /* Also of any pseudo-regs that share with it. */
1307 if (reg_may_share
[allocno
[num
].reg
])
1308 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1309 if (reg_allocno
[j
] == num
)
1310 reg_renumber
[j
] = best_reg
;
1312 /* Make a set of the hard regs being allocated. */
1313 CLEAR_HARD_REG_SET (this_reg
);
1314 lim
= best_reg
+ hard_regno_nregs
[best_reg
][mode
];
1315 for (j
= best_reg
; j
< lim
; j
++)
1317 SET_HARD_REG_BIT (this_reg
, j
);
1318 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1319 /* This is no longer a reg used just by local regs. */
1320 local_reg_n_refs
[j
] = 0;
1321 local_reg_freq
[j
] = 0;
1323 /* For each other pseudo-reg conflicting with this one,
1324 mark it as conflicting with the hard regs this one occupies. */
1326 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ lim
* allocno_row_words
, j
,
1328 IOR_HARD_REG_SET (allocno
[j
].hard_reg_conflicts
, this_reg
);
1333 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1334 Perhaps it had previously seemed not worth a hard reg,
1335 or perhaps its old hard reg has been commandeered for reloads.
1336 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1337 they do not appear to be allocated.
1338 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1341 retry_global_alloc (int regno
, HARD_REG_SET forbidden_regs
)
1343 int alloc_no
= reg_allocno
[regno
];
1346 /* If we have more than one register class,
1347 first try allocating in the class that is cheapest
1348 for this pseudo-reg. If that fails, try any reg. */
1349 if (N_REG_CLASSES
> 1)
1350 find_reg (alloc_no
, forbidden_regs
, 0, 0, 1);
1351 if (reg_renumber
[regno
] < 0
1352 && reg_alternate_class (regno
) != NO_REGS
)
1353 find_reg (alloc_no
, forbidden_regs
, 1, 0, 1);
1355 /* If we found a register, modify the RTL for the register to
1356 show the hard register, and mark that register live. */
1357 if (reg_renumber
[regno
] >= 0)
1359 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1360 mark_home_live (regno
);
1365 /* Record a conflict between register REGNO
1366 and everything currently live.
1367 REGNO must not be a pseudo reg that was allocated
1368 by local_alloc; such numbers must be translated through
1369 reg_renumber before calling here. */
1372 record_one_conflict (int regno
)
1376 if (regno
< FIRST_PSEUDO_REGISTER
)
1377 /* When a hard register becomes live,
1378 record conflicts with live pseudo regs. */
1379 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, j
,
1381 SET_HARD_REG_BIT (allocno
[j
].hard_reg_conflicts
, regno
);
1384 /* When a pseudo-register becomes live,
1385 record conflicts first with hard regs,
1386 then with other pseudo regs. */
1388 int ialloc
= reg_allocno
[regno
];
1389 int ialloc_prod
= ialloc
* allocno_row_words
;
1391 IOR_HARD_REG_SET (allocno
[ialloc
].hard_reg_conflicts
, hard_regs_live
);
1392 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1393 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1397 /* Record all allocnos currently live as conflicting
1398 with all hard regs currently live.
1400 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1401 are currently live. Their bits are also flagged in allocnos_live. */
1404 record_conflicts (int *allocno_vec
, int len
)
1407 IOR_HARD_REG_SET (allocno
[allocno_vec
[len
]].hard_reg_conflicts
,
1411 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1413 mirror_conflicts (void)
1416 int rw
= allocno_row_words
;
1417 int rwb
= rw
* INT_BITS
;
1418 INT_TYPE
*p
= conflicts
;
1419 INT_TYPE
*q0
= conflicts
, *q1
, *q2
;
1420 unsigned INT_TYPE mask
;
1422 for (i
= max_allocno
- 1, mask
= 1; i
>= 0; i
--, mask
<<= 1)
1429 for (j
= allocno_row_words
- 1, q1
= q0
; j
>= 0; j
--, q1
+= rwb
)
1431 unsigned INT_TYPE word
;
1433 for (word
= (unsigned INT_TYPE
) *p
++, q2
= q1
; word
;
1434 word
>>= 1, q2
+= rw
)
1443 /* Handle the case where REG is set by the insn being scanned,
1444 during the forward scan to accumulate conflicts.
1445 Store a 1 in regs_live or allocnos_live for this register, record how many
1446 consecutive hardware registers it actually needs,
1447 and record a conflict with all other registers already live.
1449 Note that even if REG does not remain alive after this insn,
1450 we must mark it here as live, to ensure a conflict between
1451 REG and any other regs set in this insn that really do live.
1452 This is because those other regs could be considered after this.
1454 REG might actually be something other than a register;
1455 if so, we do nothing.
1457 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1458 a REG_INC note was found for it). */
1461 mark_reg_store (rtx reg
, rtx setter
, void *data ATTRIBUTE_UNUSED
)
1465 if (GET_CODE (reg
) == SUBREG
)
1466 reg
= SUBREG_REG (reg
);
1468 if (GET_CODE (reg
) != REG
)
1471 regs_set
[n_regs_set
++] = reg
;
1473 if (setter
&& GET_CODE (setter
) != CLOBBER
)
1474 set_preference (reg
, SET_SRC (setter
));
1476 regno
= REGNO (reg
);
1478 /* Either this is one of the max_allocno pseudo regs not allocated,
1479 or it is or has a hardware reg. First handle the pseudo-regs. */
1480 if (regno
>= FIRST_PSEUDO_REGISTER
)
1482 if (reg_allocno
[regno
] >= 0)
1484 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1485 record_one_conflict (regno
);
1489 if (reg_renumber
[regno
] >= 0)
1490 regno
= reg_renumber
[regno
];
1492 /* Handle hardware regs (and pseudos allocated to hard regs). */
1493 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1495 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1496 while (regno
< last
)
1498 record_one_conflict (regno
);
1499 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1505 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1508 mark_reg_clobber (rtx reg
, rtx setter
, void *data
)
1510 if (GET_CODE (setter
) == CLOBBER
)
1511 mark_reg_store (reg
, setter
, data
);
1514 /* Record that REG has conflicts with all the regs currently live.
1515 Do not mark REG itself as live. */
1518 mark_reg_conflicts (rtx reg
)
1522 if (GET_CODE (reg
) == SUBREG
)
1523 reg
= SUBREG_REG (reg
);
1525 if (GET_CODE (reg
) != REG
)
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)
1535 record_one_conflict (regno
);
1538 if (reg_renumber
[regno
] >= 0)
1539 regno
= reg_renumber
[regno
];
1541 /* Handle hardware regs (and pseudos allocated to hard regs). */
1542 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1544 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1545 while (regno
< last
)
1547 record_one_conflict (regno
);
1553 /* Mark REG as being dead (following the insn being scanned now).
1554 Store a 0 in regs_live or allocnos_live for this register. */
1557 mark_reg_death (rtx reg
)
1559 int regno
= REGNO (reg
);
1561 /* Either this is one of the max_allocno pseudo regs not allocated,
1562 or it is a hardware reg. First handle the pseudo-regs. */
1563 if (regno
>= FIRST_PSEUDO_REGISTER
)
1565 if (reg_allocno
[regno
] >= 0)
1566 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1569 /* For pseudo reg, see if it has been assigned a hardware reg. */
1570 if (reg_renumber
[regno
] >= 0)
1571 regno
= reg_renumber
[regno
];
1573 /* Handle hardware regs (and pseudos allocated to hard regs). */
1574 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1576 /* Pseudo regs already assigned hardware regs are treated
1577 almost the same as explicit hardware regs. */
1578 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1579 while (regno
< last
)
1581 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1587 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1588 for the value stored in it. MODE determines how many consecutive
1589 registers are actually in use. Do not record conflicts;
1590 it is assumed that the caller will do that. */
1593 mark_reg_live_nc (int regno
, enum machine_mode mode
)
1595 int last
= regno
+ hard_regno_nregs
[regno
][mode
];
1596 while (regno
< last
)
1598 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1603 /* Try to set a preference for an allocno to a hard register.
1604 We are passed DEST and SRC which are the operands of a SET. It is known
1605 that SRC is a register. If SRC or the first operand of SRC is a register,
1606 try to set a preference. If one of the two is a hard register and the other
1607 is a pseudo-register, mark the preference.
1609 Note that we are not as aggressive as local-alloc in trying to tie a
1610 pseudo-register to a hard register. */
1613 set_preference (rtx dest
, rtx src
)
1615 unsigned int src_regno
, dest_regno
;
1616 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1617 to compensate for subregs in SRC or DEST. */
1622 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1623 src
= XEXP (src
, 0), copy
= 0;
1625 /* Get the reg number for both SRC and DEST.
1626 If neither is a reg, give up. */
1628 if (GET_CODE (src
) == REG
)
1629 src_regno
= REGNO (src
);
1630 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1632 src_regno
= REGNO (SUBREG_REG (src
));
1634 if (REGNO (SUBREG_REG (src
)) < FIRST_PSEUDO_REGISTER
)
1635 offset
+= subreg_regno_offset (REGNO (SUBREG_REG (src
)),
1636 GET_MODE (SUBREG_REG (src
)),
1640 offset
+= (SUBREG_BYTE (src
)
1641 / REGMODE_NATURAL_SIZE (GET_MODE (src
)));
1646 if (GET_CODE (dest
) == REG
)
1647 dest_regno
= REGNO (dest
);
1648 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1650 dest_regno
= REGNO (SUBREG_REG (dest
));
1652 if (REGNO (SUBREG_REG (dest
)) < FIRST_PSEUDO_REGISTER
)
1653 offset
-= subreg_regno_offset (REGNO (SUBREG_REG (dest
)),
1654 GET_MODE (SUBREG_REG (dest
)),
1658 offset
-= (SUBREG_BYTE (dest
)
1659 / REGMODE_NATURAL_SIZE (GET_MODE (dest
)));
1664 /* Convert either or both to hard reg numbers. */
1666 if (reg_renumber
[src_regno
] >= 0)
1667 src_regno
= reg_renumber
[src_regno
];
1669 if (reg_renumber
[dest_regno
] >= 0)
1670 dest_regno
= reg_renumber
[dest_regno
];
1672 /* Now if one is a hard reg and the other is a global pseudo
1673 then give the other a preference. */
1675 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1676 && reg_allocno
[src_regno
] >= 0)
1678 dest_regno
-= offset
;
1679 if (dest_regno
< FIRST_PSEUDO_REGISTER
)
1682 SET_REGBIT (hard_reg_copy_preferences
,
1683 reg_allocno
[src_regno
], dest_regno
);
1685 SET_REGBIT (hard_reg_preferences
,
1686 reg_allocno
[src_regno
], dest_regno
);
1687 for (i
= dest_regno
;
1688 i
< dest_regno
+ hard_regno_nregs
[dest_regno
][GET_MODE (dest
)];
1690 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1694 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1695 && reg_allocno
[dest_regno
] >= 0)
1697 src_regno
+= offset
;
1698 if (src_regno
< FIRST_PSEUDO_REGISTER
)
1701 SET_REGBIT (hard_reg_copy_preferences
,
1702 reg_allocno
[dest_regno
], src_regno
);
1704 SET_REGBIT (hard_reg_preferences
,
1705 reg_allocno
[dest_regno
], src_regno
);
1707 i
< src_regno
+ hard_regno_nregs
[src_regno
][GET_MODE (src
)];
1709 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1714 /* Indicate that hard register number FROM was eliminated and replaced with
1715 an offset from hard register number TO. The status of hard registers live
1716 at the start of a basic block is updated by replacing a use of FROM with
1720 mark_elimination (int from
, int to
)
1726 regset r
= bb
->global_live_at_start
;
1727 if (REGNO_REG_SET_P (r
, from
))
1729 CLEAR_REGNO_REG_SET (r
, from
);
1730 SET_REGNO_REG_SET (r
, to
);
1735 /* Used for communication between the following functions. Holds the
1736 current life information. */
1737 static regset live_relevant_regs
;
1739 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1740 This is called via note_stores. */
1742 reg_becomes_live (rtx reg
, rtx setter ATTRIBUTE_UNUSED
, void *regs_set
)
1746 if (GET_CODE (reg
) == SUBREG
)
1747 reg
= SUBREG_REG (reg
);
1749 if (GET_CODE (reg
) != REG
)
1752 regno
= REGNO (reg
);
1753 if (regno
< FIRST_PSEUDO_REGISTER
)
1755 int nregs
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1758 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1759 if (! fixed_regs
[regno
])
1760 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1764 else if (reg_renumber
[regno
] >= 0)
1766 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1767 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1771 /* Record in live_relevant_regs that register REGNO died. */
1773 reg_dies (int regno
, enum machine_mode mode
, struct insn_chain
*chain
)
1775 if (regno
< FIRST_PSEUDO_REGISTER
)
1777 int nregs
= hard_regno_nregs
[regno
][mode
];
1780 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1781 if (! fixed_regs
[regno
])
1782 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1788 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1789 if (reg_renumber
[regno
] >= 0)
1790 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1794 /* Walk the insns of the current function and build reload_insn_chain,
1795 and record register life information. */
1797 build_insn_chain (rtx first
)
1799 struct insn_chain
**p
= &reload_insn_chain
;
1800 struct insn_chain
*prev
= 0;
1801 basic_block b
= ENTRY_BLOCK_PTR
->next_bb
;
1802 regset_head live_relevant_regs_head
;
1804 live_relevant_regs
= INITIALIZE_REG_SET (live_relevant_regs_head
);
1806 for (; first
; first
= NEXT_INSN (first
))
1808 struct insn_chain
*c
;
1810 if (first
== BB_HEAD (b
))
1814 CLEAR_REG_SET (live_relevant_regs
);
1816 EXECUTE_IF_SET_IN_BITMAP
1817 (b
->global_live_at_start
, 0, i
,
1819 if (i
< FIRST_PSEUDO_REGISTER
1820 ? ! TEST_HARD_REG_BIT (eliminable_regset
, i
)
1821 : reg_renumber
[i
] >= 0)
1822 SET_REGNO_REG_SET (live_relevant_regs
, i
);
1826 if (GET_CODE (first
) != NOTE
&& GET_CODE (first
) != BARRIER
)
1828 c
= new_insn_chain ();
1834 c
->block
= b
->index
;
1840 /* Mark the death of everything that dies in this instruction. */
1842 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1843 if (REG_NOTE_KIND (link
) == REG_DEAD
1844 && GET_CODE (XEXP (link
, 0)) == REG
)
1845 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1848 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1850 /* Mark everything born in this instruction as live. */
1852 note_stores (PATTERN (first
), reg_becomes_live
,
1856 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1862 /* Mark anything that is set in this insn and then unused as dying. */
1864 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1865 if (REG_NOTE_KIND (link
) == REG_UNUSED
1866 && GET_CODE (XEXP (link
, 0)) == REG
)
1867 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1872 if (first
== BB_END (b
))
1875 /* Stop after we pass the end of the last basic block. Verify that
1876 no real insns are after the end of the last basic block.
1878 We may want to reorganize the loop somewhat since this test should
1879 always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if
1880 the previous real insn is a JUMP_INSN. */
1881 if (b
== EXIT_BLOCK_PTR
)
1883 for (first
= NEXT_INSN (first
) ; first
; first
= NEXT_INSN (first
))
1885 && GET_CODE (PATTERN (first
)) != USE
1886 && ! ((GET_CODE (PATTERN (first
)) == ADDR_VEC
1887 || GET_CODE (PATTERN (first
)) == ADDR_DIFF_VEC
)
1888 && prev_real_insn (first
) != 0
1889 && GET_CODE (prev_real_insn (first
)) == JUMP_INSN
))
1894 FREE_REG_SET (live_relevant_regs
);
1898 /* Print debugging trace information if -dg switch is given,
1899 showing the information on which the allocation decisions are based. */
1902 dump_conflicts (FILE *file
)
1905 int has_preferences
;
1908 for (i
= 0; i
< max_allocno
; i
++)
1910 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1914 fprintf (file
, ";; %d regs to allocate:", nregs
);
1915 for (i
= 0; i
< max_allocno
; i
++)
1918 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1920 fprintf (file
, " %d", allocno
[allocno_order
[i
]].reg
);
1921 for (j
= 0; j
< max_regno
; j
++)
1922 if (reg_allocno
[j
] == allocno_order
[i
]
1923 && j
!= allocno
[allocno_order
[i
]].reg
)
1924 fprintf (file
, "+%d", j
);
1925 if (allocno
[allocno_order
[i
]].size
!= 1)
1926 fprintf (file
, " (%d)", allocno
[allocno_order
[i
]].size
);
1928 fprintf (file
, "\n");
1930 for (i
= 0; i
< max_allocno
; i
++)
1933 fprintf (file
, ";; %d conflicts:", allocno
[i
].reg
);
1934 for (j
= 0; j
< max_allocno
; j
++)
1935 if (CONFLICTP (j
, i
))
1936 fprintf (file
, " %d", allocno
[j
].reg
);
1937 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1938 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_conflicts
, j
))
1939 fprintf (file
, " %d", j
);
1940 fprintf (file
, "\n");
1942 has_preferences
= 0;
1943 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1944 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1945 has_preferences
= 1;
1947 if (! has_preferences
)
1949 fprintf (file
, ";; %d preferences:", allocno
[i
].reg
);
1950 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1951 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1952 fprintf (file
, " %d", j
);
1953 fprintf (file
, "\n");
1955 fprintf (file
, "\n");
1959 dump_global_regs (FILE *file
)
1963 fprintf (file
, ";; Register dispositions:\n");
1964 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1965 if (reg_renumber
[i
] >= 0)
1967 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1969 fprintf (file
, "\n");
1972 fprintf (file
, "\n\n;; Hard regs used: ");
1973 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1974 if (regs_ever_live
[i
])
1975 fprintf (file
, " %d", i
);
1976 fprintf (file
, "\n\n");
1981 /* This page contains code to make live information more accurate.
1982 The accurate register liveness at program point P means:
1983 o there is a path from P to usage of the register and the
1984 register is not redefined or killed on the path.
1985 o register at P is partially available, i.e. there is a path from
1986 a register definition to the point P and the register is not
1987 killed (clobbered) on the path
1989 The standard GCC live information means only the first condition.
1990 Without the partial availability, there will be more register
1991 conflicts and as a consequence worse register allocation. The
1992 typical example where the information can be different is a
1993 register initialized in the loop at the basic block preceding the
1996 /* The following structure contains basic block data flow information
1997 used to calculate partial availability of registers. */
2001 /* The basic block reverse post-order number. */
2003 /* Registers correspondingly killed (clobbered) and defined but not
2004 killed afterward in the basic block. */
2005 bitmap killed
, avloc
;
2006 /* Registers partially available correspondingly at the start and
2007 end of the basic block. */
2008 bitmap pavin
, pavout
;
2011 /* Macros for accessing data flow information of basic blocks. */
2013 #define BB_INFO(BB) ((struct bb_info *) (BB)->aux)
2014 #define BB_INFO_BY_INDEX(N) BB_INFO (BASIC_BLOCK(N))
2016 /* The function allocates the info structures of each basic block. It
2017 also initialized PAVIN and PAVOUT as if all hard registers were
2018 partially available. */
2021 allocate_bb_info (void)
2025 struct bb_info
*bb_info
;
2028 alloc_aux_for_blocks (sizeof (struct bb_info
));
2029 init
= BITMAP_XMALLOC ();
2030 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2031 bitmap_set_bit (init
, i
);
2035 bb_info
->avloc
= BITMAP_XMALLOC ();
2036 bb_info
->killed
= BITMAP_XMALLOC ();
2037 bb_info
->pavin
= BITMAP_XMALLOC ();
2038 bb_info
->pavout
= BITMAP_XMALLOC ();
2039 bitmap_copy (bb_info
->pavin
, init
);
2040 bitmap_copy (bb_info
->pavout
, init
);
2042 BITMAP_XFREE (init
);
2045 /* The function frees the allocated info of all basic blocks. */
2051 struct bb_info
*bb_info
;
2055 bb_info
= BB_INFO (bb
);
2056 BITMAP_XFREE (bb_info
->pavout
);
2057 BITMAP_XFREE (bb_info
->pavin
);
2058 BITMAP_XFREE (bb_info
->killed
);
2059 BITMAP_XFREE (bb_info
->avloc
);
2061 free_aux_for_blocks ();
2064 /* The function modifies local info for register REG being changed in
2065 SETTER. DATA is used to pass the current basic block info. */
2068 mark_reg_change (rtx reg
, rtx setter
, void *data
)
2071 basic_block bb
= data
;
2072 struct bb_info
*bb_info
= BB_INFO (bb
);
2074 if (GET_CODE (reg
) == SUBREG
)
2075 reg
= SUBREG_REG (reg
);
2077 if (GET_CODE (reg
) != REG
)
2080 regno
= REGNO (reg
);
2081 bitmap_set_bit (bb_info
->killed
, regno
);
2083 if (GET_CODE (setter
) != CLOBBER
)
2084 bitmap_set_bit (bb_info
->avloc
, regno
);
2086 bitmap_clear_bit (bb_info
->avloc
, regno
);
2089 /* The function calculates local info for each basic block. */
2092 calculate_local_reg_bb_info (void)
2099 bound
= NEXT_INSN (BB_END (bb
));
2100 for (insn
= BB_HEAD (bb
); insn
!= bound
; insn
= NEXT_INSN (insn
))
2102 note_stores (PATTERN (insn
), mark_reg_change
, bb
);
2106 /* The function sets up reverse post-order number of each basic
2110 set_up_bb_rts_numbers (void)
2115 rts_order
= xmalloc (sizeof (int) * n_basic_blocks
);
2116 flow_reverse_top_sort_order_compute (rts_order
);
2117 for (i
= 0; i
< n_basic_blocks
; i
++)
2118 BB_INFO_BY_INDEX (rts_order
[i
])->rts_number
= i
;
2122 /* Compare function for sorting blocks in reverse postorder. */
2125 rpost_cmp (const void *bb1
, const void *bb2
)
2127 basic_block b1
= *(basic_block
*) bb1
, b2
= *(basic_block
*) bb2
;
2129 return BB_INFO (b2
)->rts_number
- BB_INFO (b1
)->rts_number
;
2132 /* The function calculates partial availability of registers. The
2133 function calculates partial availability at the end of basic block
2134 BB by propagating partial availability at end of predecessor basic
2135 block PRED. The function returns true if the partial availability
2136 at the end of BB has been changed or if CHANGED_P. We have the
2137 following equations:
2139 bb.pavin = empty for entry block | union (pavout of predecessors)
2140 bb.pavout = union (bb.pavin - b.killed, bb.avloc) */
2143 modify_bb_reg_pav (basic_block bb
, basic_block pred
, bool changed_p
)
2145 struct bb_info
*bb_info
;
2146 bitmap bb_pavin
, bb_pavout
;
2148 bb_info
= BB_INFO (bb
);
2149 bb_pavin
= bb_info
->pavin
;
2150 bb_pavout
= bb_info
->pavout
;
2151 if (pred
->index
!= ENTRY_BLOCK
)
2152 bitmap_a_or_b (bb_pavin
, bb_pavin
, BB_INFO (pred
)->pavout
);
2153 changed_p
|= bitmap_union_of_diff (bb_pavout
, bb_info
->avloc
,
2154 bb_pavin
, bb_info
->killed
);
2158 /* The function calculates partial register availability. */
2161 calculate_reg_pav (void)
2163 basic_block bb
, succ
;
2167 varray_type bbs
, new_bbs
, temp
;
2168 basic_block
*bb_array
;
2171 VARRAY_BB_INIT (bbs
, n_basic_blocks
, "basic blocks");
2172 VARRAY_BB_INIT (new_bbs
, n_basic_blocks
, "basic blocks for the next iter.");
2175 VARRAY_PUSH_BB (bbs
, bb
);
2177 wset
= sbitmap_alloc (n_basic_blocks
+ 1);
2178 while (VARRAY_ACTIVE_SIZE (bbs
))
2180 bb_array
= &VARRAY_BB (bbs
, 0);
2181 nel
= VARRAY_ACTIVE_SIZE (bbs
);
2182 qsort (bb_array
, nel
, sizeof (basic_block
), rpost_cmp
);
2183 sbitmap_zero (wset
);
2184 for (i
= 0; i
< nel
; i
++)
2188 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
2189 changed_p
= modify_bb_reg_pav (bb
, e
->src
, changed_p
);
2191 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
2194 if (succ
->index
!= EXIT_BLOCK
&& !TEST_BIT (wset
, succ
->index
))
2196 SET_BIT (wset
, succ
->index
);
2197 VARRAY_PUSH_BB (new_bbs
, succ
);
2204 VARRAY_POP_ALL (new_bbs
);
2206 sbitmap_free (wset
);
2209 /* The following function makes live information more accurate by
2210 modifying global_live_at_start and global_live_at_end of basic
2211 blocks. After the function call a register lives at a program
2212 point only if it is initialized on a path from CFG entry to the
2213 program point. The standard GCC life analysis permits registers to
2214 live uninitialized. */
2217 make_accurate_live_analysis (void)
2220 struct bb_info
*bb_info
;
2222 max_regno
= max_reg_num ();
2224 allocate_bb_info ();
2225 calculate_local_reg_bb_info ();
2226 set_up_bb_rts_numbers ();
2227 calculate_reg_pav ();
2230 bb_info
= BB_INFO (bb
);
2232 bitmap_a_and_b (bb
->global_live_at_start
, bb
->global_live_at_start
,
2234 bitmap_a_and_b (bb
->global_live_at_end
, bb
->global_live_at_end
,