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, 2007 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 3, 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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
27 #include "hard-reg-set.h"
33 #include "insn-config.h"
38 #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 calls that might throw crossed by each allocno. */
101 int throwing_calls_crossed
;
103 /* Number of refs to each allocno. */
106 /* Frequency of uses of each allocno. */
109 /* Guess at live length of each allocno.
110 This is actually the max of the live lengths of the regs. */
113 /* Set of hard regs conflicting with allocno N. */
115 HARD_REG_SET hard_reg_conflicts
;
117 /* Set of hard regs preferred by allocno N.
118 This is used to make allocnos go into regs that are copied to or from them,
119 when possible, to reduce register shuffling. */
121 HARD_REG_SET hard_reg_preferences
;
123 /* Similar, but just counts register preferences made in simple copy
124 operations, rather than arithmetic. These are given priority because
125 we can always eliminate an insn by using these, but using a register
126 in the above list won't always eliminate an insn. */
128 HARD_REG_SET hard_reg_copy_preferences
;
130 /* Similar to hard_reg_preferences, but includes bits for subsequent
131 registers when an allocno is multi-word. The above variable is used for
132 allocation while this is used to build reg_someone_prefers, below. */
134 HARD_REG_SET hard_reg_full_preferences
;
136 /* Set of hard registers that some later allocno has a preference for. */
138 HARD_REG_SET regs_someone_prefers
;
141 /* Set to true if allocno can't be allocated in the stack register. */
146 static struct allocno
*allocno
;
148 /* A vector of the integers from 0 to max_allocno-1,
149 sorted in the order of first-to-be-allocated first. */
151 static int *allocno_order
;
153 /* Indexed by (pseudo) reg number, gives the number of another
154 lower-numbered pseudo reg which can share a hard reg with this pseudo
155 *even if the two pseudos would otherwise appear to conflict*. */
157 static int *reg_may_share
;
159 /* Define the number of bits in each element of `conflicts' and what
160 type that element has. We use the largest integer format on the
163 #define INT_BITS HOST_BITS_PER_WIDE_INT
164 #define INT_TYPE HOST_WIDE_INT
166 /* max_allocno by max_allocno array of bits,
167 recording whether two allocno's conflict (can't go in the same
170 `conflicts' is symmetric after the call to mirror_conflicts. */
172 static INT_TYPE
*conflicts
;
174 /* Number of ints required to hold max_allocno bits.
175 This is the length of a row in `conflicts'. */
177 static int allocno_row_words
;
179 /* Two macros to test or store 1 in an element of `conflicts'. */
181 #define CONFLICTP(I, J) \
182 (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS] \
183 & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS)))
185 /* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
187 #define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
191 INT_TYPE *p_ = (ALLOCNO_SET); \
193 for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
194 i_--, allocno_ += INT_BITS) \
196 unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
198 for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
206 /* This doesn't work for non-GNU C due to the way CODE is macro expanded. */
208 /* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to
209 the conflicting allocno, and execute CODE. This macro assumes that
210 mirror_conflicts has been run. */
211 #define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\
212 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\
216 /* Set of hard regs currently live (during scan of all insns). */
218 static HARD_REG_SET hard_regs_live
;
220 /* Set of registers that global-alloc isn't supposed to use. */
222 static HARD_REG_SET no_global_alloc_regs
;
224 /* Set of registers used so far. */
226 static HARD_REG_SET regs_used_so_far
;
228 /* Number of refs to each hard reg, as used by local alloc.
229 It is zero for a reg that contains global pseudos or is explicitly used. */
231 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
233 /* Frequency of uses of given hard reg. */
234 static int local_reg_freq
[FIRST_PSEUDO_REGISTER
];
236 /* Guess at live length of each hard reg, as used by local alloc.
237 This is actually the sum of the live lengths of the specific regs. */
239 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
241 /* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
242 element I, and hard register number J. */
244 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
246 /* Bit mask for allocnos live at current point in the scan. */
248 static INT_TYPE
*allocnos_live
;
250 /* Test, set or clear bit number I in allocnos_live,
251 a bit vector indexed by allocno. */
253 #define SET_ALLOCNO_LIVE(I) \
254 (allocnos_live[(unsigned) (I) / INT_BITS] \
255 |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
257 #define CLEAR_ALLOCNO_LIVE(I) \
258 (allocnos_live[(unsigned) (I) / INT_BITS] \
259 &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
261 /* This is turned off because it doesn't work right for DImode.
262 (And it is only used for DImode, so the other cases are worthless.)
263 The problem is that it isn't true that there is NO possibility of conflict;
264 only that there is no conflict if the two pseudos get the exact same regs.
265 If they were allocated with a partial overlap, there would be a conflict.
266 We can't safely turn off the conflict unless we have another way to
267 prevent the partial overlap.
269 Idea: change hard_reg_conflicts so that instead of recording which
270 hard regs the allocno may not overlap, it records where the allocno
271 may not start. Change both where it is used and where it is updated.
272 Then there is a way to record that (reg:DI 108) may start at 10
273 but not at 9 or 11. There is still the question of how to record
274 this semi-conflict between two pseudos. */
276 /* Reg pairs for which conflict after the current insn
277 is inhibited by a REG_NO_CONFLICT note.
278 If the table gets full, we ignore any other notes--that is conservative. */
279 #define NUM_NO_CONFLICT_PAIRS 4
280 /* Number of pairs in use in this insn. */
281 int n_no_conflict_pairs
;
282 static struct { int allocno1
, allocno2
;}
283 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
286 /* Record all regs that are set in any one insn.
287 Communication from mark_reg_{store,clobber} and global_conflicts. */
289 static rtx
*regs_set
;
290 static int n_regs_set
;
292 /* All registers that can be eliminated. */
294 static HARD_REG_SET eliminable_regset
;
296 static int allocno_compare (const void *, const void *);
297 static void global_conflicts (void);
298 static void mirror_conflicts (void);
299 static void expand_preferences (void);
300 static void prune_preferences (void);
301 static void find_reg (int, HARD_REG_SET
, int, int, int);
302 static void record_one_conflict (int);
303 static void record_conflicts (int *, int);
304 static void mark_reg_store (rtx
, rtx
, void *);
305 static void mark_reg_clobber (rtx
, rtx
, void *);
306 static void mark_reg_conflicts (rtx
);
307 static void mark_reg_death (rtx
);
308 static void mark_reg_live_nc (int, enum machine_mode
);
309 static void set_preference (rtx
, rtx
);
310 static void dump_conflicts (FILE *);
311 static void reg_becomes_live (rtx
, rtx
, void *);
312 static void reg_dies (int, enum machine_mode
, struct insn_chain
*);
314 static void allocate_bb_info (void);
315 static void free_bb_info (void);
316 static bool check_earlyclobber (rtx
);
317 static void mark_reg_use_for_earlyclobber_1 (rtx
*, void *);
318 static int mark_reg_use_for_earlyclobber (rtx
*, void *);
319 static void calculate_local_reg_bb_info (void);
320 static void set_up_bb_rts_numbers (void);
321 static int rpost_cmp (const void *, const void *);
322 static void calculate_reg_pav (void);
323 static void modify_reg_pav (void);
324 static void make_accurate_live_analysis (void);
328 /* Perform allocation of pseudo-registers not allocated by local_alloc.
330 Return value is nonzero if reload failed
331 and we must not do any more for this function. */
337 #ifdef ELIMINABLE_REGS
338 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
341 = (! flag_omit_frame_pointer
342 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
343 || FRAME_POINTER_REQUIRED
);
348 make_accurate_live_analysis ();
352 /* A machine may have certain hard registers that
353 are safe to use only within a basic block. */
355 CLEAR_HARD_REG_SET (no_global_alloc_regs
);
357 /* Build the regset of all eliminable registers and show we can't use those
358 that we already know won't be eliminated. */
359 #ifdef ELIMINABLE_REGS
360 for (i
= 0; i
< ARRAY_SIZE (eliminables
); i
++)
363 = (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
364 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
));
366 if (!regs_asm_clobbered
[eliminables
[i
].from
])
368 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
371 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
373 else if (cannot_elim
)
374 error ("%s cannot be used in asm here",
375 reg_names
[eliminables
[i
].from
]);
377 regs_ever_live
[eliminables
[i
].from
] = 1;
379 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
380 if (!regs_asm_clobbered
[HARD_FRAME_POINTER_REGNUM
])
382 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
384 SET_HARD_REG_BIT (no_global_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
387 error ("%s cannot be used in asm here",
388 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
390 regs_ever_live
[HARD_FRAME_POINTER_REGNUM
] = 1;
394 if (!regs_asm_clobbered
[FRAME_POINTER_REGNUM
])
396 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
398 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
401 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
403 regs_ever_live
[FRAME_POINTER_REGNUM
] = 1;
406 /* Track which registers have already been used. Start with registers
407 explicitly in the rtl, then registers allocated by local register
410 CLEAR_HARD_REG_SET (regs_used_so_far
);
411 #ifdef LEAF_REGISTERS
412 /* If we are doing the leaf function optimization, and this is a leaf
413 function, it means that the registers that take work to save are those
414 that need a register window. So prefer the ones that can be used in
417 const char *cheap_regs
;
418 const char *const leaf_regs
= LEAF_REGISTERS
;
420 if (only_leaf_regs_used () && leaf_function_p ())
421 cheap_regs
= leaf_regs
;
423 cheap_regs
= call_used_regs
;
424 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
425 if (regs_ever_live
[i
] || cheap_regs
[i
])
426 SET_HARD_REG_BIT (regs_used_so_far
, i
);
429 /* We consider registers that do not have to be saved over calls as if
430 they were already used since there is no cost in using them. */
431 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
432 if (regs_ever_live
[i
] || call_used_regs
[i
])
433 SET_HARD_REG_BIT (regs_used_so_far
, i
);
436 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
437 if (reg_renumber
[i
] >= 0)
438 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
440 /* Establish mappings from register number to allocation number
441 and vice versa. In the process, count the allocnos. */
443 reg_allocno
= XNEWVEC (int, max_regno
);
445 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
448 /* Initialize the shared-hard-reg mapping
449 from the list of pairs that may share. */
450 reg_may_share
= XCNEWVEC (int, max_regno
);
451 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
453 int r1
= REGNO (XEXP (x
, 0));
454 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
456 reg_may_share
[r1
] = r2
;
458 reg_may_share
[r2
] = r1
;
461 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
462 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
463 that we are supposed to refrain from putting in a hard reg.
464 -2 means do make an allocno but don't allocate it. */
465 if (REG_N_REFS (i
) != 0 && REG_LIVE_LENGTH (i
) != -1
466 /* Don't allocate pseudos that cross calls,
467 if this function receives a nonlocal goto. */
468 && (! current_function_has_nonlocal_label
469 || REG_N_CALLS_CROSSED (i
) == 0))
471 if (reg_renumber
[i
] < 0
472 && reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
473 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
475 reg_allocno
[i
] = max_allocno
++;
476 gcc_assert (REG_LIVE_LENGTH (i
));
481 allocno
= XCNEWVEC (struct allocno
, max_allocno
);
483 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
484 if (reg_allocno
[i
] >= 0)
486 int num
= reg_allocno
[i
];
487 allocno
[num
].reg
= i
;
488 allocno
[num
].size
= PSEUDO_REGNO_SIZE (i
);
489 allocno
[num
].calls_crossed
+= REG_N_CALLS_CROSSED (i
);
490 allocno
[num
].throwing_calls_crossed
491 += REG_N_THROWING_CALLS_CROSSED (i
);
492 allocno
[num
].n_refs
+= REG_N_REFS (i
);
493 allocno
[num
].freq
+= REG_FREQ (i
);
494 if (allocno
[num
].live_length
< REG_LIVE_LENGTH (i
))
495 allocno
[num
].live_length
= REG_LIVE_LENGTH (i
);
498 /* Calculate amount of usage of each hard reg by pseudos
499 allocated by local-alloc. This is to see if we want to
501 memset (local_reg_live_length
, 0, sizeof local_reg_live_length
);
502 memset (local_reg_n_refs
, 0, sizeof local_reg_n_refs
);
503 memset (local_reg_freq
, 0, sizeof local_reg_freq
);
504 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
505 if (reg_renumber
[i
] >= 0)
507 int regno
= reg_renumber
[i
];
508 int endregno
= regno
+ hard_regno_nregs
[regno
][PSEUDO_REGNO_MODE (i
)];
511 for (j
= regno
; j
< endregno
; j
++)
513 local_reg_n_refs
[j
] += REG_N_REFS (i
);
514 local_reg_freq
[j
] += REG_FREQ (i
);
515 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
519 /* We can't override local-alloc for a reg used not just by local-alloc. */
520 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
521 if (regs_ever_live
[i
])
522 local_reg_n_refs
[i
] = 0, local_reg_freq
[i
] = 0;
524 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
526 /* We used to use alloca here, but the size of what it would try to
527 allocate would occasionally cause it to exceed the stack limit and
528 cause unpredictable core dumps. Some examples were > 2Mb in size. */
529 conflicts
= XCNEWVEC (INT_TYPE
, max_allocno
* allocno_row_words
);
531 allocnos_live
= XNEWVEC (INT_TYPE
, allocno_row_words
);
533 /* If there is work to be done (at least one reg to allocate),
534 perform global conflict analysis and allocate the regs. */
538 /* Scan all the insns and compute the conflicts among allocnos
539 and between allocnos and hard regs. */
545 /* Eliminate conflicts between pseudos and eliminable registers. If
546 the register is not eliminated, the pseudo won't really be able to
547 live in the eliminable register, so the conflict doesn't matter.
548 If we do eliminate the register, the conflict will no longer exist.
549 So in either case, we can ignore the conflict. Likewise for
552 for (i
= 0; i
< (size_t) max_allocno
; i
++)
554 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_conflicts
,
556 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_copy_preferences
,
558 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_preferences
,
562 /* Try to expand the preferences by merging them between allocnos. */
564 expand_preferences ();
566 /* Determine the order to allocate the remaining pseudo registers. */
568 allocno_order
= XNEWVEC (int, max_allocno
);
569 for (i
= 0; i
< (size_t) max_allocno
; i
++)
570 allocno_order
[i
] = i
;
572 /* Default the size to 1, since allocno_compare uses it to divide by.
573 Also convert allocno_live_length of zero to -1. A length of zero
574 can occur when all the registers for that allocno have reg_live_length
575 equal to -2. In this case, we want to make an allocno, but not
576 allocate it. So avoid the divide-by-zero and set it to a low
579 for (i
= 0; i
< (size_t) max_allocno
; i
++)
581 if (allocno
[i
].size
== 0)
583 if (allocno
[i
].live_length
== 0)
584 allocno
[i
].live_length
= -1;
587 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
589 prune_preferences ();
592 dump_conflicts (dump_file
);
594 /* Try allocating them, one by one, in that order,
595 except for parameters marked with reg_live_length[regno] == -2. */
597 for (i
= 0; i
< (size_t) max_allocno
; i
++)
598 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] < 0
599 && REG_LIVE_LENGTH (allocno
[allocno_order
[i
]].reg
) >= 0)
601 /* If we have more than one register class,
602 first try allocating in the class that is cheapest
603 for this pseudo-reg. If that fails, try any reg. */
604 if (N_REG_CLASSES
> 1)
606 find_reg (allocno_order
[i
], 0, 0, 0, 0);
607 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
610 if (reg_alternate_class (allocno
[allocno_order
[i
]].reg
) != NO_REGS
)
611 find_reg (allocno_order
[i
], 0, 1, 0, 0);
614 free (allocno_order
);
617 /* Do the reloads now while the allocno data still exists, so that we can
618 try to assign new hard regs to any pseudo regs that are spilled. */
620 #if 0 /* We need to eliminate regs even if there is no rtl code,
621 for the sake of debugging information. */
622 if (n_basic_blocks
> NUM_FIXED_BLOCKS
)
625 build_insn_chain (get_insns ());
626 retval
= reload (get_insns (), 1);
631 free (reg_may_share
);
634 free (allocnos_live
);
639 /* Sort predicate for ordering the allocnos.
640 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
643 allocno_compare (const void *v1p
, const void *v2p
)
645 int v1
= *(const int *)v1p
, v2
= *(const int *)v2p
;
646 /* Note that the quotient will never be bigger than
647 the value of floor_log2 times the maximum number of
648 times a register can occur in one insn (surely less than 100)
649 weighted by the frequency (maximally REG_FREQ_MAX).
650 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
652 = (((double) (floor_log2 (allocno
[v1
].n_refs
) * allocno
[v1
].freq
)
653 / allocno
[v1
].live_length
)
654 * (10000 / REG_FREQ_MAX
) * allocno
[v1
].size
);
656 = (((double) (floor_log2 (allocno
[v2
].n_refs
) * allocno
[v2
].freq
)
657 / allocno
[v2
].live_length
)
658 * (10000 / REG_FREQ_MAX
) * allocno
[v2
].size
);
662 /* If regs are equally good, sort by allocno,
663 so that the results of qsort leave nothing to chance. */
667 /* Scan the rtl code and record all conflicts and register preferences in the
668 conflict matrices and preference tables. */
671 global_conflicts (void)
676 int *block_start_allocnos
;
678 /* Make a vector that mark_reg_{store,clobber} will store in. */
679 regs_set
= XNEWVEC (rtx
, max_parallel
* 2);
681 block_start_allocnos
= XNEWVEC (int, max_allocno
);
685 memset (allocnos_live
, 0, allocno_row_words
* sizeof (INT_TYPE
));
687 /* Initialize table of registers currently live
688 to the state at the beginning of this basic block.
689 This also marks the conflicts among hard registers
690 and any allocnos that are live.
692 For pseudo-regs, there is only one bit for each one
693 no matter how many hard regs it occupies.
694 This is ok; we know the size from PSEUDO_REGNO_SIZE.
695 For explicit hard regs, we cannot know the size that way
696 since one hard reg can be used with various sizes.
697 Therefore, we must require that all the hard regs
698 implicitly live as part of a multi-word hard reg
699 be explicitly marked in basic_block_live_at_start. */
702 regset old
= b
->il
.rtl
->global_live_at_start
;
704 reg_set_iterator rsi
;
706 REG_SET_TO_HARD_REG_SET (hard_regs_live
, old
);
707 EXECUTE_IF_SET_IN_REG_SET (old
, FIRST_PSEUDO_REGISTER
, i
, rsi
)
709 int a
= reg_allocno
[i
];
712 SET_ALLOCNO_LIVE (a
);
713 block_start_allocnos
[ax
++] = a
;
715 else if ((a
= reg_renumber
[i
]) >= 0)
716 mark_reg_live_nc (a
, PSEUDO_REGNO_MODE (i
));
719 /* Record that each allocno now live conflicts with each hard reg
722 It is not necessary to mark any conflicts between pseudos at
723 this point, even for pseudos which are live at the start of
726 Given two pseudos X and Y and any point in the CFG P.
728 On any path to point P where X and Y are live one of the
729 following conditions must be true:
731 1. X is live at some instruction on the path that
734 2. Y is live at some instruction on the path that
737 3. Either X or Y is not evaluated on the path to P
738 (i.e. it is used uninitialized) and thus the
739 conflict can be ignored.
741 In cases #1 and #2 the conflict will be recorded when we
742 scan the instruction that makes either X or Y become live. */
743 record_conflicts (block_start_allocnos
, ax
);
745 #ifdef EH_RETURN_DATA_REGNO
746 if (bb_has_eh_pred (b
))
752 unsigned int regno
= EH_RETURN_DATA_REGNO (i
);
753 if (regno
== INVALID_REGNUM
)
755 record_one_conflict (regno
);
760 /* Pseudos can't go in stack regs at the start of a basic block that
761 is reached by an abnormal edge. Likewise for call clobbered regs,
762 because caller-save, fixup_abnormal_edges and possibly the table
763 driven EH machinery are not quite ready to handle such regs live
764 across such edges. */
769 FOR_EACH_EDGE (e
, ei
, b
->preds
)
770 if (e
->flags
& EDGE_ABNORMAL
)
776 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, ax
,
778 allocno
[ax
].no_stack_reg
= 1;
780 for (ax
= FIRST_STACK_REG
; ax
<= LAST_STACK_REG
; ax
++)
781 record_one_conflict (ax
);
784 /* No need to record conflicts for call clobbered regs if we have
785 nonlocal labels around, as we don't ever try to allocate such
786 regs in this case. */
787 if (! current_function_has_nonlocal_label
)
788 for (ax
= 0; ax
< FIRST_PSEUDO_REGISTER
; ax
++)
789 if (call_used_regs
[ax
])
790 record_one_conflict (ax
);
797 /* Scan the code of this basic block, noting which allocnos
798 and hard regs are born or die. When one is born,
799 record a conflict with all others currently live. */
803 RTX_CODE code
= GET_CODE (insn
);
806 /* Make regs_set an empty set. */
810 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
815 for (link
= REG_NOTES (insn
);
816 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
817 link
= XEXP (link
, 1))
818 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
820 no_conflict_pairs
[i
].allocno1
821 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
822 no_conflict_pairs
[i
].allocno2
823 = reg_allocno
[REGNO (XEXP (link
, 0))];
828 /* Mark any registers clobbered by INSN as live,
829 so they conflict with the inputs. */
831 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
833 /* Mark any registers dead after INSN as dead now. */
835 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
836 if (REG_NOTE_KIND (link
) == REG_DEAD
)
837 mark_reg_death (XEXP (link
, 0));
839 /* Mark any registers set in INSN as live,
840 and mark them as conflicting with all other live regs.
841 Clobbers are processed again, so they conflict with
842 the registers that are set. */
844 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
847 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
848 if (REG_NOTE_KIND (link
) == REG_INC
)
849 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
852 /* If INSN has multiple outputs, then any reg that dies here
853 and is used inside of an output
854 must conflict with the other outputs.
856 It is unsafe to use !single_set here since it will ignore an
857 unused output. Just because an output is unused does not mean
858 the compiler can assume the side effect will not occur.
859 Consider if REG appears in the address of an output and we
860 reload the output. If we allocate REG to the same hard
861 register as an unused output we could set the hard register
862 before the output reload insn. */
863 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
864 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
865 if (REG_NOTE_KIND (link
) == REG_DEAD
)
867 int used_in_output
= 0;
869 rtx reg
= XEXP (link
, 0);
871 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
873 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
874 if (GET_CODE (set
) == SET
875 && !REG_P (SET_DEST (set
))
876 && !rtx_equal_p (reg
, SET_DEST (set
))
877 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
881 mark_reg_conflicts (reg
);
884 /* Mark any registers set in INSN and then never used. */
886 while (n_regs_set
-- > 0)
888 rtx note
= find_regno_note (insn
, REG_UNUSED
,
889 REGNO (regs_set
[n_regs_set
]));
891 mark_reg_death (XEXP (note
, 0));
895 if (insn
== BB_END (b
))
897 insn
= NEXT_INSN (insn
);
902 free (block_start_allocnos
);
905 /* Expand the preference information by looking for cases where one allocno
906 dies in an insn that sets an allocno. If those two allocnos don't conflict,
907 merge any preferences between those allocnos. */
910 expand_preferences (void)
916 /* We only try to handle the most common cases here. Most of the cases
917 where this wins are reg-reg copies. */
919 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
921 && (set
= single_set (insn
)) != 0
922 && REG_P (SET_DEST (set
))
923 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
924 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
925 if (REG_NOTE_KIND (link
) == REG_DEAD
926 && REG_P (XEXP (link
, 0))
927 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
928 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
929 reg_allocno
[REGNO (XEXP (link
, 0))]))
931 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
932 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
934 if (XEXP (link
, 0) == SET_SRC (set
))
936 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_copy_preferences
,
937 allocno
[a2
].hard_reg_copy_preferences
);
938 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_copy_preferences
,
939 allocno
[a1
].hard_reg_copy_preferences
);
942 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_preferences
,
943 allocno
[a2
].hard_reg_preferences
);
944 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_preferences
,
945 allocno
[a1
].hard_reg_preferences
);
946 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_full_preferences
,
947 allocno
[a2
].hard_reg_full_preferences
);
948 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_full_preferences
,
949 allocno
[a1
].hard_reg_full_preferences
);
953 /* Prune the preferences for global registers to exclude registers that cannot
956 Compute `regs_someone_prefers', which is a bitmask of the hard registers
957 that are preferred by conflicting registers of lower priority. If possible,
958 we will avoid using these registers. */
961 prune_preferences (void)
965 int *allocno_to_order
= XNEWVEC (int, max_allocno
);
967 /* Scan least most important to most important.
968 For each allocno, remove from preferences registers that cannot be used,
969 either because of conflicts or register type. Then compute all registers
970 preferred by each lower-priority register that conflicts. */
972 for (i
= max_allocno
- 1; i
>= 0; i
--)
976 num
= allocno_order
[i
];
977 allocno_to_order
[num
] = i
;
978 COPY_HARD_REG_SET (temp
, allocno
[num
].hard_reg_conflicts
);
980 if (allocno
[num
].calls_crossed
== 0)
981 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
983 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
985 IOR_COMPL_HARD_REG_SET
987 reg_class_contents
[(int) reg_preferred_class (allocno
[num
].reg
)]);
989 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, temp
);
990 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, temp
);
991 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_full_preferences
, temp
);
994 for (i
= max_allocno
- 1; i
>= 0; i
--)
996 /* Merge in the preferences of lower-priority registers (they have
997 already been pruned). If we also prefer some of those registers,
998 don't exclude them unless we are of a smaller size (in which case
999 we want to give the lower-priority allocno the first chance for
1000 these registers). */
1001 HARD_REG_SET temp
, temp2
;
1004 num
= allocno_order
[i
];
1006 CLEAR_HARD_REG_SET (temp
);
1007 CLEAR_HARD_REG_SET (temp2
);
1009 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ num
* allocno_row_words
,
1012 if (allocno_to_order
[allocno2
] > i
)
1014 if (allocno
[allocno2
].size
<= allocno
[num
].size
)
1015 IOR_HARD_REG_SET (temp
,
1016 allocno
[allocno2
].hard_reg_full_preferences
);
1018 IOR_HARD_REG_SET (temp2
,
1019 allocno
[allocno2
].hard_reg_full_preferences
);
1023 AND_COMPL_HARD_REG_SET (temp
, allocno
[num
].hard_reg_full_preferences
);
1024 IOR_HARD_REG_SET (temp
, temp2
);
1025 COPY_HARD_REG_SET (allocno
[num
].regs_someone_prefers
, temp
);
1027 free (allocno_to_order
);
1030 /* Assign a hard register to allocno NUM; look for one that is the beginning
1031 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
1032 The registers marked in PREFREGS are tried first.
1034 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
1035 be used for this allocation.
1037 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
1038 Otherwise ignore that preferred class and use the alternate class.
1040 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
1041 will have to be saved and restored at calls.
1043 RETRYING is nonzero if this is called from retry_global_alloc.
1045 If we find one, record it in reg_renumber.
1046 If not, do nothing. */
1049 find_reg (int num
, HARD_REG_SET losers
, int alt_regs_p
, int accept_call_clobbered
, int retrying
)
1051 int i
, best_reg
, pass
;
1052 HARD_REG_SET used
, used1
, used2
;
1054 enum reg_class
class = (alt_regs_p
1055 ? reg_alternate_class (allocno
[num
].reg
)
1056 : reg_preferred_class (allocno
[num
].reg
));
1057 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno
[num
].reg
);
1059 if (accept_call_clobbered
)
1060 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
1061 else if (allocno
[num
].calls_crossed
== 0)
1062 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
1064 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
1066 /* Some registers should not be allocated in global-alloc. */
1067 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
1069 IOR_HARD_REG_SET (used1
, losers
);
1071 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
1072 COPY_HARD_REG_SET (used2
, used1
);
1074 IOR_HARD_REG_SET (used1
, allocno
[num
].hard_reg_conflicts
);
1076 #ifdef CANNOT_CHANGE_MODE_CLASS
1077 cannot_change_mode_set_regs (&used1
, mode
, allocno
[num
].reg
);
1080 /* Try each hard reg to see if it fits. Do this in two passes.
1081 In the first pass, skip registers that are preferred by some other pseudo
1082 to give it a better chance of getting one of those registers. Only if
1083 we can't get a register when excluding those do we take one of them.
1084 However, we never allocate a register for the first time in pass 0. */
1086 COPY_HARD_REG_SET (used
, used1
);
1087 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
1088 IOR_HARD_REG_SET (used
, allocno
[num
].regs_someone_prefers
);
1091 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
1092 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
1096 COPY_HARD_REG_SET (used
, used1
);
1097 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1099 #ifdef REG_ALLOC_ORDER
1100 int regno
= reg_alloc_order
[i
];
1104 if (! TEST_HARD_REG_BIT (used
, regno
)
1105 && HARD_REGNO_MODE_OK (regno
, mode
)
1106 && (allocno
[num
].calls_crossed
== 0
1107 || accept_call_clobbered
1108 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
)))
1111 int lim
= regno
+ hard_regno_nregs
[regno
][mode
];
1114 && ! TEST_HARD_REG_BIT (used
, j
));
1121 #ifndef REG_ALLOC_ORDER
1122 i
= j
; /* Skip starting points we know will lose */
1128 /* See if there is a preferred register with the same class as the register
1129 we allocated above. Making this restriction prevents register
1130 preferencing from creating worse register allocation.
1132 Remove from the preferred registers and conflicting registers. Note that
1133 additional conflicts may have been added after `prune_preferences' was
1136 First do this for those register with copy preferences, then all
1137 preferred registers. */
1139 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, used
);
1140 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_copy_preferences
,
1141 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
1145 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1146 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_copy_preferences
, i
)
1147 && HARD_REGNO_MODE_OK (i
, mode
)
1148 && (allocno
[num
].calls_crossed
== 0
1149 || accept_call_clobbered
1150 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1151 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1152 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1153 REGNO_REG_CLASS (best_reg
))
1154 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1155 REGNO_REG_CLASS (i
))))
1158 int lim
= i
+ hard_regno_nregs
[i
][mode
];
1161 && ! TEST_HARD_REG_BIT (used
, j
)
1162 && (REGNO_REG_CLASS (j
)
1163 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1164 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1165 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1166 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1167 REGNO_REG_CLASS (j
))));
1178 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, used
);
1179 GO_IF_HARD_REG_SUBSET (allocno
[num
].hard_reg_preferences
,
1180 reg_class_contents
[(int) NO_REGS
], no_prefs
);
1184 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1185 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_preferences
, i
)
1186 && HARD_REGNO_MODE_OK (i
, mode
)
1187 && (allocno
[num
].calls_crossed
== 0
1188 || accept_call_clobbered
1189 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1190 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1191 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1192 REGNO_REG_CLASS (best_reg
))
1193 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1194 REGNO_REG_CLASS (i
))))
1197 int lim
= i
+ hard_regno_nregs
[i
][mode
];
1200 && ! TEST_HARD_REG_BIT (used
, j
)
1201 && (REGNO_REG_CLASS (j
)
1202 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1203 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1204 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1205 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1206 REGNO_REG_CLASS (j
))));
1217 /* If we haven't succeeded yet, try with caller-saves.
1218 We need not check to see if the current function has nonlocal
1219 labels because we don't put any pseudos that are live over calls in
1220 registers in that case. */
1222 if (flag_caller_saves
&& best_reg
< 0)
1224 /* Did not find a register. If it would be profitable to
1225 allocate a call-clobbered register and save and restore it
1226 around calls, do that. Don't do this if it crosses any calls
1227 that might throw. */
1228 if (! accept_call_clobbered
1229 && allocno
[num
].calls_crossed
!= 0
1230 && allocno
[num
].throwing_calls_crossed
== 0
1231 && CALLER_SAVE_PROFITABLE (allocno
[num
].n_refs
,
1232 allocno
[num
].calls_crossed
))
1234 HARD_REG_SET new_losers
;
1236 CLEAR_HARD_REG_SET (new_losers
);
1238 COPY_HARD_REG_SET (new_losers
, losers
);
1240 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1241 find_reg (num
, new_losers
, alt_regs_p
, 1, retrying
);
1242 if (reg_renumber
[allocno
[num
].reg
] >= 0)
1244 caller_save_needed
= 1;
1250 /* If we haven't succeeded yet,
1251 see if some hard reg that conflicts with us
1252 was utilized poorly by local-alloc.
1253 If so, kick out the regs that were put there by local-alloc
1254 so we can use it instead. */
1255 if (best_reg
< 0 && !retrying
1256 /* Let's not bother with multi-reg allocnos. */
1257 && allocno
[num
].size
== 1
1258 && REG_BASIC_BLOCK (allocno
[num
].reg
) == REG_BLOCK_GLOBAL
)
1260 /* Count from the end, to find the least-used ones first. */
1261 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1263 #ifdef REG_ALLOC_ORDER
1264 int regno
= reg_alloc_order
[i
];
1269 if (local_reg_n_refs
[regno
] != 0
1270 /* Don't use a reg no good for this pseudo. */
1271 && ! TEST_HARD_REG_BIT (used2
, regno
)
1272 && HARD_REGNO_MODE_OK (regno
, mode
)
1273 /* The code below assumes that we need only a single
1274 register, but the check of allocno[num].size above
1275 was not enough. Sometimes we need more than one
1276 register for a single-word value. */
1277 && hard_regno_nregs
[regno
][mode
] == 1
1278 && (allocno
[num
].calls_crossed
== 0
1279 || accept_call_clobbered
1280 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
))
1281 #ifdef CANNOT_CHANGE_MODE_CLASS
1282 && ! invalid_mode_change_p (regno
, REGNO_REG_CLASS (regno
),
1286 && (!allocno
[num
].no_stack_reg
1287 || regno
< FIRST_STACK_REG
|| regno
> LAST_STACK_REG
)
1291 /* We explicitly evaluate the divide results into temporary
1292 variables so as to avoid excess precision problems that occur
1293 on an i386-unknown-sysv4.2 (unixware) host. */
1295 double tmp1
= ((double) local_reg_freq
[regno
] * local_reg_n_refs
[regno
]
1296 / local_reg_live_length
[regno
]);
1297 double tmp2
= ((double) allocno
[num
].freq
* allocno
[num
].n_refs
1298 / allocno
[num
].live_length
);
1302 /* Hard reg REGNO was used less in total by local regs
1303 than it would be used by this one allocno! */
1307 fprintf (dump_file
, "Regno %d better for global %d, ",
1308 regno
, allocno
[num
].reg
);
1309 fprintf (dump_file
, "fr:%d, ll:%d, nr:%d ",
1310 allocno
[num
].freq
, allocno
[num
].live_length
,
1311 allocno
[num
].n_refs
);
1312 fprintf (dump_file
, "(was: fr:%d, ll:%d, nr:%d)\n",
1313 local_reg_freq
[regno
],
1314 local_reg_live_length
[regno
],
1315 local_reg_n_refs
[regno
]);
1318 for (k
= 0; k
< max_regno
; k
++)
1319 if (reg_renumber
[k
] >= 0)
1321 int r
= reg_renumber
[k
];
1323 = r
+ hard_regno_nregs
[r
][PSEUDO_REGNO_MODE (k
)];
1325 if (regno
>= r
&& regno
< endregno
)
1329 "Local Reg %d now on stack\n", k
);
1330 reg_renumber
[k
] = -1;
1341 /* Did we find a register? */
1346 HARD_REG_SET this_reg
;
1348 /* Yes. Record it as the hard register of this pseudo-reg. */
1349 reg_renumber
[allocno
[num
].reg
] = best_reg
;
1350 /* Also of any pseudo-regs that share with it. */
1351 if (reg_may_share
[allocno
[num
].reg
])
1352 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1353 if (reg_allocno
[j
] == num
)
1354 reg_renumber
[j
] = best_reg
;
1356 /* Make a set of the hard regs being allocated. */
1357 CLEAR_HARD_REG_SET (this_reg
);
1358 lim
= best_reg
+ hard_regno_nregs
[best_reg
][mode
];
1359 for (j
= best_reg
; j
< lim
; j
++)
1361 SET_HARD_REG_BIT (this_reg
, j
);
1362 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1363 /* This is no longer a reg used just by local regs. */
1364 local_reg_n_refs
[j
] = 0;
1365 local_reg_freq
[j
] = 0;
1367 /* For each other pseudo-reg conflicting with this one,
1368 mark it as conflicting with the hard regs this one occupies. */
1370 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ lim
* allocno_row_words
, j
,
1372 IOR_HARD_REG_SET (allocno
[j
].hard_reg_conflicts
, this_reg
);
1377 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1378 Perhaps it had previously seemed not worth a hard reg,
1379 or perhaps its old hard reg has been commandeered for reloads.
1380 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1381 they do not appear to be allocated.
1382 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1385 retry_global_alloc (int regno
, HARD_REG_SET forbidden_regs
)
1387 int alloc_no
= reg_allocno
[regno
];
1390 /* If we have more than one register class,
1391 first try allocating in the class that is cheapest
1392 for this pseudo-reg. If that fails, try any reg. */
1393 if (N_REG_CLASSES
> 1)
1394 find_reg (alloc_no
, forbidden_regs
, 0, 0, 1);
1395 if (reg_renumber
[regno
] < 0
1396 && reg_alternate_class (regno
) != NO_REGS
)
1397 find_reg (alloc_no
, forbidden_regs
, 1, 0, 1);
1399 /* If we found a register, modify the RTL for the register to
1400 show the hard register, and mark that register live. */
1401 if (reg_renumber
[regno
] >= 0)
1403 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1404 mark_home_live (regno
);
1409 /* Record a conflict between register REGNO
1410 and everything currently live.
1411 REGNO must not be a pseudo reg that was allocated
1412 by local_alloc; such numbers must be translated through
1413 reg_renumber before calling here. */
1416 record_one_conflict (int regno
)
1420 if (regno
< FIRST_PSEUDO_REGISTER
)
1421 /* When a hard register becomes live,
1422 record conflicts with live pseudo regs. */
1423 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, j
,
1425 SET_HARD_REG_BIT (allocno
[j
].hard_reg_conflicts
, regno
);
1428 /* When a pseudo-register becomes live,
1429 record conflicts first with hard regs,
1430 then with other pseudo regs. */
1432 int ialloc
= reg_allocno
[regno
];
1433 int ialloc_prod
= ialloc
* allocno_row_words
;
1435 IOR_HARD_REG_SET (allocno
[ialloc
].hard_reg_conflicts
, hard_regs_live
);
1436 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1437 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1441 /* Record all allocnos currently live as conflicting
1442 with all hard regs currently live.
1444 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1445 are currently live. Their bits are also flagged in allocnos_live. */
1448 record_conflicts (int *allocno_vec
, int len
)
1451 IOR_HARD_REG_SET (allocno
[allocno_vec
[len
]].hard_reg_conflicts
,
1455 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1457 mirror_conflicts (void)
1460 int rw
= allocno_row_words
;
1461 int rwb
= rw
* INT_BITS
;
1462 INT_TYPE
*p
= conflicts
;
1463 INT_TYPE
*q0
= conflicts
, *q1
, *q2
;
1464 unsigned INT_TYPE mask
;
1466 for (i
= max_allocno
- 1, mask
= 1; i
>= 0; i
--, mask
<<= 1)
1473 for (j
= allocno_row_words
- 1, q1
= q0
; j
>= 0; j
--, q1
+= rwb
)
1475 unsigned INT_TYPE word
;
1477 for (word
= (unsigned INT_TYPE
) *p
++, q2
= q1
; word
;
1478 word
>>= 1, q2
+= rw
)
1487 /* Handle the case where REG is set by the insn being scanned,
1488 during the forward scan to accumulate conflicts.
1489 Store a 1 in regs_live or allocnos_live for this register, record how many
1490 consecutive hardware registers it actually needs,
1491 and record a conflict with all other registers already live.
1493 Note that even if REG does not remain alive after this insn,
1494 we must mark it here as live, to ensure a conflict between
1495 REG and any other regs set in this insn that really do live.
1496 This is because those other regs could be considered after this.
1498 REG might actually be something other than a register;
1499 if so, we do nothing.
1501 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1502 a REG_INC note was found for it). */
1505 mark_reg_store (rtx reg
, rtx setter
, void *data ATTRIBUTE_UNUSED
)
1509 if (GET_CODE (reg
) == SUBREG
)
1510 reg
= SUBREG_REG (reg
);
1515 regs_set
[n_regs_set
++] = reg
;
1517 if (setter
&& GET_CODE (setter
) != CLOBBER
)
1518 set_preference (reg
, SET_SRC (setter
));
1520 regno
= REGNO (reg
);
1522 /* Either this is one of the max_allocno pseudo regs not allocated,
1523 or it is or has a hardware reg. First handle the pseudo-regs. */
1524 if (regno
>= FIRST_PSEUDO_REGISTER
)
1526 if (reg_allocno
[regno
] >= 0)
1528 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1529 record_one_conflict (regno
);
1533 if (reg_renumber
[regno
] >= 0)
1534 regno
= reg_renumber
[regno
];
1536 /* Handle hardware regs (and pseudos allocated to hard regs). */
1537 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1539 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1540 while (regno
< last
)
1542 record_one_conflict (regno
);
1543 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1549 /* Like mark_reg_store except notice just CLOBBERs; ignore SETs. */
1552 mark_reg_clobber (rtx reg
, rtx setter
, void *data
)
1554 if (GET_CODE (setter
) == CLOBBER
)
1555 mark_reg_store (reg
, setter
, data
);
1558 /* Record that REG has conflicts with all the regs currently live.
1559 Do not mark REG itself as live. */
1562 mark_reg_conflicts (rtx reg
)
1566 if (GET_CODE (reg
) == SUBREG
)
1567 reg
= SUBREG_REG (reg
);
1572 regno
= REGNO (reg
);
1574 /* Either this is one of the max_allocno pseudo regs not allocated,
1575 or it is or has a hardware reg. First handle the pseudo-regs. */
1576 if (regno
>= FIRST_PSEUDO_REGISTER
)
1578 if (reg_allocno
[regno
] >= 0)
1579 record_one_conflict (regno
);
1582 if (reg_renumber
[regno
] >= 0)
1583 regno
= reg_renumber
[regno
];
1585 /* Handle hardware regs (and pseudos allocated to hard regs). */
1586 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1588 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1589 while (regno
< last
)
1591 record_one_conflict (regno
);
1597 /* Mark REG as being dead (following the insn being scanned now).
1598 Store a 0 in regs_live or allocnos_live for this register. */
1601 mark_reg_death (rtx reg
)
1603 int regno
= REGNO (reg
);
1605 /* Either this is one of the max_allocno pseudo regs not allocated,
1606 or it is a hardware reg. First handle the pseudo-regs. */
1607 if (regno
>= FIRST_PSEUDO_REGISTER
)
1609 if (reg_allocno
[regno
] >= 0)
1610 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1613 /* For pseudo reg, see if it has been assigned a hardware reg. */
1614 if (reg_renumber
[regno
] >= 0)
1615 regno
= reg_renumber
[regno
];
1617 /* Handle hardware regs (and pseudos allocated to hard regs). */
1618 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1620 /* Pseudo regs already assigned hardware regs are treated
1621 almost the same as explicit hardware regs. */
1622 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1623 while (regno
< last
)
1625 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1631 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1632 for the value stored in it. MODE determines how many consecutive
1633 registers are actually in use. Do not record conflicts;
1634 it is assumed that the caller will do that. */
1637 mark_reg_live_nc (int regno
, enum machine_mode mode
)
1639 int last
= regno
+ hard_regno_nregs
[regno
][mode
];
1640 while (regno
< last
)
1642 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1647 /* Try to set a preference for an allocno to a hard register.
1648 We are passed DEST and SRC which are the operands of a SET. It is known
1649 that SRC is a register. If SRC or the first operand of SRC is a register,
1650 try to set a preference. If one of the two is a hard register and the other
1651 is a pseudo-register, mark the preference.
1653 Note that we are not as aggressive as local-alloc in trying to tie a
1654 pseudo-register to a hard register. */
1657 set_preference (rtx dest
, rtx src
)
1659 unsigned int src_regno
, dest_regno
;
1660 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1661 to compensate for subregs in SRC or DEST. */
1666 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1667 src
= XEXP (src
, 0), copy
= 0;
1669 /* Get the reg number for both SRC and DEST.
1670 If neither is a reg, give up. */
1673 src_regno
= REGNO (src
);
1674 else if (GET_CODE (src
) == SUBREG
&& REG_P (SUBREG_REG (src
)))
1676 src_regno
= REGNO (SUBREG_REG (src
));
1678 if (REGNO (SUBREG_REG (src
)) < FIRST_PSEUDO_REGISTER
)
1679 offset
+= subreg_regno_offset (REGNO (SUBREG_REG (src
)),
1680 GET_MODE (SUBREG_REG (src
)),
1684 offset
+= (SUBREG_BYTE (src
)
1685 / REGMODE_NATURAL_SIZE (GET_MODE (src
)));
1691 dest_regno
= REGNO (dest
);
1692 else if (GET_CODE (dest
) == SUBREG
&& REG_P (SUBREG_REG (dest
)))
1694 dest_regno
= REGNO (SUBREG_REG (dest
));
1696 if (REGNO (SUBREG_REG (dest
)) < FIRST_PSEUDO_REGISTER
)
1697 offset
-= subreg_regno_offset (REGNO (SUBREG_REG (dest
)),
1698 GET_MODE (SUBREG_REG (dest
)),
1702 offset
-= (SUBREG_BYTE (dest
)
1703 / REGMODE_NATURAL_SIZE (GET_MODE (dest
)));
1708 /* Convert either or both to hard reg numbers. */
1710 if (reg_renumber
[src_regno
] >= 0)
1711 src_regno
= reg_renumber
[src_regno
];
1713 if (reg_renumber
[dest_regno
] >= 0)
1714 dest_regno
= reg_renumber
[dest_regno
];
1716 /* Now if one is a hard reg and the other is a global pseudo
1717 then give the other a preference. */
1719 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1720 && reg_allocno
[src_regno
] >= 0)
1722 dest_regno
-= offset
;
1723 if (dest_regno
< FIRST_PSEUDO_REGISTER
)
1726 SET_REGBIT (hard_reg_copy_preferences
,
1727 reg_allocno
[src_regno
], dest_regno
);
1729 SET_REGBIT (hard_reg_preferences
,
1730 reg_allocno
[src_regno
], dest_regno
);
1731 for (i
= dest_regno
;
1732 i
< dest_regno
+ hard_regno_nregs
[dest_regno
][GET_MODE (dest
)];
1734 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1738 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1739 && reg_allocno
[dest_regno
] >= 0)
1741 src_regno
+= offset
;
1742 if (src_regno
< FIRST_PSEUDO_REGISTER
)
1745 SET_REGBIT (hard_reg_copy_preferences
,
1746 reg_allocno
[dest_regno
], src_regno
);
1748 SET_REGBIT (hard_reg_preferences
,
1749 reg_allocno
[dest_regno
], src_regno
);
1751 i
< src_regno
+ hard_regno_nregs
[src_regno
][GET_MODE (src
)];
1753 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1758 /* Indicate that hard register number FROM was eliminated and replaced with
1759 an offset from hard register number TO. The status of hard registers live
1760 at the start of a basic block is updated by replacing a use of FROM with
1764 mark_elimination (int from
, int to
)
1770 regset r
= bb
->il
.rtl
->global_live_at_start
;
1771 if (REGNO_REG_SET_P (r
, from
))
1773 CLEAR_REGNO_REG_SET (r
, from
);
1774 SET_REGNO_REG_SET (r
, to
);
1779 /* Used for communication between the following functions. Holds the
1780 current life information. */
1781 static regset live_relevant_regs
;
1783 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1784 This is called via note_stores. */
1786 reg_becomes_live (rtx reg
, rtx setter ATTRIBUTE_UNUSED
, void *regs_set
)
1790 if (GET_CODE (reg
) == SUBREG
)
1791 reg
= SUBREG_REG (reg
);
1796 regno
= REGNO (reg
);
1797 if (regno
< FIRST_PSEUDO_REGISTER
)
1799 int nregs
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1802 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1803 if (! fixed_regs
[regno
])
1804 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1808 else if (reg_renumber
[regno
] >= 0)
1810 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1811 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1815 /* Record in live_relevant_regs that register REGNO died. */
1817 reg_dies (int regno
, enum machine_mode mode
, struct insn_chain
*chain
)
1819 if (regno
< FIRST_PSEUDO_REGISTER
)
1821 int nregs
= hard_regno_nregs
[regno
][mode
];
1824 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1825 if (! fixed_regs
[regno
])
1826 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1832 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1833 if (reg_renumber
[regno
] >= 0)
1834 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1838 /* Walk the insns of the current function and build reload_insn_chain,
1839 and record register life information. */
1841 build_insn_chain (rtx first
)
1843 struct insn_chain
**p
= &reload_insn_chain
;
1844 struct insn_chain
*prev
= 0;
1845 basic_block b
= ENTRY_BLOCK_PTR
->next_bb
;
1847 live_relevant_regs
= ALLOC_REG_SET (®_obstack
);
1849 for (; first
; first
= NEXT_INSN (first
))
1851 struct insn_chain
*c
;
1853 if (first
== BB_HEAD (b
))
1858 CLEAR_REG_SET (live_relevant_regs
);
1860 EXECUTE_IF_SET_IN_BITMAP (b
->il
.rtl
->global_live_at_start
, 0, i
, bi
)
1862 if (i
< FIRST_PSEUDO_REGISTER
1863 ? ! TEST_HARD_REG_BIT (eliminable_regset
, i
)
1864 : reg_renumber
[i
] >= 0)
1865 SET_REGNO_REG_SET (live_relevant_regs
, i
);
1869 if (!NOTE_P (first
) && !BARRIER_P (first
))
1871 c
= new_insn_chain ();
1877 c
->block
= b
->index
;
1883 /* Mark the death of everything that dies in this instruction. */
1885 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1886 if (REG_NOTE_KIND (link
) == REG_DEAD
1887 && REG_P (XEXP (link
, 0)))
1888 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1891 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1893 /* Mark everything born in this instruction as live. */
1895 note_stores (PATTERN (first
), reg_becomes_live
,
1899 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1905 /* Mark anything that is set in this insn and then unused as dying. */
1907 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1908 if (REG_NOTE_KIND (link
) == REG_UNUSED
1909 && REG_P (XEXP (link
, 0)))
1910 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1915 if (first
== BB_END (b
))
1918 /* Stop after we pass the end of the last basic block. Verify that
1919 no real insns are after the end of the last basic block.
1921 We may want to reorganize the loop somewhat since this test should
1922 always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if
1923 the previous real insn is a JUMP_INSN. */
1924 if (b
== EXIT_BLOCK_PTR
)
1926 #ifdef ENABLE_CHECKING
1927 for (first
= NEXT_INSN (first
); first
; first
= NEXT_INSN (first
))
1928 gcc_assert (!INSN_P (first
)
1929 || GET_CODE (PATTERN (first
)) == USE
1930 || ((GET_CODE (PATTERN (first
)) == ADDR_VEC
1931 || GET_CODE (PATTERN (first
)) == ADDR_DIFF_VEC
)
1932 && prev_real_insn (first
) != 0
1933 && JUMP_P (prev_real_insn (first
))));
1938 FREE_REG_SET (live_relevant_regs
);
1942 /* Print debugging trace information if -dg switch is given,
1943 showing the information on which the allocation decisions are based. */
1946 dump_conflicts (FILE *file
)
1949 int has_preferences
;
1952 for (i
= 0; i
< max_allocno
; i
++)
1954 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1958 fprintf (file
, ";; %d regs to allocate:", nregs
);
1959 for (i
= 0; i
< max_allocno
; i
++)
1962 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1964 fprintf (file
, " %d", allocno
[allocno_order
[i
]].reg
);
1965 for (j
= 0; j
< max_regno
; j
++)
1966 if (reg_allocno
[j
] == allocno_order
[i
]
1967 && j
!= allocno
[allocno_order
[i
]].reg
)
1968 fprintf (file
, "+%d", j
);
1969 if (allocno
[allocno_order
[i
]].size
!= 1)
1970 fprintf (file
, " (%d)", allocno
[allocno_order
[i
]].size
);
1972 fprintf (file
, "\n");
1974 for (i
= 0; i
< max_allocno
; i
++)
1977 fprintf (file
, ";; %d conflicts:", allocno
[i
].reg
);
1978 for (j
= 0; j
< max_allocno
; j
++)
1979 if (CONFLICTP (j
, i
))
1980 fprintf (file
, " %d", allocno
[j
].reg
);
1981 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1982 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_conflicts
, j
))
1983 fprintf (file
, " %d", j
);
1984 fprintf (file
, "\n");
1986 has_preferences
= 0;
1987 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1988 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1989 has_preferences
= 1;
1991 if (! has_preferences
)
1993 fprintf (file
, ";; %d preferences:", allocno
[i
].reg
);
1994 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1995 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
1996 fprintf (file
, " %d", j
);
1997 fprintf (file
, "\n");
1999 fprintf (file
, "\n");
2003 dump_global_regs (FILE *file
)
2007 fprintf (file
, ";; Register dispositions:\n");
2008 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
2009 if (reg_renumber
[i
] >= 0)
2011 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
2013 fprintf (file
, "\n");
2016 fprintf (file
, "\n\n;; Hard regs used: ");
2017 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2018 if (regs_ever_live
[i
])
2019 fprintf (file
, " %d", i
);
2020 fprintf (file
, "\n\n");
2025 /* This page contains code to make live information more accurate.
2026 The accurate register liveness at program point P means:
2027 o there is a path from P to usage of the register and the
2028 register is not redefined or killed on the path.
2029 o register at P is partially available, i.e. there is a path from
2030 a register definition to the point P and the register is not
2031 killed (clobbered) on the path
2033 The standard GCC live information means only the first condition.
2034 Without the partial availability, there will be more register
2035 conflicts and as a consequence worse register allocation. The
2036 typical example where the information can be different is a
2037 register initialized in the loop at the basic block preceding the
2040 /* The following structure contains basic block data flow information
2041 used to calculate partial availability of registers. */
2045 /* The basic block reverse post-order number. */
2047 /* Registers used uninitialized in an insn in which there is an
2048 early clobbered register might get the same hard register. */
2049 bitmap earlyclobber
;
2050 /* Registers correspondingly killed (clobbered) and defined but not
2051 killed afterward in the basic block. */
2052 bitmap killed
, avloc
;
2053 /* Registers partially available and living (in other words whose
2054 values were calculated and used) correspondingly at the start
2055 and end of the basic block. */
2056 bitmap live_pavin
, live_pavout
;
2059 /* Macros for accessing data flow information of basic blocks. */
2061 #define BB_INFO(BB) ((struct bb_info *) (BB)->aux)
2062 #define BB_INFO_BY_INDEX(N) BB_INFO (BASIC_BLOCK(N))
2064 static struct bitmap_obstack greg_obstack
;
2065 /* The function allocates the info structures of each basic block. It
2066 also initialized LIVE_PAVIN and LIVE_PAVOUT as if all hard
2067 registers were partially available. */
2070 allocate_bb_info (void)
2074 struct bb_info
*bb_info
;
2077 alloc_aux_for_blocks (sizeof (struct bb_info
));
2078 init
= BITMAP_ALLOC (NULL
);
2079 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2080 bitmap_set_bit (init
, i
);
2081 bitmap_obstack_initialize (&greg_obstack
);
2085 bb_info
->earlyclobber
= BITMAP_ALLOC (&greg_obstack
);
2086 bb_info
->avloc
= BITMAP_ALLOC (&greg_obstack
);
2087 bb_info
->killed
= BITMAP_ALLOC (&greg_obstack
);
2088 bb_info
->live_pavin
= BITMAP_ALLOC (&greg_obstack
);
2089 bb_info
->live_pavout
= BITMAP_ALLOC (&greg_obstack
);
2090 bitmap_copy (bb_info
->live_pavin
, init
);
2091 bitmap_copy (bb_info
->live_pavout
, init
);
2096 /* The function frees the allocated info of all basic blocks. */
2101 bitmap_obstack_release (&greg_obstack
);
2102 free_aux_for_blocks ();
2105 /* The function modifies local info for register REG being changed in
2106 SETTER. DATA is used to pass the current basic block info. */
2109 mark_reg_change (rtx reg
, rtx setter
, void *data
)
2112 basic_block bb
= data
;
2113 struct bb_info
*bb_info
= BB_INFO (bb
);
2115 if (GET_CODE (reg
) == SUBREG
)
2116 reg
= SUBREG_REG (reg
);
2121 regno
= REGNO (reg
);
2122 bitmap_set_bit (bb_info
->killed
, regno
);
2124 if (GET_CODE (setter
) != CLOBBER
)
2125 bitmap_set_bit (bb_info
->avloc
, regno
);
2127 bitmap_clear_bit (bb_info
->avloc
, regno
);
2130 /* Classes of registers which could be early clobbered in the current
2133 static VEC(int,heap
) *earlyclobber_regclass
;
2135 /* This function finds and stores register classes that could be early
2136 clobbered in INSN. If any earlyclobber classes are found, the function
2137 returns TRUE, in all other cases it returns FALSE. */
2140 check_earlyclobber (rtx insn
)
2145 extract_insn (insn
);
2147 VEC_truncate (int, earlyclobber_regclass
, 0);
2148 for (opno
= 0; opno
< recog_data
.n_operands
; opno
++)
2153 enum reg_class
class;
2154 const char *p
= recog_data
.constraints
[opno
];
2163 case '=': case '+': case '?':
2166 case 'm': case '<': case '>': case 'V': case 'o':
2167 case 'E': case 'F': case 'G': case 'H':
2168 case 's': case 'i': case 'n':
2169 case 'I': case 'J': case 'K': case 'L':
2170 case 'M': case 'N': case 'O': case 'P':
2172 case '0': case '1': case '2': case '3': case '4':
2173 case '5': case '6': case '7': case '8': case '9':
2174 /* These don't say anything we care about. */
2182 if (amp_p
&& class != NO_REGS
)
2188 VEC_iterate (int, earlyclobber_regclass
, i
, rc
);
2191 if (rc
== (int) class)
2195 /* We use VEC_quick_push here because
2196 earlyclobber_regclass holds no more than
2197 N_REG_CLASSES elements. */
2198 VEC_quick_push (int, earlyclobber_regclass
, (int) class);
2208 class = GENERAL_REGS
;
2212 class = REG_CLASS_FROM_CONSTRAINT (c
, p
);
2217 p
+= CONSTRAINT_LEN (c
, p
);
2224 /* The function checks that pseudo-register *X has a class
2225 intersecting with the class of pseudo-register could be early
2226 clobbered in the same insn.
2227 This function is a no-op if earlyclobber_regclass is empty. */
2230 mark_reg_use_for_earlyclobber (rtx
*x
, void *data ATTRIBUTE_UNUSED
)
2232 enum reg_class pref_class
, alt_class
;
2234 basic_block bb
= data
;
2235 struct bb_info
*bb_info
= BB_INFO (bb
);
2237 if (REG_P (*x
) && REGNO (*x
) >= FIRST_PSEUDO_REGISTER
)
2242 if (bitmap_bit_p (bb_info
->killed
, regno
)
2243 || bitmap_bit_p (bb_info
->avloc
, regno
))
2245 pref_class
= reg_preferred_class (regno
);
2246 alt_class
= reg_alternate_class (regno
);
2247 for (i
= 0; VEC_iterate (int, earlyclobber_regclass
, i
, rc
); i
++)
2249 if (reg_classes_intersect_p (rc
, pref_class
)
2251 && reg_classes_intersect_p (rc
, alt_class
)))
2253 bitmap_set_bit (bb_info
->earlyclobber
, regno
);
2261 /* The function processes all pseudo-registers in *X with the aid of
2262 previous function. */
2265 mark_reg_use_for_earlyclobber_1 (rtx
*x
, void *data
)
2267 for_each_rtx (x
, mark_reg_use_for_earlyclobber
, data
);
2270 /* The function calculates local info for each basic block. */
2273 calculate_local_reg_bb_info (void)
2278 /* We know that earlyclobber_regclass holds no more than
2279 N_REG_CLASSES elements. See check_earlyclobber. */
2280 earlyclobber_regclass
= VEC_alloc (int, heap
, N_REG_CLASSES
);
2283 bound
= NEXT_INSN (BB_END (bb
));
2284 for (insn
= BB_HEAD (bb
); insn
!= bound
; insn
= NEXT_INSN (insn
))
2287 note_stores (PATTERN (insn
), mark_reg_change
, bb
);
2288 if (check_earlyclobber (insn
))
2289 note_uses (&PATTERN (insn
), mark_reg_use_for_earlyclobber_1
, bb
);
2292 VEC_free (int, heap
, earlyclobber_regclass
);
2295 /* The function sets up reverse post-order number of each basic
2299 set_up_bb_rts_numbers (void)
2304 rts_order
= XNEWVEC (int, n_basic_blocks
- NUM_FIXED_BLOCKS
);
2305 post_order_compute (rts_order
, false);
2306 for (i
= 0; i
< n_basic_blocks
- NUM_FIXED_BLOCKS
; i
++)
2307 BB_INFO_BY_INDEX (rts_order
[i
])->rts_number
= i
;
2311 /* Compare function for sorting blocks in reverse postorder. */
2314 rpost_cmp (const void *bb1
, const void *bb2
)
2316 basic_block b1
= *(basic_block
*) bb1
, b2
= *(basic_block
*) bb2
;
2318 return BB_INFO (b2
)->rts_number
- BB_INFO (b1
)->rts_number
;
2321 /* Temporary bitmap used for live_pavin, live_pavout calculation. */
2322 static bitmap temp_bitmap
;
2324 /* The function calculates partial register availability according to
2325 the following equations:
2328 = empty for entry block
2329 | union (live_pavout of predecessors) & global_live_at_start
2330 bb.live_pavout = union (bb.live_pavin - bb.killed, bb.avloc)
2331 & global_live_at_end */
2334 calculate_reg_pav (void)
2336 basic_block bb
, succ
;
2339 VEC(basic_block
,heap
) *bbs
, *new_bbs
, *temp
;
2340 basic_block
*bb_array
;
2343 bbs
= VEC_alloc (basic_block
, heap
, n_basic_blocks
);
2344 new_bbs
= VEC_alloc (basic_block
, heap
, n_basic_blocks
);
2345 temp_bitmap
= BITMAP_ALLOC (NULL
);
2348 VEC_quick_push (basic_block
, bbs
, bb
);
2350 wset
= sbitmap_alloc (n_basic_blocks
+ 1);
2351 while (VEC_length (basic_block
, bbs
))
2353 bb_array
= VEC_address (basic_block
, bbs
);
2354 nel
= VEC_length (basic_block
, bbs
);
2355 qsort (bb_array
, nel
, sizeof (basic_block
), rpost_cmp
);
2356 sbitmap_zero (wset
);
2357 for (i
= 0; i
< nel
; i
++)
2360 struct bb_info
*bb_info
;
2361 bitmap bb_live_pavin
, bb_live_pavout
;
2364 bb_info
= BB_INFO (bb
);
2365 bb_live_pavin
= bb_info
->live_pavin
;
2366 bb_live_pavout
= bb_info
->live_pavout
;
2367 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2369 basic_block pred
= e
->src
;
2371 if (pred
->index
!= ENTRY_BLOCK
)
2372 bitmap_ior_into (bb_live_pavin
, BB_INFO (pred
)->live_pavout
);
2374 bitmap_and_into (bb_live_pavin
, bb
->il
.rtl
->global_live_at_start
);
2375 bitmap_ior_and_compl (temp_bitmap
, bb_info
->avloc
,
2376 bb_live_pavin
, bb_info
->killed
);
2377 bitmap_and_into (temp_bitmap
, bb
->il
.rtl
->global_live_at_end
);
2378 if (! bitmap_equal_p (temp_bitmap
, bb_live_pavout
))
2380 bitmap_copy (bb_live_pavout
, temp_bitmap
);
2381 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2384 if (succ
->index
!= EXIT_BLOCK
2385 && !TEST_BIT (wset
, succ
->index
))
2387 SET_BIT (wset
, succ
->index
);
2388 VEC_quick_push (basic_block
, new_bbs
, succ
);
2396 VEC_truncate (basic_block
, new_bbs
, 0);
2398 sbitmap_free (wset
);
2399 BITMAP_FREE (temp_bitmap
);
2400 VEC_free (basic_block
, heap
, new_bbs
);
2401 VEC_free (basic_block
, heap
, bbs
);
2404 /* The function modifies partial availability information for two
2405 special cases to prevent incorrect work of the subsequent passes
2406 with the accurate live information based on the partial
2410 modify_reg_pav (void)
2413 struct bb_info
*bb_info
;
2416 HARD_REG_SET zero
, stack_hard_regs
, used
;
2419 CLEAR_HARD_REG_SET (zero
);
2420 CLEAR_HARD_REG_SET (stack_hard_regs
);
2421 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
2422 SET_HARD_REG_BIT(stack_hard_regs
, i
);
2423 stack_regs
= BITMAP_ALLOC (&greg_obstack
);
2424 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
2426 COPY_HARD_REG_SET (used
, reg_class_contents
[reg_preferred_class (i
)]);
2427 IOR_HARD_REG_SET (used
, reg_class_contents
[reg_alternate_class (i
)]);
2428 AND_HARD_REG_SET (used
, stack_hard_regs
);
2429 GO_IF_HARD_REG_EQUAL(used
, zero
, skip
);
2430 bitmap_set_bit (stack_regs
, i
);
2437 bb_info
= BB_INFO (bb
);
2439 /* Reload can assign the same hard register to uninitialized
2440 pseudo-register and early clobbered pseudo-register in an
2441 insn if the pseudo-register is used first time in given BB
2442 and not lived at the BB start. To prevent this we don't
2443 change life information for such pseudo-registers. */
2444 bitmap_ior_into (bb_info
->live_pavin
, bb_info
->earlyclobber
);
2446 /* We can not use the same stack register for uninitialized
2447 pseudo-register and another living pseudo-register because if the
2448 uninitialized pseudo-register dies, subsequent pass reg-stack
2449 will be confused (it will believe that the other register
2451 bitmap_ior_into (bb_info
->live_pavin
, stack_regs
);
2455 BITMAP_FREE (stack_regs
);
2459 /* The following function makes live information more accurate by
2460 modifying global_live_at_start and global_live_at_end of basic
2463 The standard GCC life analysis permits registers to live
2464 uninitialized, for example:
2473 With normal life_analysis, R would be live before "Loop:".
2474 The result is that R causes many interferences that do not
2477 After the function call a register lives at a program point
2478 only if it is initialized on a path from CFG entry to the
2482 make_accurate_live_analysis (void)
2485 struct bb_info
*bb_info
;
2487 max_regno
= max_reg_num ();
2489 allocate_bb_info ();
2490 calculate_local_reg_bb_info ();
2491 set_up_bb_rts_numbers ();
2492 calculate_reg_pav ();
2496 bb_info
= BB_INFO (bb
);
2498 bitmap_and_into (bb
->il
.rtl
->global_live_at_start
, bb_info
->live_pavin
);
2499 bitmap_and_into (bb
->il
.rtl
->global_live_at_end
, bb_info
->live_pavout
);
2503 /* Run old register allocator. Return TRUE if we must exit
2504 rest_of_compilation upon return. */
2506 rest_of_handle_global_alloc (void)
2510 /* If optimizing, allocate remaining pseudo-regs. Do the reload
2511 pass fixing up any insns that are invalid. */
2514 failure
= global_alloc ();
2517 build_insn_chain (get_insns ());
2518 failure
= reload (get_insns (), 0);
2521 if (dump_enabled_p (pass_global_alloc
.static_pass_number
))
2523 timevar_push (TV_DUMP
);
2524 dump_global_regs (dump_file
);
2525 timevar_pop (TV_DUMP
);
2528 gcc_assert (reload_completed
|| failure
);
2529 reload_completed
= !failure
;
2533 struct tree_opt_pass pass_global_alloc
=
2537 rest_of_handle_global_alloc
, /* execute */
2540 0, /* static_pass_number */
2541 TV_GLOBAL_ALLOC
, /* tv_id */
2542 0, /* properties_required */
2543 0, /* properties_provided */
2544 0, /* properties_destroyed */
2545 0, /* todo_flags_start */
2547 TODO_ggc_collect
, /* todo_flags_finish */