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, 2006, 2007
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
26 #include "coretypes.h"
29 #include "hard-reg-set.h"
35 #include "insn-config.h"
40 #include "tree-pass.h"
45 /* This pass of the compiler performs global register allocation.
46 It assigns hard register numbers to all the pseudo registers
47 that were not handled in local_alloc. Assignments are recorded
48 in the vector reg_renumber, not by changing the rtl code.
49 (Such changes are made by final). The entry point is
50 the function global_alloc.
52 After allocation is complete, the reload pass is run as a subroutine
53 of this pass, so that when a pseudo reg loses its hard reg due to
54 spilling it is possible to make a second attempt to find a hard
55 reg for it. The reload pass is independent in other respects
56 and it is run even when stupid register allocation is in use.
58 1. Assign allocation-numbers (allocnos) to the pseudo-registers
59 still needing allocations and to the pseudo-registers currently
60 allocated by local-alloc which may be spilled by reload.
61 Set up tables reg_allocno and allocno_reg to map
62 reg numbers to allocnos and vice versa.
63 max_allocno gets the number of allocnos in use.
65 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
66 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
67 for conflicts between allocnos and explicit hard register use
68 (which includes use of pseudo-registers allocated by local_alloc).
70 3. For each basic block
71 walk forward through the block, recording which
72 pseudo-registers and which hardware registers are live.
73 Build the conflict matrix between the pseudo-registers
74 and another of pseudo-registers versus hardware registers.
75 Also record the preferred hardware registers
76 for each pseudo-register.
78 4. Sort a table of the allocnos into order of
79 desirability of the variables.
81 5. Allocate the variables in that order; each if possible into
82 a preferred register, else into another register. */
84 /* Number of pseudo-registers which are candidates for allocation. */
86 static int max_allocno
;
88 /* Indexed by (pseudo) reg number, gives the allocno, or -1
89 for pseudo registers which are not to be allocated. */
91 static int *reg_allocno
;
96 /* Gives the number of consecutive hard registers needed by that
100 /* Number of calls crossed by each allocno. */
103 /* Number of calls that might throw crossed by each allocno. */
104 int throwing_calls_crossed
;
106 /* Number of refs to each allocno. */
109 /* Frequency of uses of each allocno. */
112 /* Guess at live length of each allocno.
113 This is actually the max of the live lengths of the regs. */
116 /* Set of hard regs conflicting with allocno N. */
118 HARD_REG_SET hard_reg_conflicts
;
120 /* Set of hard regs preferred by allocno N.
121 This is used to make allocnos go into regs that are copied to or from them,
122 when possible, to reduce register shuffling. */
124 HARD_REG_SET hard_reg_preferences
;
126 /* Similar, but just counts register preferences made in simple copy
127 operations, rather than arithmetic. These are given priority because
128 we can always eliminate an insn by using these, but using a register
129 in the above list won't always eliminate an insn. */
131 HARD_REG_SET hard_reg_copy_preferences
;
133 /* Similar to hard_reg_preferences, but includes bits for subsequent
134 registers when an allocno is multi-word. The above variable is used for
135 allocation while this is used to build reg_someone_prefers, below. */
137 HARD_REG_SET hard_reg_full_preferences
;
139 /* Set of hard registers that some later allocno has a preference for. */
141 HARD_REG_SET regs_someone_prefers
;
144 /* Set to true if allocno can't be allocated in the stack register. */
149 static struct allocno
*allocno
;
151 /* A vector of the integers from 0 to max_allocno-1,
152 sorted in the order of first-to-be-allocated first. */
154 static int *allocno_order
;
156 /* Define the number of bits in each element of `conflicts' and what
157 type that element has. We use the largest integer format on the
160 #define INT_BITS HOST_BITS_PER_WIDE_INT
161 #define INT_TYPE HOST_WIDE_INT
163 /* max_allocno by max_allocno array of bits,
164 recording whether two allocno's conflict (can't go in the same
167 `conflicts' is symmetric after the call to mirror_conflicts. */
169 static INT_TYPE
*conflicts
;
171 /* Number of ints required to hold max_allocno bits.
172 This is the length of a row in `conflicts'. */
174 static int allocno_row_words
;
176 /* Two macros to test or store 1 in an element of `conflicts'. */
178 #define CONFLICTP(I, J) \
179 (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS] \
180 & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS)))
182 /* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
184 #define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
188 INT_TYPE *p_ = (ALLOCNO_SET); \
190 for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
191 i_--, allocno_ += INT_BITS) \
193 unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
195 for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
203 /* Set of hard regs currently live (during scan of all insns). */
205 static HARD_REG_SET hard_regs_live
;
207 /* Set of registers that global-alloc isn't supposed to use. */
209 static HARD_REG_SET no_global_alloc_regs
;
211 /* Set of registers used so far. */
213 static HARD_REG_SET regs_used_so_far
;
215 /* Number of refs to each hard reg, as used by local alloc.
216 It is zero for a reg that contains global pseudos or is explicitly used. */
218 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
220 /* Frequency of uses of given hard reg. */
221 static int local_reg_freq
[FIRST_PSEUDO_REGISTER
];
223 /* Guess at live length of each hard reg, as used by local alloc.
224 This is actually the sum of the live lengths of the specific regs. */
226 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
228 /* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
229 element I, and hard register number J. */
231 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
233 /* Bit mask for allocnos live at current point in the scan. */
235 static INT_TYPE
*allocnos_live
;
237 /* Test, set or clear bit number I in allocnos_live,
238 a bit vector indexed by allocno. */
240 #define SET_ALLOCNO_LIVE(I) \
241 (allocnos_live[(unsigned) (I) / INT_BITS] \
242 |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
244 #define CLEAR_ALLOCNO_LIVE(I) \
245 (allocnos_live[(unsigned) (I) / INT_BITS] \
246 &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
248 /* This is turned off because it doesn't work right for DImode.
249 (And it is only used for DImode, so the other cases are worthless.)
250 The problem is that it isn't true that there is NO possibility of conflict;
251 only that there is no conflict if the two pseudos get the exact same regs.
252 If they were allocated with a partial overlap, there would be a conflict.
253 We can't safely turn off the conflict unless we have another way to
254 prevent the partial overlap.
256 Idea: change hard_reg_conflicts so that instead of recording which
257 hard regs the allocno may not overlap, it records where the allocno
258 may not start. Change both where it is used and where it is updated.
259 Then there is a way to record that (reg:DI 108) may start at 10
260 but not at 9 or 11. There is still the question of how to record
261 this semi-conflict between two pseudos. */
263 /* Reg pairs for which conflict after the current insn
264 is inhibited by a REG_NO_CONFLICT note.
265 If the table gets full, we ignore any other notes--that is conservative. */
266 #define NUM_NO_CONFLICT_PAIRS 4
267 /* Number of pairs in use in this insn. */
268 int n_no_conflict_pairs
;
269 static struct { int allocno1
, allocno2
;}
270 no_conflict_pairs
[NUM_NO_CONFLICT_PAIRS
];
273 /* Record all regs that are set in any one insn.
274 Communication from mark_reg_{store,clobber} and global_conflicts. */
276 static VEC(rtx
, heap
) *regs_set
;
279 /* Return true if *LOC contains an asm. */
282 insn_contains_asm_1 (rtx
*loc
, void *data ATTRIBUTE_UNUSED
)
286 if (GET_CODE (*loc
) == ASM_OPERANDS
)
292 /* Return true if INSN contains an ASM. */
295 insn_contains_asm (rtx insn
)
297 return for_each_rtx (&insn
, insn_contains_asm_1
, NULL
);
302 compute_regs_asm_clobbered (char *regs_asm_clobbered
)
306 memset (regs_asm_clobbered
, 0, sizeof (char) * FIRST_PSEUDO_REGISTER
);
311 FOR_BB_INSNS_REVERSE (bb
, insn
)
313 struct df_ref
**def_rec
;
314 if (insn_contains_asm (insn
))
315 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
317 struct df_ref
*def
= *def_rec
;
318 unsigned int dregno
= DF_REF_REGNO (def
);
319 if (dregno
< FIRST_PSEUDO_REGISTER
)
322 enum machine_mode mode
= GET_MODE (DF_REF_REAL_REG (def
));
323 unsigned int end
= dregno
324 + hard_regno_nregs
[dregno
][mode
] - 1;
325 for (i
= dregno
; i
<= end
; ++i
)
326 regs_asm_clobbered
[i
] = 1;
334 /* All registers that can be eliminated. */
336 static HARD_REG_SET eliminable_regset
;
338 static int allocno_compare (const void *, const void *);
339 static void global_conflicts (void);
340 static void mirror_conflicts (void);
341 static void expand_preferences (void);
342 static void prune_preferences (void);
343 static void find_reg (int, HARD_REG_SET
, int, int, int);
344 static void record_one_conflict (int);
345 static void record_conflicts (int *, int);
346 static void mark_reg_store (rtx
, rtx
, void *);
347 static void mark_reg_clobber (rtx
, rtx
, void *);
348 static void mark_reg_conflicts (rtx
);
349 static void mark_reg_death (rtx
);
350 static void set_preference (rtx
, rtx
);
351 static void dump_conflicts (FILE *);
352 static void reg_becomes_live (rtx
, rtx
, void *);
353 static void reg_dies (int, enum machine_mode
, struct insn_chain
*);
358 /* Look through the list of eliminable registers. Set ELIM_SET to the
359 set of registers which may be eliminated. Set NO_GLOBAL_SET to the
360 set of registers which may not be used across blocks.
362 This will normally be called with ELIM_SET as the file static
363 variable eliminable_regset, and NO_GLOBAL_SET as the file static
364 variable NO_GLOBAL_ALLOC_REGS. */
367 compute_regsets (HARD_REG_SET
*elim_set
,
368 HARD_REG_SET
*no_global_set
)
371 /* Like regs_ever_live, but 1 if a reg is set or clobbered from an asm.
372 Unlike regs_ever_live, elements of this array corresponding to
373 eliminable regs like the frame pointer are set if an asm sets them. */
374 char *regs_asm_clobbered
= alloca (FIRST_PSEUDO_REGISTER
* sizeof (char));
376 #ifdef ELIMINABLE_REGS
377 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
381 = (! flag_omit_frame_pointer
382 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
383 || FRAME_POINTER_REQUIRED
);
385 max_regno
= max_reg_num ();
390 /* A machine may have certain hard registers that
391 are safe to use only within a basic block. */
393 CLEAR_HARD_REG_SET (*no_global_set
);
394 CLEAR_HARD_REG_SET (*elim_set
);
396 compute_regs_asm_clobbered (regs_asm_clobbered
);
397 /* Build the regset of all eliminable registers and show we can't use those
398 that we already know won't be eliminated. */
399 #ifdef ELIMINABLE_REGS
400 for (i
= 0; i
< ARRAY_SIZE (eliminables
); i
++)
403 = (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
404 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
));
406 if (!regs_asm_clobbered
[eliminables
[i
].from
])
408 SET_HARD_REG_BIT (*elim_set
, eliminables
[i
].from
);
411 SET_HARD_REG_BIT (*no_global_set
, eliminables
[i
].from
);
413 else if (cannot_elim
)
414 error ("%s cannot be used in asm here",
415 reg_names
[eliminables
[i
].from
]);
417 df_set_regs_ever_live (eliminables
[i
].from
, true);
419 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
420 if (!regs_asm_clobbered
[HARD_FRAME_POINTER_REGNUM
])
422 SET_HARD_REG_BIT (*elim_set
, HARD_FRAME_POINTER_REGNUM
);
424 SET_HARD_REG_BIT (*no_global_set
, HARD_FRAME_POINTER_REGNUM
);
427 error ("%s cannot be used in asm here",
428 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
430 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
, true);
434 if (!regs_asm_clobbered
[FRAME_POINTER_REGNUM
])
436 SET_HARD_REG_BIT (*elim_set
, FRAME_POINTER_REGNUM
);
438 SET_HARD_REG_BIT (*no_global_set
, FRAME_POINTER_REGNUM
);
441 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
443 df_set_regs_ever_live (FRAME_POINTER_REGNUM
, true);
447 /* Perform allocation of pseudo-registers not allocated by local_alloc.
449 Return value is nonzero if reload failed
450 and we must not do any more for this function. */
458 compute_regsets (&eliminable_regset
, &no_global_alloc_regs
);
460 /* Track which registers have already been used. Start with registers
461 explicitly in the rtl, then registers allocated by local register
464 CLEAR_HARD_REG_SET (regs_used_so_far
);
465 #ifdef LEAF_REGISTERS
466 /* If we are doing the leaf function optimization, and this is a leaf
467 function, it means that the registers that take work to save are those
468 that need a register window. So prefer the ones that can be used in
471 const char *cheap_regs
;
472 const char *const leaf_regs
= LEAF_REGISTERS
;
474 if (only_leaf_regs_used () && leaf_function_p ())
475 cheap_regs
= leaf_regs
;
477 cheap_regs
= call_used_regs
;
478 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
479 if (df_regs_ever_live_p (i
) || cheap_regs
[i
])
480 SET_HARD_REG_BIT (regs_used_so_far
, i
);
483 /* We consider registers that do not have to be saved over calls as if
484 they were already used since there is no cost in using them. */
485 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
486 if (df_regs_ever_live_p (i
) || call_used_regs
[i
])
487 SET_HARD_REG_BIT (regs_used_so_far
, i
);
490 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
491 if (reg_renumber
[i
] >= 0)
492 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
494 /* Establish mappings from register number to allocation number
495 and vice versa. In the process, count the allocnos. */
497 reg_allocno
= XNEWVEC (int, max_regno
);
499 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
503 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
504 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
505 that we are supposed to refrain from putting in a hard reg.
506 -2 means do make an allocno but don't allocate it. */
507 if (REG_N_REFS (i
) != 0 && REG_LIVE_LENGTH (i
) != -1
508 /* Don't allocate pseudos that cross calls,
509 if this function receives a nonlocal goto. */
510 && (! current_function_has_nonlocal_label
511 || REG_N_CALLS_CROSSED (i
) == 0))
513 reg_allocno
[i
] = max_allocno
++;
514 gcc_assert (REG_LIVE_LENGTH (i
));
519 allocno
= XCNEWVEC (struct allocno
, max_allocno
);
521 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
522 if (reg_allocno
[i
] >= 0)
524 int num
= reg_allocno
[i
];
525 allocno
[num
].reg
= i
;
526 allocno
[num
].size
= PSEUDO_REGNO_SIZE (i
);
527 allocno
[num
].calls_crossed
+= REG_N_CALLS_CROSSED (i
);
528 allocno
[num
].throwing_calls_crossed
529 += REG_N_THROWING_CALLS_CROSSED (i
);
530 allocno
[num
].n_refs
+= REG_N_REFS (i
);
531 allocno
[num
].freq
+= REG_FREQ (i
);
532 if (allocno
[num
].live_length
< REG_LIVE_LENGTH (i
))
533 allocno
[num
].live_length
= REG_LIVE_LENGTH (i
);
536 /* Calculate amount of usage of each hard reg by pseudos
537 allocated by local-alloc. This is to see if we want to
539 memset (local_reg_live_length
, 0, sizeof local_reg_live_length
);
540 memset (local_reg_n_refs
, 0, sizeof local_reg_n_refs
);
541 memset (local_reg_freq
, 0, sizeof local_reg_freq
);
542 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
543 if (reg_renumber
[i
] >= 0)
545 int regno
= reg_renumber
[i
];
546 int endregno
= end_hard_regno (PSEUDO_REGNO_MODE (i
), regno
);
549 for (j
= regno
; j
< endregno
; j
++)
551 local_reg_n_refs
[j
] += REG_N_REFS (i
);
552 local_reg_freq
[j
] += REG_FREQ (i
);
553 local_reg_live_length
[j
] += REG_LIVE_LENGTH (i
);
557 /* We can't override local-alloc for a reg used not just by local-alloc. */
558 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
559 if (df_regs_ever_live_p (i
))
560 local_reg_n_refs
[i
] = 0, local_reg_freq
[i
] = 0;
564 for (i
= FIRST_PSEUDO_REGISTER
; i
< (size_t) max_regno
; i
++)
566 fprintf (dump_file
, "%d REG_N_REFS=%d, REG_FREQ=%d, REG_LIVE_LENGTH=%d\n",
567 (int)i
, REG_N_REFS (i
), REG_FREQ (i
), REG_LIVE_LENGTH (i
));
569 fprintf (dump_file
, "regs_ever_live =");
570 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
571 if (df_regs_ever_live_p (i
))
572 fprintf (dump_file
, " %d", (int)i
);
573 fprintf (dump_file
, "\n");
575 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
577 /* We used to use alloca here, but the size of what it would try to
578 allocate would occasionally cause it to exceed the stack limit and
579 cause unpredictable core dumps. Some examples were > 2Mb in size. */
580 conflicts
= XCNEWVEC (INT_TYPE
, max_allocno
* allocno_row_words
);
582 allocnos_live
= XNEWVEC (INT_TYPE
, allocno_row_words
);
584 /* If there is work to be done (at least one reg to allocate),
585 perform global conflict analysis and allocate the regs. */
589 /* Make a vector that mark_reg_{store,clobber} will store in. */
591 regs_set
= VEC_alloc (rtx
, heap
, 10);
593 /* Scan all the insns and compute the conflicts among allocnos
594 and between allocnos and hard regs. */
600 /* Eliminate conflicts between pseudos and eliminable registers. If
601 the register is not eliminated, the pseudo won't really be able to
602 live in the eliminable register, so the conflict doesn't matter.
603 If we do eliminate the register, the conflict will no longer exist.
604 So in either case, we can ignore the conflict. Likewise for
607 for (i
= 0; i
< (size_t) max_allocno
; i
++)
609 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_conflicts
,
611 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_copy_preferences
,
613 AND_COMPL_HARD_REG_SET (allocno
[i
].hard_reg_preferences
,
617 /* Try to expand the preferences by merging them between allocnos. */
619 expand_preferences ();
621 /* Determine the order to allocate the remaining pseudo registers. */
623 allocno_order
= XNEWVEC (int, max_allocno
);
624 for (i
= 0; i
< (size_t) max_allocno
; i
++)
625 allocno_order
[i
] = i
;
627 /* Default the size to 1, since allocno_compare uses it to divide by.
628 Also convert allocno_live_length of zero to -1. A length of zero
629 can occur when all the registers for that allocno have reg_live_length
630 equal to -2. In this case, we want to make an allocno, but not
631 allocate it. So avoid the divide-by-zero and set it to a low
634 for (i
= 0; i
< (size_t) max_allocno
; i
++)
636 if (allocno
[i
].size
== 0)
638 if (allocno
[i
].live_length
== 0)
639 allocno
[i
].live_length
= -1;
642 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
644 prune_preferences ();
647 dump_conflicts (dump_file
);
649 /* Try allocating them, one by one, in that order,
650 except for parameters marked with reg_live_length[regno] == -2. */
652 for (i
= 0; i
< (size_t) max_allocno
; i
++)
653 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] < 0
654 && REG_LIVE_LENGTH (allocno
[allocno_order
[i
]].reg
) >= 0)
656 /* If we have more than one register class,
657 first try allocating in the class that is cheapest
658 for this pseudo-reg. If that fails, try any reg. */
659 if (N_REG_CLASSES
> 1)
661 find_reg (allocno_order
[i
], 0, 0, 0, 0);
662 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
665 if (reg_alternate_class (allocno
[allocno_order
[i
]].reg
) != NO_REGS
)
666 find_reg (allocno_order
[i
], 0, 1, 0, 0);
669 free (allocno_order
);
672 /* Do the reloads now while the allocno data still exists, so that we can
673 try to assign new hard regs to any pseudo regs that are spilled. */
675 #if 0 /* We need to eliminate regs even if there is no rtl code,
676 for the sake of debugging information. */
677 if (n_basic_blocks
> NUM_FIXED_BLOCKS
)
680 build_insn_chain (get_insns ());
681 retval
= reload (get_insns (), 1);
688 free (allocnos_live
);
693 /* Sort predicate for ordering the allocnos.
694 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
697 allocno_compare (const void *v1p
, const void *v2p
)
699 int v1
= *(const int *)v1p
, v2
= *(const int *)v2p
;
700 /* Note that the quotient will never be bigger than
701 the value of floor_log2 times the maximum number of
702 times a register can occur in one insn (surely less than 100)
703 weighted by the frequency (maximally REG_FREQ_MAX).
704 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
706 = (((double) (floor_log2 (allocno
[v1
].n_refs
) * allocno
[v1
].freq
)
707 / allocno
[v1
].live_length
)
708 * (10000 / REG_FREQ_MAX
) * allocno
[v1
].size
);
710 = (((double) (floor_log2 (allocno
[v2
].n_refs
) * allocno
[v2
].freq
)
711 / allocno
[v2
].live_length
)
712 * (10000 / REG_FREQ_MAX
) * allocno
[v2
].size
);
716 /* If regs are equally good, sort by allocno,
717 so that the results of qsort leave nothing to chance. */
721 /* Scan the rtl code and record all conflicts and register preferences in the
722 conflict matrices and preference tables. */
725 global_conflicts (void)
730 int *block_start_allocnos
;
732 block_start_allocnos
= XNEWVEC (int, max_allocno
);
736 memset (allocnos_live
, 0, allocno_row_words
* sizeof (INT_TYPE
));
738 /* Initialize table of registers currently live
739 to the state at the beginning of this basic block.
740 This also marks the conflicts among hard registers
741 and any allocnos that are live.
743 For pseudo-regs, there is only one bit for each one
744 no matter how many hard regs it occupies.
745 This is ok; we know the size from PSEUDO_REGNO_SIZE.
746 For explicit hard regs, we cannot know the size that way
747 since one hard reg can be used with various sizes.
748 Therefore, we must require that all the hard regs
749 implicitly live as part of a multi-word hard reg
750 be explicitly marked in basic_block_live_at_start. */
754 reg_set_iterator rsi
;
756 REG_SET_TO_HARD_REG_SET (hard_regs_live
, DF_RA_LIVE_TOP (b
));
757 EXECUTE_IF_SET_IN_REG_SET (DF_RA_LIVE_TOP (b
), FIRST_PSEUDO_REGISTER
, i
, rsi
)
759 int a
= reg_allocno
[i
];
762 SET_ALLOCNO_LIVE (a
);
763 block_start_allocnos
[ax
++] = a
;
765 else if ((a
= reg_renumber
[i
]) >= 0)
766 add_to_hard_reg_set (&hard_regs_live
, PSEUDO_REGNO_MODE (i
), a
);
769 /* Record that each allocno now live conflicts with each hard reg
772 It is not necessary to mark any conflicts between pseudos at
773 this point, even for pseudos which are live at the start of
776 Given two pseudos X and Y and any point in the CFG P.
778 On any path to point P where X and Y are live one of the
779 following conditions must be true:
781 1. X is live at some instruction on the path that
784 2. Y is live at some instruction on the path that
787 3. Either X or Y is not evaluated on the path to P
788 (i.e. it is used uninitialized) and thus the
789 conflict can be ignored.
791 In cases #1 and #2 the conflict will be recorded when we
792 scan the instruction that makes either X or Y become live. */
793 record_conflicts (block_start_allocnos
, ax
);
795 #ifdef EH_RETURN_DATA_REGNO
796 if (bb_has_eh_pred (b
))
802 unsigned int regno
= EH_RETURN_DATA_REGNO (i
);
803 if (regno
== INVALID_REGNUM
)
805 record_one_conflict (regno
);
810 /* Pseudos can't go in stack regs at the start of a basic block that
811 is reached by an abnormal edge. Likewise for call clobbered regs,
812 because caller-save, fixup_abnormal_edges and possibly the table
813 driven EH machinery are not quite ready to handle such regs live
814 across such edges. */
819 FOR_EACH_EDGE (e
, ei
, b
->preds
)
820 if (e
->flags
& EDGE_ABNORMAL
)
826 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, ax
,
828 allocno
[ax
].no_stack_reg
= 1;
830 for (ax
= FIRST_STACK_REG
; ax
<= LAST_STACK_REG
; ax
++)
831 record_one_conflict (ax
);
834 /* No need to record conflicts for call clobbered regs if we have
835 nonlocal labels around, as we don't ever try to allocate such
836 regs in this case. */
837 if (! current_function_has_nonlocal_label
)
838 for (ax
= 0; ax
< FIRST_PSEUDO_REGISTER
; ax
++)
839 if (call_used_regs
[ax
])
840 record_one_conflict (ax
);
847 /* Scan the code of this basic block, noting which allocnos
848 and hard regs are born or die. When one is born,
849 record a conflict with all others currently live. */
853 RTX_CODE code
= GET_CODE (insn
);
856 gcc_assert (VEC_empty (rtx
, regs_set
));
857 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
861 for (link
= REG_NOTES (insn
);
862 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
863 link
= XEXP (link
, 1))
864 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
866 no_conflict_pairs
[i
].allocno1
867 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
868 no_conflict_pairs
[i
].allocno2
869 = reg_allocno
[REGNO (XEXP (link
, 0))];
874 /* Mark any registers clobbered by INSN as live,
875 so they conflict with the inputs. */
877 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
880 /* Auto-increment instructions clobber the base
882 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
883 if (REG_NOTE_KIND (link
) == REG_INC
)
884 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
886 /* Mark any registers dead after INSN as dead now. */
888 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
889 if (REG_NOTE_KIND (link
) == REG_DEAD
)
890 mark_reg_death (XEXP (link
, 0));
892 /* Mark any registers set in INSN as live,
893 and mark them as conflicting with all other live regs.
894 Clobbers are processed again, so they conflict with
895 the registers that are set. */
897 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
899 /* If INSN has multiple outputs, then any reg that dies here
900 and is used inside of an output
901 must conflict with the other outputs.
903 It is unsafe to use !single_set here since it will ignore an
904 unused output. Just because an output is unused does not mean
905 the compiler can assume the side effect will not occur.
906 Consider if REG appears in the address of an output and we
907 reload the output. If we allocate REG to the same hard
908 register as an unused output we could set the hard register
909 before the output reload insn. */
910 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
911 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
912 if (REG_NOTE_KIND (link
) == REG_DEAD
)
914 int used_in_output
= 0;
916 rtx reg
= XEXP (link
, 0);
918 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
920 rtx set
= XVECEXP (PATTERN (insn
), 0, i
);
921 if (GET_CODE (set
) == SET
922 && !REG_P (SET_DEST (set
))
923 && !rtx_equal_p (reg
, SET_DEST (set
))
924 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
928 mark_reg_conflicts (reg
);
931 /* Mark any registers set in INSN and then never used. */
933 while (!VEC_empty (rtx
, regs_set
))
935 rtx reg
= VEC_pop (rtx
, regs_set
);
936 rtx note
= find_regno_note (insn
, REG_UNUSED
,
939 mark_reg_death (XEXP (note
, 0));
943 if (insn
== BB_END (b
))
945 insn
= NEXT_INSN (insn
);
950 free (block_start_allocnos
);
953 /* Expand the preference information by looking for cases where one allocno
954 dies in an insn that sets an allocno. If those two allocnos don't conflict,
955 merge any preferences between those allocnos. */
958 expand_preferences (void)
964 /* We only try to handle the most common cases here. Most of the cases
965 where this wins are reg-reg copies. */
967 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
969 && (set
= single_set (insn
)) != 0
970 && REG_P (SET_DEST (set
))
971 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
972 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
973 if (REG_NOTE_KIND (link
) == REG_DEAD
974 && REG_P (XEXP (link
, 0))
975 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
976 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
977 reg_allocno
[REGNO (XEXP (link
, 0))]))
979 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
980 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
982 if (XEXP (link
, 0) == SET_SRC (set
))
984 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_copy_preferences
,
985 allocno
[a2
].hard_reg_copy_preferences
);
986 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_copy_preferences
,
987 allocno
[a1
].hard_reg_copy_preferences
);
990 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_preferences
,
991 allocno
[a2
].hard_reg_preferences
);
992 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_preferences
,
993 allocno
[a1
].hard_reg_preferences
);
994 IOR_HARD_REG_SET (allocno
[a1
].hard_reg_full_preferences
,
995 allocno
[a2
].hard_reg_full_preferences
);
996 IOR_HARD_REG_SET (allocno
[a2
].hard_reg_full_preferences
,
997 allocno
[a1
].hard_reg_full_preferences
);
1001 /* Prune the preferences for global registers to exclude registers that cannot
1004 Compute `regs_someone_prefers', which is a bitmask of the hard registers
1005 that are preferred by conflicting registers of lower priority. If possible,
1006 we will avoid using these registers. */
1009 prune_preferences (void)
1013 int *allocno_to_order
= XNEWVEC (int, max_allocno
);
1015 /* Scan least most important to most important.
1016 For each allocno, remove from preferences registers that cannot be used,
1017 either because of conflicts or register type. Then compute all registers
1018 preferred by each lower-priority register that conflicts. */
1020 for (i
= max_allocno
- 1; i
>= 0; i
--)
1024 num
= allocno_order
[i
];
1025 allocno_to_order
[num
] = i
;
1026 COPY_HARD_REG_SET (temp
, allocno
[num
].hard_reg_conflicts
);
1028 if (allocno
[num
].calls_crossed
== 0)
1029 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
1031 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
1033 IOR_COMPL_HARD_REG_SET
1035 reg_class_contents
[(int) reg_preferred_class (allocno
[num
].reg
)]);
1037 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, temp
);
1038 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, temp
);
1039 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_full_preferences
, temp
);
1042 for (i
= max_allocno
- 1; i
>= 0; i
--)
1044 /* Merge in the preferences of lower-priority registers (they have
1045 already been pruned). If we also prefer some of those registers,
1046 don't exclude them unless we are of a smaller size (in which case
1047 we want to give the lower-priority allocno the first chance for
1048 these registers). */
1049 HARD_REG_SET temp
, temp2
;
1052 num
= allocno_order
[i
];
1054 CLEAR_HARD_REG_SET (temp
);
1055 CLEAR_HARD_REG_SET (temp2
);
1057 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ num
* allocno_row_words
,
1060 if (allocno_to_order
[allocno2
] > i
)
1062 if (allocno
[allocno2
].size
<= allocno
[num
].size
)
1063 IOR_HARD_REG_SET (temp
,
1064 allocno
[allocno2
].hard_reg_full_preferences
);
1066 IOR_HARD_REG_SET (temp2
,
1067 allocno
[allocno2
].hard_reg_full_preferences
);
1071 AND_COMPL_HARD_REG_SET (temp
, allocno
[num
].hard_reg_full_preferences
);
1072 IOR_HARD_REG_SET (temp
, temp2
);
1073 COPY_HARD_REG_SET (allocno
[num
].regs_someone_prefers
, temp
);
1075 free (allocno_to_order
);
1078 /* Assign a hard register to allocno NUM; look for one that is the beginning
1079 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
1080 The registers marked in PREFREGS are tried first.
1082 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
1083 be used for this allocation.
1085 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
1086 Otherwise ignore that preferred class and use the alternate class.
1088 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
1089 will have to be saved and restored at calls.
1091 RETRYING is nonzero if this is called from retry_global_alloc.
1093 If we find one, record it in reg_renumber.
1094 If not, do nothing. */
1097 find_reg (int num
, HARD_REG_SET losers
, int alt_regs_p
, int accept_call_clobbered
, int retrying
)
1099 int i
, best_reg
, pass
;
1100 HARD_REG_SET used
, used1
, used2
;
1102 enum reg_class
class = (alt_regs_p
1103 ? reg_alternate_class (allocno
[num
].reg
)
1104 : reg_preferred_class (allocno
[num
].reg
));
1105 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno
[num
].reg
);
1107 if (accept_call_clobbered
)
1108 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
1109 else if (allocno
[num
].calls_crossed
== 0)
1110 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
1112 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
1114 /* Some registers should not be allocated in global-alloc. */
1115 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
1117 IOR_HARD_REG_SET (used1
, losers
);
1119 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
1120 COPY_HARD_REG_SET (used2
, used1
);
1122 IOR_HARD_REG_SET (used1
, allocno
[num
].hard_reg_conflicts
);
1124 #ifdef CANNOT_CHANGE_MODE_CLASS
1125 cannot_change_mode_set_regs (&used1
, mode
, allocno
[num
].reg
);
1128 /* Try each hard reg to see if it fits. Do this in two passes.
1129 In the first pass, skip registers that are preferred by some other pseudo
1130 to give it a better chance of getting one of those registers. Only if
1131 we can't get a register when excluding those do we take one of them.
1132 However, we never allocate a register for the first time in pass 0. */
1134 COPY_HARD_REG_SET (used
, used1
);
1135 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
1136 IOR_HARD_REG_SET (used
, allocno
[num
].regs_someone_prefers
);
1139 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
1140 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
1144 COPY_HARD_REG_SET (used
, used1
);
1145 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1147 #ifdef REG_ALLOC_ORDER
1148 int regno
= reg_alloc_order
[i
];
1152 if (! TEST_HARD_REG_BIT (used
, regno
)
1153 && HARD_REGNO_MODE_OK (regno
, mode
)
1154 && (allocno
[num
].calls_crossed
== 0
1155 || accept_call_clobbered
1156 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
)))
1159 int lim
= end_hard_regno (mode
, regno
);
1162 && ! TEST_HARD_REG_BIT (used
, j
));
1169 #ifndef REG_ALLOC_ORDER
1170 i
= j
; /* Skip starting points we know will lose */
1176 /* See if there is a preferred register with the same class as the register
1177 we allocated above. Making this restriction prevents register
1178 preferencing from creating worse register allocation.
1180 Remove from the preferred registers and conflicting registers. Note that
1181 additional conflicts may have been added after `prune_preferences' was
1184 First do this for those register with copy preferences, then all
1185 preferred registers. */
1187 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_copy_preferences
, used
);
1188 if (!hard_reg_set_empty_p (allocno
[num
].hard_reg_copy_preferences
)
1191 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1192 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_copy_preferences
, i
)
1193 && HARD_REGNO_MODE_OK (i
, mode
)
1194 && (allocno
[num
].calls_crossed
== 0
1195 || accept_call_clobbered
1196 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1197 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1198 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1199 REGNO_REG_CLASS (best_reg
))
1200 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1201 REGNO_REG_CLASS (i
))))
1204 int lim
= end_hard_regno (mode
, i
);
1207 && ! TEST_HARD_REG_BIT (used
, j
)
1208 && (REGNO_REG_CLASS (j
)
1209 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1210 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1211 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1212 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1213 REGNO_REG_CLASS (j
))));
1223 AND_COMPL_HARD_REG_SET (allocno
[num
].hard_reg_preferences
, used
);
1224 if (!hard_reg_set_empty_p (allocno
[num
].hard_reg_preferences
)
1227 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1228 if (TEST_HARD_REG_BIT (allocno
[num
].hard_reg_preferences
, i
)
1229 && HARD_REGNO_MODE_OK (i
, mode
)
1230 && (allocno
[num
].calls_crossed
== 0
1231 || accept_call_clobbered
1232 || ! HARD_REGNO_CALL_PART_CLOBBERED (i
, mode
))
1233 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
1234 || reg_class_subset_p (REGNO_REG_CLASS (i
),
1235 REGNO_REG_CLASS (best_reg
))
1236 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
1237 REGNO_REG_CLASS (i
))))
1240 int lim
= end_hard_regno (mode
, i
);
1243 && ! TEST_HARD_REG_BIT (used
, j
)
1244 && (REGNO_REG_CLASS (j
)
1245 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
1246 || reg_class_subset_p (REGNO_REG_CLASS (j
),
1247 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
1248 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
1249 REGNO_REG_CLASS (j
))));
1260 /* If we haven't succeeded yet, try with caller-saves.
1261 We need not check to see if the current function has nonlocal
1262 labels because we don't put any pseudos that are live over calls in
1263 registers in that case. */
1265 if (flag_caller_saves
&& best_reg
< 0)
1267 /* Did not find a register. If it would be profitable to
1268 allocate a call-clobbered register and save and restore it
1269 around calls, do that. Don't do this if it crosses any calls
1270 that might throw. */
1271 if (! accept_call_clobbered
1272 && allocno
[num
].calls_crossed
!= 0
1273 && allocno
[num
].throwing_calls_crossed
== 0
1274 && CALLER_SAVE_PROFITABLE (allocno
[num
].n_refs
,
1275 allocno
[num
].calls_crossed
))
1277 HARD_REG_SET new_losers
;
1279 CLEAR_HARD_REG_SET (new_losers
);
1281 COPY_HARD_REG_SET (new_losers
, losers
);
1283 IOR_HARD_REG_SET(new_losers
, losing_caller_save_reg_set
);
1284 find_reg (num
, new_losers
, alt_regs_p
, 1, retrying
);
1285 if (reg_renumber
[allocno
[num
].reg
] >= 0)
1287 caller_save_needed
= 1;
1293 /* If we haven't succeeded yet,
1294 see if some hard reg that conflicts with us
1295 was utilized poorly by local-alloc.
1296 If so, kick out the regs that were put there by local-alloc
1297 so we can use it instead. */
1298 if (best_reg
< 0 && !retrying
1299 /* Let's not bother with multi-reg allocnos. */
1300 && allocno
[num
].size
== 1
1301 && REG_BASIC_BLOCK (allocno
[num
].reg
) == REG_BLOCK_GLOBAL
)
1303 /* Count from the end, to find the least-used ones first. */
1304 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1306 #ifdef REG_ALLOC_ORDER
1307 int regno
= reg_alloc_order
[i
];
1312 if (local_reg_n_refs
[regno
] != 0
1313 /* Don't use a reg no good for this pseudo. */
1314 && ! TEST_HARD_REG_BIT (used2
, regno
)
1315 && HARD_REGNO_MODE_OK (regno
, mode
)
1316 /* The code below assumes that we need only a single
1317 register, but the check of allocno[num].size above
1318 was not enough. Sometimes we need more than one
1319 register for a single-word value. */
1320 && hard_regno_nregs
[regno
][mode
] == 1
1321 && (allocno
[num
].calls_crossed
== 0
1322 || accept_call_clobbered
1323 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno
, mode
))
1324 #ifdef CANNOT_CHANGE_MODE_CLASS
1325 && ! invalid_mode_change_p (regno
, REGNO_REG_CLASS (regno
),
1329 && (!allocno
[num
].no_stack_reg
1330 || regno
< FIRST_STACK_REG
|| regno
> LAST_STACK_REG
)
1334 /* We explicitly evaluate the divide results into temporary
1335 variables so as to avoid excess precision problems that occur
1336 on an i386-unknown-sysv4.2 (unixware) host. */
1338 double tmp1
= ((double) local_reg_freq
[regno
] * local_reg_n_refs
[regno
]
1339 / local_reg_live_length
[regno
]);
1340 double tmp2
= ((double) allocno
[num
].freq
* allocno
[num
].n_refs
1341 / allocno
[num
].live_length
);
1345 /* Hard reg REGNO was used less in total by local regs
1346 than it would be used by this one allocno! */
1350 fprintf (dump_file
, "Regno %d better for global %d, ",
1351 regno
, allocno
[num
].reg
);
1352 fprintf (dump_file
, "fr:%d, ll:%d, nr:%d ",
1353 allocno
[num
].freq
, allocno
[num
].live_length
,
1354 allocno
[num
].n_refs
);
1355 fprintf (dump_file
, "(was: fr:%d, ll:%d, nr:%d)\n",
1356 local_reg_freq
[regno
],
1357 local_reg_live_length
[regno
],
1358 local_reg_n_refs
[regno
]);
1361 for (k
= 0; k
< max_regno
; k
++)
1362 if (reg_renumber
[k
] >= 0)
1364 int r
= reg_renumber
[k
];
1366 = end_hard_regno (PSEUDO_REGNO_MODE (k
), r
);
1368 if (regno
>= r
&& regno
< endregno
)
1372 "Local Reg %d now on stack\n", k
);
1373 reg_renumber
[k
] = -1;
1384 /* Did we find a register? */
1389 HARD_REG_SET this_reg
;
1391 /* Yes. Record it as the hard register of this pseudo-reg. */
1392 reg_renumber
[allocno
[num
].reg
] = best_reg
;
1394 /* Make a set of the hard regs being allocated. */
1395 CLEAR_HARD_REG_SET (this_reg
);
1396 lim
= end_hard_regno (mode
, best_reg
);
1397 for (j
= best_reg
; j
< lim
; j
++)
1399 SET_HARD_REG_BIT (this_reg
, j
);
1400 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1401 /* This is no longer a reg used just by local regs. */
1402 local_reg_n_refs
[j
] = 0;
1403 local_reg_freq
[j
] = 0;
1405 /* For each other pseudo-reg conflicting with this one,
1406 mark it as conflicting with the hard regs this one occupies. */
1408 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts
+ lim
* allocno_row_words
, j
,
1410 IOR_HARD_REG_SET (allocno
[j
].hard_reg_conflicts
, this_reg
);
1415 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1416 Perhaps it had previously seemed not worth a hard reg,
1417 or perhaps its old hard reg has been commandeered for reloads.
1418 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1419 they do not appear to be allocated.
1420 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1423 retry_global_alloc (int regno
, HARD_REG_SET forbidden_regs
)
1425 int alloc_no
= reg_allocno
[regno
];
1428 /* If we have more than one register class,
1429 first try allocating in the class that is cheapest
1430 for this pseudo-reg. If that fails, try any reg. */
1431 if (N_REG_CLASSES
> 1)
1432 find_reg (alloc_no
, forbidden_regs
, 0, 0, 1);
1433 if (reg_renumber
[regno
] < 0
1434 && reg_alternate_class (regno
) != NO_REGS
)
1435 find_reg (alloc_no
, forbidden_regs
, 1, 0, 1);
1437 /* If we found a register, modify the RTL for the register to
1438 show the hard register, and mark that register live. */
1439 if (reg_renumber
[regno
] >= 0)
1441 SET_REGNO (regno_reg_rtx
[regno
], reg_renumber
[regno
]);
1442 mark_home_live (regno
);
1447 /* Record a conflict between register REGNO
1448 and everything currently live.
1449 REGNO must not be a pseudo reg that was allocated
1450 by local_alloc; such numbers must be translated through
1451 reg_renumber before calling here. */
1454 record_one_conflict (int regno
)
1458 if (regno
< FIRST_PSEUDO_REGISTER
)
1459 /* When a hard register becomes live,
1460 record conflicts with live pseudo regs. */
1461 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live
, j
,
1463 SET_HARD_REG_BIT (allocno
[j
].hard_reg_conflicts
, regno
);
1466 /* When a pseudo-register becomes live,
1467 record conflicts first with hard regs,
1468 then with other pseudo regs. */
1470 int ialloc
= reg_allocno
[regno
];
1471 int ialloc_prod
= ialloc
* allocno_row_words
;
1473 IOR_HARD_REG_SET (allocno
[ialloc
].hard_reg_conflicts
, hard_regs_live
);
1474 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1475 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1479 /* Record all allocnos currently live as conflicting
1480 with all hard regs currently live.
1482 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1483 are currently live. Their bits are also flagged in allocnos_live. */
1486 record_conflicts (int *allocno_vec
, int len
)
1489 IOR_HARD_REG_SET (allocno
[allocno_vec
[len
]].hard_reg_conflicts
,
1493 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1495 mirror_conflicts (void)
1498 int rw
= allocno_row_words
;
1499 int rwb
= rw
* INT_BITS
;
1500 INT_TYPE
*p
= conflicts
;
1501 INT_TYPE
*q0
= conflicts
, *q1
, *q2
;
1502 unsigned INT_TYPE mask
;
1504 for (i
= max_allocno
- 1, mask
= 1; i
>= 0; i
--, mask
<<= 1)
1511 for (j
= allocno_row_words
- 1, q1
= q0
; j
>= 0; j
--, q1
+= rwb
)
1513 unsigned INT_TYPE word
;
1515 for (word
= (unsigned INT_TYPE
) *p
++, q2
= q1
; word
;
1516 word
>>= 1, q2
+= rw
)
1525 /* Handle the case where REG is set by the insn being scanned,
1526 during the forward scan to accumulate conflicts.
1527 Store a 1 in regs_live or allocnos_live for this register, record how many
1528 consecutive hardware registers it actually needs,
1529 and record a conflict with all other registers already live.
1531 Note that even if REG does not remain alive after this insn,
1532 we must mark it here as live, to ensure a conflict between
1533 REG and any other regs set in this insn that really do live.
1534 This is because those other regs could be considered after this.
1536 REG might actually be something other than a register;
1537 if so, we do nothing.
1539 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1540 a REG_INC note was found for it). */
1543 mark_reg_store (rtx reg
, rtx setter
, void *data ATTRIBUTE_UNUSED
)
1547 if (GET_CODE (reg
) == SUBREG
)
1548 reg
= SUBREG_REG (reg
);
1553 VEC_safe_push (rtx
, heap
, regs_set
, reg
);
1555 if (setter
&& GET_CODE (setter
) != CLOBBER
)
1556 set_preference (reg
, SET_SRC (setter
));
1558 regno
= REGNO (reg
);
1560 /* Either this is one of the max_allocno pseudo regs not allocated,
1561 or it is or has a hardware reg. First handle the pseudo-regs. */
1562 if (regno
>= FIRST_PSEUDO_REGISTER
)
1564 if (reg_allocno
[regno
] >= 0)
1566 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1567 record_one_conflict (regno
);
1571 if (reg_renumber
[regno
] >= 0)
1572 regno
= reg_renumber
[regno
];
1574 /* Handle hardware regs (and pseudos allocated to hard regs). */
1575 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1577 int last
= end_hard_regno (GET_MODE (reg
), regno
);
1578 while (regno
< last
)
1580 record_one_conflict (regno
);
1581 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1587 /* Like mark_reg_store except notice just CLOBBERs; ignore SETs. */
1590 mark_reg_clobber (rtx reg
, rtx setter
, void *data
)
1592 if (GET_CODE (setter
) == CLOBBER
)
1593 mark_reg_store (reg
, setter
, data
);
1596 /* Record that REG has conflicts with all the regs currently live.
1597 Do not mark REG itself as live. */
1600 mark_reg_conflicts (rtx reg
)
1604 if (GET_CODE (reg
) == SUBREG
)
1605 reg
= SUBREG_REG (reg
);
1610 regno
= REGNO (reg
);
1612 /* Either this is one of the max_allocno pseudo regs not allocated,
1613 or it is or has a hardware reg. First handle the pseudo-regs. */
1614 if (regno
>= FIRST_PSEUDO_REGISTER
)
1616 if (reg_allocno
[regno
] >= 0)
1617 record_one_conflict (regno
);
1620 if (reg_renumber
[regno
] >= 0)
1621 regno
= reg_renumber
[regno
];
1623 /* Handle hardware regs (and pseudos allocated to hard regs). */
1624 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1626 int last
= end_hard_regno (GET_MODE (reg
), regno
);
1627 while (regno
< last
)
1629 record_one_conflict (regno
);
1635 /* Mark REG as being dead (following the insn being scanned now).
1636 Store a 0 in regs_live or allocnos_live for this register. */
1639 mark_reg_death (rtx reg
)
1641 int regno
= REGNO (reg
);
1643 /* Either this is one of the max_allocno pseudo regs not allocated,
1644 or it is a hardware reg. First handle the pseudo-regs. */
1645 if (regno
>= FIRST_PSEUDO_REGISTER
)
1647 if (reg_allocno
[regno
] >= 0)
1648 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1651 /* For pseudo reg, see if it has been assigned a hardware reg. */
1652 if (reg_renumber
[regno
] >= 0)
1653 regno
= reg_renumber
[regno
];
1655 /* Handle hardware regs (and pseudos allocated to hard regs). */
1656 if (regno
< FIRST_PSEUDO_REGISTER
&& ! fixed_regs
[regno
])
1657 /* Pseudo regs already assigned hardware regs are treated
1658 almost the same as explicit hardware regs. */
1659 remove_from_hard_reg_set (&hard_regs_live
, GET_MODE (reg
), regno
);
1662 /* Try to set a preference for an allocno to a hard register.
1663 We are passed DEST and SRC which are the operands of a SET. It is known
1664 that SRC is a register. If SRC or the first operand of SRC is a register,
1665 try to set a preference. If one of the two is a hard register and the other
1666 is a pseudo-register, mark the preference.
1668 Note that we are not as aggressive as local-alloc in trying to tie a
1669 pseudo-register to a hard register. */
1672 set_preference (rtx dest
, rtx src
)
1674 unsigned int src_regno
, dest_regno
, end_regno
;
1675 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1676 to compensate for subregs in SRC or DEST. */
1681 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1682 src
= XEXP (src
, 0), copy
= 0;
1684 /* Get the reg number for both SRC and DEST.
1685 If neither is a reg, give up. */
1688 src_regno
= REGNO (src
);
1689 else if (GET_CODE (src
) == SUBREG
&& REG_P (SUBREG_REG (src
)))
1691 src_regno
= REGNO (SUBREG_REG (src
));
1693 if (REGNO (SUBREG_REG (src
)) < FIRST_PSEUDO_REGISTER
)
1694 offset
+= subreg_regno_offset (REGNO (SUBREG_REG (src
)),
1695 GET_MODE (SUBREG_REG (src
)),
1699 offset
+= (SUBREG_BYTE (src
)
1700 / REGMODE_NATURAL_SIZE (GET_MODE (src
)));
1706 dest_regno
= REGNO (dest
);
1707 else if (GET_CODE (dest
) == SUBREG
&& REG_P (SUBREG_REG (dest
)))
1709 dest_regno
= REGNO (SUBREG_REG (dest
));
1711 if (REGNO (SUBREG_REG (dest
)) < FIRST_PSEUDO_REGISTER
)
1712 offset
-= subreg_regno_offset (REGNO (SUBREG_REG (dest
)),
1713 GET_MODE (SUBREG_REG (dest
)),
1717 offset
-= (SUBREG_BYTE (dest
)
1718 / REGMODE_NATURAL_SIZE (GET_MODE (dest
)));
1723 /* Convert either or both to hard reg numbers. */
1725 if (reg_renumber
[src_regno
] >= 0)
1726 src_regno
= reg_renumber
[src_regno
];
1728 if (reg_renumber
[dest_regno
] >= 0)
1729 dest_regno
= reg_renumber
[dest_regno
];
1731 /* Now if one is a hard reg and the other is a global pseudo
1732 then give the other a preference. */
1734 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1735 && reg_allocno
[src_regno
] >= 0)
1737 dest_regno
-= offset
;
1738 if (dest_regno
< FIRST_PSEUDO_REGISTER
)
1741 SET_REGBIT (hard_reg_copy_preferences
,
1742 reg_allocno
[src_regno
], dest_regno
);
1744 SET_REGBIT (hard_reg_preferences
,
1745 reg_allocno
[src_regno
], dest_regno
);
1746 end_regno
= end_hard_regno (GET_MODE (dest
), dest_regno
);
1747 for (i
= dest_regno
; i
< end_regno
; i
++)
1748 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1752 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1753 && reg_allocno
[dest_regno
] >= 0)
1755 src_regno
+= offset
;
1756 if (src_regno
< FIRST_PSEUDO_REGISTER
)
1759 SET_REGBIT (hard_reg_copy_preferences
,
1760 reg_allocno
[dest_regno
], src_regno
);
1762 SET_REGBIT (hard_reg_preferences
,
1763 reg_allocno
[dest_regno
], src_regno
);
1764 end_regno
= end_hard_regno (GET_MODE (src
), src_regno
);
1765 for (i
= src_regno
; i
< end_regno
; i
++)
1766 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1771 /* Indicate that hard register number FROM was eliminated and replaced with
1772 an offset from hard register number TO. The status of hard registers live
1773 at the start of a basic block is updated by replacing a use of FROM with
1777 mark_elimination (int from
, int to
)
1783 regset r
= DF_RA_LIVE_IN (bb
);
1784 if (REGNO_REG_SET_P (r
, from
))
1786 CLEAR_REGNO_REG_SET (r
, from
);
1787 SET_REGNO_REG_SET (r
, to
);
1792 /* Used for communication between the following functions. Holds the
1793 current life information. */
1794 static regset live_relevant_regs
;
1796 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1797 This is called via note_stores. */
1799 reg_becomes_live (rtx reg
, rtx setter ATTRIBUTE_UNUSED
, void *regs_set
)
1803 if (GET_CODE (reg
) == SUBREG
)
1804 reg
= SUBREG_REG (reg
);
1809 regno
= REGNO (reg
);
1810 if (regno
< FIRST_PSEUDO_REGISTER
)
1812 int nregs
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1815 if (GET_CODE (setter
) == CLOBBER
)
1816 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1818 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1820 if (!fixed_regs
[regno
])
1821 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1825 else if (reg_renumber
[regno
] >= 0)
1827 if (GET_CODE (setter
) == CLOBBER
)
1828 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1830 SET_REGNO_REG_SET (live_relevant_regs
, regno
);
1831 SET_REGNO_REG_SET ((regset
) regs_set
, regno
);
1835 /* Record in live_relevant_regs that register REGNO died. */
1837 reg_dies (int regno
, enum machine_mode mode
, struct insn_chain
*chain
)
1839 if (regno
< FIRST_PSEUDO_REGISTER
)
1841 int nregs
= hard_regno_nregs
[regno
][mode
];
1844 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1845 if (! fixed_regs
[regno
])
1846 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1852 CLEAR_REGNO_REG_SET (live_relevant_regs
, regno
);
1853 if (reg_renumber
[regno
] >= 0)
1854 SET_REGNO_REG_SET (&chain
->dead_or_set
, regno
);
1858 /* Walk the insns of the current function and build reload_insn_chain,
1859 and record register life information. */
1861 build_insn_chain (rtx first
)
1863 struct insn_chain
**p
= &reload_insn_chain
;
1864 struct insn_chain
*prev
= 0;
1865 basic_block b
= ENTRY_BLOCK_PTR
->next_bb
;
1867 live_relevant_regs
= ALLOC_REG_SET (®_obstack
);
1869 for (; first
; first
= NEXT_INSN (first
))
1871 struct insn_chain
*c
;
1873 if (first
== BB_HEAD (b
))
1878 CLEAR_REG_SET (live_relevant_regs
);
1880 EXECUTE_IF_SET_IN_BITMAP (df_get_live_top (b
), 0, i
, bi
)
1882 if (i
< FIRST_PSEUDO_REGISTER
1883 ? ! TEST_HARD_REG_BIT (eliminable_regset
, i
)
1884 : reg_renumber
[i
] >= 0)
1885 SET_REGNO_REG_SET (live_relevant_regs
, i
);
1889 if (!NOTE_P (first
) && !BARRIER_P (first
))
1891 c
= new_insn_chain ();
1897 c
->block
= b
->index
;
1903 /* Mark the death of everything that dies in this instruction. */
1905 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1906 if (REG_NOTE_KIND (link
) == REG_DEAD
1907 && REG_P (XEXP (link
, 0)))
1908 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1911 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1913 /* Mark everything born in this instruction as live. */
1915 note_stores (PATTERN (first
), reg_becomes_live
,
1919 COPY_REG_SET (&c
->live_throughout
, live_relevant_regs
);
1925 /* Mark anything that is set in this insn and then unused as dying. */
1927 for (link
= REG_NOTES (first
); link
; link
= XEXP (link
, 1))
1928 if (REG_NOTE_KIND (link
) == REG_UNUSED
1929 && REG_P (XEXP (link
, 0)))
1930 reg_dies (REGNO (XEXP (link
, 0)), GET_MODE (XEXP (link
, 0)),
1935 if (first
== BB_END (b
))
1938 /* Stop after we pass the end of the last basic block. Verify that
1939 no real insns are after the end of the last basic block.
1941 We may want to reorganize the loop somewhat since this test should
1942 always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if
1943 the previous real insn is a JUMP_INSN. */
1944 if (b
== EXIT_BLOCK_PTR
)
1946 #ifdef ENABLE_CHECKING
1947 for (first
= NEXT_INSN (first
); first
; first
= NEXT_INSN (first
))
1948 gcc_assert (!INSN_P (first
)
1949 || GET_CODE (PATTERN (first
)) == USE
1950 || ((GET_CODE (PATTERN (first
)) == ADDR_VEC
1951 || GET_CODE (PATTERN (first
)) == ADDR_DIFF_VEC
)
1952 && prev_real_insn (first
) != 0
1953 && JUMP_P (prev_real_insn (first
))));
1958 FREE_REG_SET (live_relevant_regs
);
1962 /* Print debugging trace information if -dg switch is given,
1963 showing the information on which the allocation decisions are based. */
1966 dump_conflicts (FILE *file
)
1969 int has_preferences
;
1972 for (i
= 0; i
< max_allocno
; i
++)
1974 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1978 fprintf (file
, ";; %d regs to allocate:", nregs
);
1979 for (i
= 0; i
< max_allocno
; i
++)
1982 if (reg_renumber
[allocno
[allocno_order
[i
]].reg
] >= 0)
1984 fprintf (file
, " %d", allocno
[allocno_order
[i
]].reg
);
1985 for (j
= 0; j
< max_regno
; j
++)
1986 if (reg_allocno
[j
] == allocno_order
[i
]
1987 && j
!= allocno
[allocno_order
[i
]].reg
)
1988 fprintf (file
, "+%d", j
);
1989 if (allocno
[allocno_order
[i
]].size
!= 1)
1990 fprintf (file
, " (%d)", allocno
[allocno_order
[i
]].size
);
1992 fprintf (file
, "\n");
1994 for (i
= 0; i
< max_allocno
; i
++)
1997 fprintf (file
, ";; %d conflicts:", allocno
[i
].reg
);
1998 for (j
= 0; j
< max_allocno
; j
++)
1999 if (CONFLICTP (j
, i
))
2000 fprintf (file
, " %d", allocno
[j
].reg
);
2001 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
2002 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_conflicts
, j
))
2003 fprintf (file
, " %d", j
);
2004 fprintf (file
, "\n");
2006 has_preferences
= 0;
2007 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
2008 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
2009 has_preferences
= 1;
2011 if (! has_preferences
)
2013 fprintf (file
, ";; %d preferences:", allocno
[i
].reg
);
2014 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
2015 if (TEST_HARD_REG_BIT (allocno
[i
].hard_reg_preferences
, j
))
2016 fprintf (file
, " %d", j
);
2017 fprintf (file
, "\n");
2019 fprintf (file
, "\n");
2023 dump_global_regs (FILE *file
)
2027 fprintf (file
, ";; Register dispositions:\n");
2028 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
2029 if (reg_renumber
[i
] >= 0)
2031 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
2033 fprintf (file
, "\n");
2036 fprintf (file
, "\n\n;; Hard regs used: ");
2037 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2038 if (df_regs_ever_live_p (i
))
2039 fprintf (file
, " %d", i
);
2040 fprintf (file
, "\n\n");
2043 /* Run old register allocator. Return TRUE if we must exit
2044 rest_of_compilation upon return. */
2046 rest_of_handle_global_alloc (void)
2050 /* If optimizing, allocate remaining pseudo-regs. Do the reload
2051 pass fixing up any insns that are invalid. */
2053 failure
= global_alloc ();
2056 compute_regsets (&eliminable_regset
, &no_global_alloc_regs
);
2057 build_insn_chain (get_insns ());
2058 df_set_flags (DF_NO_INSN_RESCAN
);
2059 failure
= reload (get_insns (), 0);
2062 if (dump_enabled_p (pass_global_alloc
.static_pass_number
))
2064 timevar_push (TV_DUMP
);
2065 dump_global_regs (dump_file
);
2066 timevar_pop (TV_DUMP
);
2069 /* FIXME: This appears on the surface to be wrong thing to be doing.
2070 So much of the compiler is designed to check reload_completed to
2071 see if it is running after reload that seems doomed to failure.
2072 We should be returning a value that says that we have found
2073 errors so that nothing but the cleanup passes are run
2075 gcc_assert (reload_completed
|| failure
);
2076 reload_completed
= !failure
;
2078 /* The world has changed so much that at this point we might as well
2079 just rescan everything. Not that df_rescan_all_insns is not
2080 going to help here because it does not touch the artificial uses
2084 df_live_add_problem ();
2085 df_scan_alloc (NULL
);
2091 regstat_free_n_sets_and_refs ();
2096 struct tree_opt_pass pass_global_alloc
=
2100 rest_of_handle_global_alloc
, /* execute */
2103 0, /* static_pass_number */
2104 TV_GLOBAL_ALLOC
, /* tv_id */
2105 0, /* properties_required */
2106 0, /* properties_provided */
2107 0, /* properties_destroyed */
2108 0, /* todo_flags_start */
2110 TODO_ggc_collect
, /* todo_flags_finish */