Daily bump.
[official-gcc.git] / gcc / global.c
blob12641a60cba593f782417be9274fccdf64c4ee8c
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 3, or (at your option) any later
11 version.
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
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "machmode.h"
28 #include "hard-reg-set.h"
29 #include "rtl.h"
30 #include "tm_p.h"
31 #include "flags.h"
32 #include "regs.h"
33 #include "function.h"
34 #include "insn-config.h"
35 #include "recog.h"
36 #include "reload.h"
37 #include "output.h"
38 #include "toplev.h"
39 #include "tree-pass.h"
40 #include "timevar.h"
41 #include "df.h"
42 #include "vecprim.h"
43 #include "dbgcnt.h"
44 #include "ra.h"
46 /* This pass of the compiler performs global register allocation.
47 It assigns hard register numbers to all the pseudo registers
48 that were not handled in local_alloc. Assignments are recorded
49 in the vector reg_renumber, not by changing the rtl code.
50 (Such changes are made by final). The entry point is
51 the function global_alloc.
53 After allocation is complete, the reload pass is run as a subroutine
54 of this pass, so that when a pseudo reg loses its hard reg due to
55 spilling it is possible to make a second attempt to find a hard
56 reg for it. The reload pass is independent in other respects
57 and it is run even when stupid register allocation is in use.
59 1. Assign allocation-numbers (allocnos) to the pseudo-registers
60 still needing allocations and to the pseudo-registers currently
61 allocated by local-alloc which may be spilled by reload.
62 Set up tables reg_allocno and allocno_reg to map
63 reg numbers to allocnos and vice versa.
64 max_allocno gets the number of allocnos in use.
66 2. Allocate a max_allocno by max_allocno compressed triangular conflict
67 bit matrix (a triangular bit matrix with portions removed for which we
68 can guarantee there are no conflicts, example: two local pseudos that
69 live in different basic blocks) and clear it. This is called "conflict".
70 Note that for triangular bit matrices, there are two possible equations
71 for computing the bit number for two allocnos: LOW and HIGH (LOW < HIGH):
73 1) BITNUM = f(HIGH) + LOW, where
74 f(HIGH) = (HIGH * (HIGH - 1)) / 2
76 2) BITNUM = f(LOW) + HIGH, where
77 f(LOW) = LOW * (max_allocno - LOW) + (LOW * (LOW - 1)) / 2 - LOW - 1
79 We use the second (and less common) equation as this gives us better
80 cache locality for local allocnos that are live within the same basic
81 block. Also note that f(HIGH) and f(LOW) can be precalculated for all
82 values of HIGH and LOW, so all that is necessary to compute the bit
83 number for two allocnos LOW and HIGH is a load followed by an addition.
85 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix for
86 conflicts between allocnos and explicit hard register use (which
87 includes use of pseudo-registers allocated by local_alloc). This
88 is the hard_reg_conflicts inside each allocno.
90 3. For each basic block, walk backward through the block, recording
91 which pseudo-registers and which hardware registers are live.
92 Build the conflict matrix between the pseudo-registers and another of
93 pseudo-registers versus hardware registers.
95 4. For each basic block, walk backward through the block, recording
96 the preferred hardware registers for each pseudo-register.
98 5. Sort a table of the allocnos into order of desirability of the variables.
100 6. Allocate the variables in that order; each if possible into
101 a preferred register, else into another register. */
103 /* A vector of the integers from 0 to max_allocno-1,
104 sorted in the order of first-to-be-allocated first. */
106 static int *allocno_order;
108 /* Set of registers that global-alloc isn't supposed to use. */
110 static HARD_REG_SET no_global_alloc_regs;
112 /* Set of registers used so far. */
114 static HARD_REG_SET regs_used_so_far;
116 /* Number of refs to each hard reg, as used by local alloc.
117 It is zero for a reg that contains global pseudos or is explicitly used. */
119 static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
121 /* Frequency of uses of given hard reg. */
122 static int local_reg_freq[FIRST_PSEUDO_REGISTER];
124 /* Guess at live length of each hard reg, as used by local alloc.
125 This is actually the sum of the live lengths of the specific regs. */
127 static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
129 /* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
130 element I, and hard register number J. */
132 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
134 /* This is turned off because it doesn't work right for DImode.
135 (And it is only used for DImode, so the other cases are worthless.)
136 The problem is that it isn't true that there is NO possibility of conflict;
137 only that there is no conflict if the two pseudos get the exact same regs.
138 If they were allocated with a partial overlap, there would be a conflict.
139 We can't safely turn off the conflict unless we have another way to
140 prevent the partial overlap.
142 Idea: change hard_reg_conflicts so that instead of recording which
143 hard regs the allocno may not overlap, it records where the allocno
144 may not start. Change both where it is used and where it is updated.
145 Then there is a way to record that (reg:DI 108) may start at 10
146 but not at 9 or 11. There is still the question of how to record
147 this semi-conflict between two pseudos. */
148 #if 0
149 /* Reg pairs for which conflict after the current insn
150 is inhibited by a REG_NO_CONFLICT note.
151 If the table gets full, we ignore any other notes--that is conservative. */
152 #define NUM_NO_CONFLICT_PAIRS 4
153 /* Number of pairs in use in this insn. */
154 int n_no_conflict_pairs;
155 static struct { int allocno1, allocno2;}
156 no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
157 #endif /* 0 */
159 /* Return true if *LOC contains an asm. */
161 static int
162 insn_contains_asm_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
164 if ( !*loc)
165 return 0;
166 if (GET_CODE (*loc) == ASM_OPERANDS)
167 return 1;
168 return 0;
172 /* Return true if INSN contains an ASM. */
174 static int
175 insn_contains_asm (rtx insn)
177 return for_each_rtx (&insn, insn_contains_asm_1, NULL);
181 static void
182 compute_regs_asm_clobbered (char *regs_asm_clobbered)
184 basic_block bb;
186 memset (regs_asm_clobbered, 0, sizeof (char) * FIRST_PSEUDO_REGISTER);
188 FOR_EACH_BB (bb)
190 rtx insn;
191 FOR_BB_INSNS_REVERSE (bb, insn)
193 struct df_ref **def_rec;
194 if (insn_contains_asm (insn))
195 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
197 struct df_ref *def = *def_rec;
198 unsigned int dregno = DF_REF_REGNO (def);
199 if (dregno < FIRST_PSEUDO_REGISTER)
201 unsigned int i;
202 enum machine_mode mode = GET_MODE (DF_REF_REAL_REG (def));
203 unsigned int end = dregno
204 + hard_regno_nregs[dregno][mode] - 1;
205 for (i = dregno; i <= end; ++i)
206 regs_asm_clobbered[i] = 1;
214 /* All registers that can be eliminated. */
216 static HARD_REG_SET eliminable_regset;
218 static int regno_compare (const void *, const void *);
219 static int allocno_compare (const void *, const void *);
220 static void expand_preferences (void);
221 static void prune_preferences (void);
222 static void set_preferences (void);
223 static void find_reg (int, HARD_REG_SET, int, int, int);
224 static void dump_conflicts (FILE *);
225 static void build_insn_chain (void);
228 /* Look through the list of eliminable registers. Set ELIM_SET to the
229 set of registers which may be eliminated. Set NO_GLOBAL_SET to the
230 set of registers which may not be used across blocks.
232 This will normally be called with ELIM_SET as the file static
233 variable eliminable_regset, and NO_GLOBAL_SET as the file static
234 variable NO_GLOBAL_ALLOC_REGS. */
236 static void
237 compute_regsets (HARD_REG_SET *elim_set,
238 HARD_REG_SET *no_global_set)
241 /* Like regs_ever_live, but 1 if a reg is set or clobbered from an asm.
242 Unlike regs_ever_live, elements of this array corresponding to
243 eliminable regs like the frame pointer are set if an asm sets them. */
244 char *regs_asm_clobbered = alloca (FIRST_PSEUDO_REGISTER * sizeof (char));
246 #ifdef ELIMINABLE_REGS
247 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
248 size_t i;
249 #endif
250 int need_fp
251 = (! flag_omit_frame_pointer
252 || (current_function_calls_alloca && EXIT_IGNORE_STACK)
253 || FRAME_POINTER_REQUIRED);
255 max_regno = max_reg_num ();
256 compact_blocks ();
258 max_allocno = 0;
260 /* A machine may have certain hard registers that
261 are safe to use only within a basic block. */
263 CLEAR_HARD_REG_SET (*no_global_set);
264 CLEAR_HARD_REG_SET (*elim_set);
266 compute_regs_asm_clobbered (regs_asm_clobbered);
267 /* Build the regset of all eliminable registers and show we can't use those
268 that we already know won't be eliminated. */
269 #ifdef ELIMINABLE_REGS
270 for (i = 0; i < ARRAY_SIZE (eliminables); i++)
272 bool cannot_elim
273 = (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
274 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp));
276 if (!regs_asm_clobbered[eliminables[i].from])
278 SET_HARD_REG_BIT (*elim_set, eliminables[i].from);
280 if (cannot_elim)
281 SET_HARD_REG_BIT (*no_global_set, eliminables[i].from);
283 else if (cannot_elim)
284 error ("%s cannot be used in asm here",
285 reg_names[eliminables[i].from]);
286 else
287 df_set_regs_ever_live (eliminables[i].from, true);
289 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
290 if (!regs_asm_clobbered[HARD_FRAME_POINTER_REGNUM])
292 SET_HARD_REG_BIT (*elim_set, HARD_FRAME_POINTER_REGNUM);
293 if (need_fp)
294 SET_HARD_REG_BIT (*no_global_set, HARD_FRAME_POINTER_REGNUM);
296 else if (need_fp)
297 error ("%s cannot be used in asm here",
298 reg_names[HARD_FRAME_POINTER_REGNUM]);
299 else
300 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
301 #endif
303 #else
304 if (!regs_asm_clobbered[FRAME_POINTER_REGNUM])
306 SET_HARD_REG_BIT (*elim_set, FRAME_POINTER_REGNUM);
307 if (need_fp)
308 SET_HARD_REG_BIT (*no_global_set, FRAME_POINTER_REGNUM);
310 else if (need_fp)
311 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
312 else
313 df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
314 #endif
317 /* Perform allocation of pseudo-registers not allocated by local_alloc.
319 Return value is nonzero if reload failed
320 and we must not do any more for this function. */
322 static int
323 global_alloc (void)
325 int retval;
326 size_t i;
327 int max_blk;
328 int *num_allocnos_per_blk;
330 compute_regsets (&eliminable_regset, &no_global_alloc_regs);
332 /* Track which registers have already been used. Start with registers
333 explicitly in the rtl, then registers allocated by local register
334 allocation. */
336 CLEAR_HARD_REG_SET (regs_used_so_far);
337 #ifdef LEAF_REGISTERS
338 /* If we are doing the leaf function optimization, and this is a leaf
339 function, it means that the registers that take work to save are those
340 that need a register window. So prefer the ones that can be used in
341 a leaf function. */
343 const char *cheap_regs;
344 const char *const leaf_regs = LEAF_REGISTERS;
346 if (only_leaf_regs_used () && leaf_function_p ())
347 cheap_regs = leaf_regs;
348 else
349 cheap_regs = call_used_regs;
350 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
351 if (df_regs_ever_live_p (i) || cheap_regs[i])
352 SET_HARD_REG_BIT (regs_used_so_far, i);
354 #else
355 /* We consider registers that do not have to be saved over calls as if
356 they were already used since there is no cost in using them. */
357 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
358 if (df_regs_ever_live_p (i) || call_used_regs[i])
359 SET_HARD_REG_BIT (regs_used_so_far, i);
360 #endif
362 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
363 if (reg_renumber[i] >= 0)
364 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
366 /* Establish mappings from register number to allocation number
367 and vice versa. In the process, count the allocnos. */
369 reg_allocno = XNEWVEC (int, max_regno);
371 /* Initially fill the reg_allocno array with regno's... */
372 max_blk = 0;
373 max_allocno = 0;
374 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
375 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
376 that we are supposed to refrain from putting in a hard reg.
377 -2 means do make an allocno but don't allocate it. */
378 if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
379 /* Don't allocate pseudos that cross calls,
380 if this function receives a nonlocal goto. */
381 && (! current_function_has_nonlocal_label
382 || REG_N_CALLS_CROSSED (i) == 0))
384 int blk = regno_basic_block (i);
385 reg_allocno[max_allocno++] = i;
386 if (blk > max_blk)
387 max_blk = blk;
388 gcc_assert (REG_LIVE_LENGTH (i));
391 allocno = XCNEWVEC (struct allocno, max_allocno);
392 partial_bitnum = XNEWVEC (HOST_WIDE_INT, max_allocno);
393 num_allocnos_per_blk = XCNEWVEC (int, max_blk + 1);
395 /* ...so we can sort them in the order we want them to receive
396 their allocnos. */
397 qsort (reg_allocno, max_allocno, sizeof (int), regno_compare);
399 for (i = 0; i < (size_t) max_allocno; i++)
401 int regno = reg_allocno[i];
402 int blk = regno_basic_block (regno);
403 num_allocnos_per_blk[blk]++;
404 allocno[i].reg = regno;
405 allocno[i].size = PSEUDO_REGNO_SIZE (regno);
406 allocno[i].calls_crossed += REG_N_CALLS_CROSSED (regno);
407 allocno[i].freq_calls_crossed += REG_FREQ_CALLS_CROSSED (regno);
408 allocno[i].throwing_calls_crossed
409 += REG_N_THROWING_CALLS_CROSSED (regno);
410 allocno[i].n_refs += REG_N_REFS (regno);
411 allocno[i].freq += REG_FREQ (regno);
412 if (allocno[i].live_length < REG_LIVE_LENGTH (regno))
413 allocno[i].live_length = REG_LIVE_LENGTH (regno);
416 /* The "global" block must contain all allocnos. */
417 num_allocnos_per_blk[0] = max_allocno;
419 /* Now reinitialize the reg_allocno array in terms of the
420 optimized regno to allocno mapping we created above. */
421 for (i = 0; i < (size_t) max_regno; i++)
422 reg_allocno[i] = -1;
424 max_bitnum = 0;
425 for (i = 0; i < (size_t) max_allocno; i++)
427 int regno = allocno[i].reg;
428 int blk = regno_basic_block (regno);
429 int row_size = --num_allocnos_per_blk[blk];
430 reg_allocno[regno] = (int) i;
431 partial_bitnum[i] = (row_size > 0) ? max_bitnum - ((int) i + 1) : -1;
432 max_bitnum += row_size;
435 #ifdef ENABLE_CHECKING
436 gcc_assert (max_bitnum <=
437 (((HOST_WIDE_INT) max_allocno *
438 ((HOST_WIDE_INT) max_allocno - 1)) / 2));
439 #endif
441 if (dump_file)
443 HOST_WIDE_INT num_bits, num_bytes, actual_bytes;
445 fprintf (dump_file, "## max_blk: %d\n", max_blk);
446 fprintf (dump_file, "## max_regno: %d\n", max_regno);
447 fprintf (dump_file, "## max_allocno: %d\n", max_allocno);
449 num_bits = max_bitnum;
450 num_bytes = CEIL (num_bits, 8);
451 actual_bytes = num_bytes;
452 fprintf (dump_file, "## Compressed triangular bitmatrix size: ");
453 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bits, ", num_bits);
454 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bytes\n", num_bytes);
456 num_bits = ((HOST_WIDE_INT) max_allocno *
457 ((HOST_WIDE_INT) max_allocno - 1)) / 2;
458 num_bytes = CEIL (num_bits, 8);
459 fprintf (dump_file, "## Standard triangular bitmatrix size: ");
460 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bits, ", num_bits);
461 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bytes [%.2f%%]\n",
462 num_bytes, 100.0 * ((double) actual_bytes / (double) num_bytes));
464 num_bits = (HOST_WIDE_INT) max_allocno * (HOST_WIDE_INT) max_allocno;
465 num_bytes = CEIL (num_bits, 8);
466 fprintf (dump_file, "## Square bitmatrix size: ");
467 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bits, ", num_bits);
468 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bytes [%.2f%%]\n",
469 num_bytes, 100.0 * ((double) actual_bytes / (double) num_bytes));
472 /* Calculate amount of usage of each hard reg by pseudos
473 allocated by local-alloc. This is to see if we want to
474 override it. */
475 memset (local_reg_live_length, 0, sizeof local_reg_live_length);
476 memset (local_reg_n_refs, 0, sizeof local_reg_n_refs);
477 memset (local_reg_freq, 0, sizeof local_reg_freq);
478 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
479 if (reg_renumber[i] >= 0)
481 int regno = reg_renumber[i];
482 int endregno = end_hard_regno (PSEUDO_REGNO_MODE (i), regno);
483 int j;
485 for (j = regno; j < endregno; j++)
487 local_reg_n_refs[j] += REG_N_REFS (i);
488 local_reg_freq[j] += REG_FREQ (i);
489 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
493 /* We can't override local-alloc for a reg used not just by local-alloc. */
494 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
495 if (df_regs_ever_live_p (i))
496 local_reg_n_refs[i] = 0, local_reg_freq[i] = 0;
498 if (dump_file)
500 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
502 fprintf (dump_file, "%d REG_N_REFS=%d, REG_FREQ=%d, REG_LIVE_LENGTH=%d\n",
503 (int)i, REG_N_REFS (i), REG_FREQ (i), REG_LIVE_LENGTH (i));
505 fprintf (dump_file, "regs_ever_live =");
506 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
507 if (df_regs_ever_live_p (i))
508 fprintf (dump_file, " %d", (int)i);
509 fprintf (dump_file, "\n");
512 conflicts = NULL;
513 adjacency = NULL;
514 adjacency_pool = NULL;
516 /* If there is work to be done (at least one reg to allocate),
517 perform global conflict analysis and allocate the regs. */
519 if (max_allocno > 0)
521 /* We used to use alloca here, but the size of what it would try to
522 allocate would occasionally cause it to exceed the stack limit and
523 cause unpredictable core dumps. Some examples were > 2Mb in size. */
524 conflicts = XCNEWVEC (HOST_WIDEST_FAST_INT,
525 CEIL(max_bitnum, HOST_BITS_PER_WIDEST_FAST_INT));
527 adjacency = XCNEWVEC (adjacency_t *, max_allocno);
528 adjacency_pool = create_alloc_pool ("global_alloc adjacency list pool",
529 sizeof (adjacency_t), 1024);
531 /* Scan all the insns and compute the conflicts among allocnos
532 and between allocnos and hard regs. */
534 global_conflicts ();
536 /* There is just too much going on in the register allocators to
537 keep things up to date. At the end we have to rescan anyway
538 because things change when the reload_completed flag is set.
539 So we just turn off scanning and we will rescan by hand.
541 However, we needed to do the rescanning before this point to
542 get the new insns scanned inserted by local_alloc scanned for
543 global_conflicts. */
544 df_set_flags (DF_NO_INSN_RESCAN);
546 /* Eliminate conflicts between pseudos and eliminable registers. If
547 the register is not eliminated, the pseudo won't really be able to
548 live in the eliminable register, so the conflict doesn't matter.
549 If we do eliminate the register, the conflict will no longer exist.
550 So in either case, we can ignore the conflict. Likewise for
551 preferences. */
553 set_preferences ();
555 for (i = 0; i < (size_t) max_allocno; i++)
557 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_conflicts,
558 eliminable_regset);
559 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_copy_preferences,
560 eliminable_regset);
561 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_preferences,
562 eliminable_regset);
565 /* Try to expand the preferences by merging them between allocnos. */
567 expand_preferences ();
569 /* Determine the order to allocate the remaining pseudo registers. */
571 allocno_order = XNEWVEC (int, max_allocno);
572 for (i = 0; i < (size_t) max_allocno; i++)
573 allocno_order[i] = i;
575 /* Default the size to 1, since allocno_compare uses it to divide by.
576 Also convert allocno_live_length of zero to -1. A length of zero
577 can occur when all the registers for that allocno have reg_live_length
578 equal to -2. In this case, we want to make an allocno, but not
579 allocate it. So avoid the divide-by-zero and set it to a low
580 priority. */
582 for (i = 0; i < (size_t) max_allocno; i++)
584 if (allocno[i].size == 0)
585 allocno[i].size = 1;
586 if (allocno[i].live_length == 0)
587 allocno[i].live_length = -1;
590 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
592 prune_preferences ();
594 if (dump_file)
595 dump_conflicts (dump_file);
597 /* Try allocating them, one by one, in that order,
598 except for parameters marked with reg_live_length[regno] == -2. */
600 for (i = 0; i < (size_t) max_allocno; i++)
601 if (reg_renumber[allocno[allocno_order[i]].reg] < 0
602 && REG_LIVE_LENGTH (allocno[allocno_order[i]].reg) >= 0)
604 if (!dbg_cnt (global_alloc_at_reg))
605 break;
606 /* If we have more than one register class,
607 first try allocating in the class that is cheapest
608 for this pseudo-reg. If that fails, try any reg. */
609 if (N_REG_CLASSES > 1)
611 find_reg (allocno_order[i], 0, 0, 0, 0);
612 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
613 continue;
615 if (reg_alternate_class (allocno[allocno_order[i]].reg) != NO_REGS)
616 find_reg (allocno_order[i], 0, 1, 0, 0);
619 free (allocno_order);
620 free (conflicts);
623 /* Do the reloads now while the allocno data still exists, so that we can
624 try to assign new hard regs to any pseudo regs that are spilled. */
626 #if 0 /* We need to eliminate regs even if there is no rtl code,
627 for the sake of debugging information. */
628 if (n_basic_blocks > NUM_FIXED_BLOCKS)
629 #endif
631 build_insn_chain ();
632 retval = reload (get_insns (), 1);
635 /* Clean up. */
636 free (reg_allocno);
637 free (num_allocnos_per_blk);
638 free (partial_bitnum);
639 free (allocno);
640 if (adjacency != NULL)
642 free_alloc_pool (adjacency_pool);
643 free (adjacency);
646 return retval;
649 /* Sort predicate for ordering the regnos. We want the regno to allocno
650 mapping to have the property that all "global" regnos (ie, regnos that
651 are referenced in more than one basic block) have smaller allocno values
652 than "local" regnos (ie, regnos referenced in only one basic block).
653 In addition, for two basic blocks "i" and "j" with i < j, all regnos
654 local to basic block i should have smaller allocno values than regnos
655 local to basic block j.
656 Returns -1 (1) if *v1p should be allocated before (after) *v2p. */
658 static int
659 regno_compare (const void *v1p, const void *v2p)
661 int regno1 = *(const int *)v1p;
662 int regno2 = *(const int *)v2p;
663 int blk1 = REG_BASIC_BLOCK (regno1);
664 int blk2 = REG_BASIC_BLOCK (regno2);
666 /* Prefer lower numbered basic blocks. Note that global and unknown
667 blocks have negative values, giving them high precedence. */
668 if (blk1 - blk2)
669 return blk1 - blk2;
671 /* If both regs are referenced from the same block, sort by regno. */
672 return regno1 - regno2;
675 /* Sort predicate for ordering the allocnos.
676 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
678 static int
679 allocno_compare (const void *v1p, const void *v2p)
681 int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
682 /* Note that the quotient will never be bigger than
683 the value of floor_log2 times the maximum number of
684 times a register can occur in one insn (surely less than 100)
685 weighted by the frequency (maximally REG_FREQ_MAX).
686 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
687 int pri1
688 = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].freq)
689 / allocno[v1].live_length)
690 * (10000 / REG_FREQ_MAX) * allocno[v1].size);
691 int pri2
692 = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].freq)
693 / allocno[v2].live_length)
694 * (10000 / REG_FREQ_MAX) * allocno[v2].size);
695 if (pri2 - pri1)
696 return pri2 - pri1;
698 /* If regs are equally good, sort by allocno,
699 so that the results of qsort leave nothing to chance. */
700 return v1 - v2;
703 /* Expand the preference information by looking for cases where one allocno
704 dies in an insn that sets an allocno. If those two allocnos don't conflict,
705 merge any preferences between those allocnos. */
707 static void
708 expand_preferences (void)
710 rtx insn;
711 rtx link;
712 rtx set;
714 /* We only try to handle the most common cases here. Most of the cases
715 where this wins are reg-reg copies. */
717 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
718 if (INSN_P (insn)
719 && (set = single_set (insn)) != 0
720 && REG_P (SET_DEST (set))
721 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
722 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
723 if (REG_NOTE_KIND (link) == REG_DEAD
724 && REG_P (XEXP (link, 0))
725 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
726 && ! conflict_p (reg_allocno[REGNO (SET_DEST (set))],
727 reg_allocno[REGNO (XEXP (link, 0))]))
729 int a1 = reg_allocno[REGNO (SET_DEST (set))];
730 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
732 if (XEXP (link, 0) == SET_SRC (set))
734 IOR_HARD_REG_SET (allocno[a1].hard_reg_copy_preferences,
735 allocno[a2].hard_reg_copy_preferences);
736 IOR_HARD_REG_SET (allocno[a2].hard_reg_copy_preferences,
737 allocno[a1].hard_reg_copy_preferences);
740 IOR_HARD_REG_SET (allocno[a1].hard_reg_preferences,
741 allocno[a2].hard_reg_preferences);
742 IOR_HARD_REG_SET (allocno[a2].hard_reg_preferences,
743 allocno[a1].hard_reg_preferences);
744 IOR_HARD_REG_SET (allocno[a1].hard_reg_full_preferences,
745 allocno[a2].hard_reg_full_preferences);
746 IOR_HARD_REG_SET (allocno[a2].hard_reg_full_preferences,
747 allocno[a1].hard_reg_full_preferences);
752 /* Try to set a preference for an allocno to a hard register.
753 We are passed DEST and SRC which are the operands of a SET. It is known
754 that SRC is a register. If SRC or the first operand of SRC is a register,
755 try to set a preference. If one of the two is a hard register and the other
756 is a pseudo-register, mark the preference.
758 Note that we are not as aggressive as local-alloc in trying to tie a
759 pseudo-register to a hard register. */
761 static void
762 set_preference (rtx dest, rtx src)
764 unsigned int src_regno, dest_regno, end_regno;
765 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
766 to compensate for subregs in SRC or DEST. */
767 int offset = 0;
768 unsigned int i;
769 int copy = 1;
771 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
772 src = XEXP (src, 0), copy = 0;
774 /* Get the reg number for both SRC and DEST.
775 If neither is a reg, give up. */
777 if (REG_P (src))
778 src_regno = REGNO (src);
779 else if (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src)))
781 src_regno = REGNO (SUBREG_REG (src));
783 if (REGNO (SUBREG_REG (src)) < FIRST_PSEUDO_REGISTER)
784 offset += subreg_regno_offset (REGNO (SUBREG_REG (src)),
785 GET_MODE (SUBREG_REG (src)),
786 SUBREG_BYTE (src),
787 GET_MODE (src));
788 else
789 offset += (SUBREG_BYTE (src)
790 / REGMODE_NATURAL_SIZE (GET_MODE (src)));
792 else
793 return;
795 if (REG_P (dest))
796 dest_regno = REGNO (dest);
797 else if (GET_CODE (dest) == SUBREG && REG_P (SUBREG_REG (dest)))
799 dest_regno = REGNO (SUBREG_REG (dest));
801 if (REGNO (SUBREG_REG (dest)) < FIRST_PSEUDO_REGISTER)
802 offset -= subreg_regno_offset (REGNO (SUBREG_REG (dest)),
803 GET_MODE (SUBREG_REG (dest)),
804 SUBREG_BYTE (dest),
805 GET_MODE (dest));
806 else
807 offset -= (SUBREG_BYTE (dest)
808 / REGMODE_NATURAL_SIZE (GET_MODE (dest)));
810 else
811 return;
813 /* Convert either or both to hard reg numbers. */
815 if (reg_renumber[src_regno] >= 0)
816 src_regno = reg_renumber[src_regno];
818 if (reg_renumber[dest_regno] >= 0)
819 dest_regno = reg_renumber[dest_regno];
821 /* Now if one is a hard reg and the other is a global pseudo
822 then give the other a preference. */
824 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
825 && reg_allocno[src_regno] >= 0)
827 dest_regno -= offset;
828 if (dest_regno < FIRST_PSEUDO_REGISTER)
830 if (copy)
831 SET_REGBIT (hard_reg_copy_preferences,
832 reg_allocno[src_regno], dest_regno);
834 SET_REGBIT (hard_reg_preferences,
835 reg_allocno[src_regno], dest_regno);
836 end_regno = end_hard_regno (GET_MODE (dest), dest_regno);
837 for (i = dest_regno; i < end_regno; i++)
838 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
842 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
843 && reg_allocno[dest_regno] >= 0)
845 src_regno += offset;
846 if (src_regno < FIRST_PSEUDO_REGISTER)
848 if (copy)
849 SET_REGBIT (hard_reg_copy_preferences,
850 reg_allocno[dest_regno], src_regno);
852 SET_REGBIT (hard_reg_preferences,
853 reg_allocno[dest_regno], src_regno);
854 end_regno = end_hard_regno (GET_MODE (src), src_regno);
855 for (i = src_regno; i < end_regno; i++)
856 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
861 /* Helper function for set_preferences. */
862 static void
863 set_preferences_1 (rtx reg, const_rtx setter, void *data ATTRIBUTE_UNUSED)
865 if (GET_CODE (reg) == SUBREG)
866 reg = SUBREG_REG (reg);
868 if (!REG_P (reg))
869 return;
871 gcc_assert (setter);
872 if (GET_CODE (setter) != CLOBBER)
873 set_preference (reg, SET_SRC (setter));
876 /* Scan all of the insns and initialize the preferences. */
878 static void
879 set_preferences (void)
881 basic_block bb;
882 rtx insn;
883 FOR_EACH_BB (bb)
884 FOR_BB_INSNS_REVERSE (bb, insn)
886 if (!INSN_P (insn))
887 continue;
889 note_stores (PATTERN (insn), set_preferences_1, NULL);
895 /* Prune the preferences for global registers to exclude registers that cannot
896 be used.
898 Compute `regs_someone_prefers', which is a bitmask of the hard registers
899 that are preferred by conflicting registers of lower priority. If possible,
900 we will avoid using these registers. */
902 static void
903 prune_preferences (void)
905 int i;
906 int num;
907 int *allocno_to_order = XNEWVEC (int, max_allocno);
909 /* Scan least most important to most important.
910 For each allocno, remove from preferences registers that cannot be used,
911 either because of conflicts or register type. Then compute all registers
912 preferred by each lower-priority register that conflicts. */
914 for (i = max_allocno - 1; i >= 0; i--)
916 HARD_REG_SET temp;
918 num = allocno_order[i];
919 allocno_to_order[num] = i;
920 COPY_HARD_REG_SET (temp, allocno[num].hard_reg_conflicts);
922 if (allocno[num].calls_crossed == 0)
923 IOR_HARD_REG_SET (temp, fixed_reg_set);
924 else
925 IOR_HARD_REG_SET (temp, call_used_reg_set);
927 IOR_COMPL_HARD_REG_SET
928 (temp,
929 reg_class_contents[(int) reg_preferred_class (allocno[num].reg)]);
931 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, temp);
932 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, temp);
933 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_full_preferences, temp);
936 for (i = max_allocno - 1; i >= 0; i--)
938 /* Merge in the preferences of lower-priority registers (they have
939 already been pruned). If we also prefer some of those registers,
940 don't exclude them unless we are of a smaller size (in which case
941 we want to give the lower-priority allocno the first chance for
942 these registers). */
943 HARD_REG_SET temp, temp2;
944 int allocno2;
945 adjacency_iter ai;
947 num = allocno_order[i];
949 CLEAR_HARD_REG_SET (temp);
950 CLEAR_HARD_REG_SET (temp2);
952 FOR_EACH_CONFLICT (num, allocno2, ai)
954 if (allocno_to_order[allocno2] > i)
956 if (allocno[allocno2].size <= allocno[num].size)
957 IOR_HARD_REG_SET (temp,
958 allocno[allocno2].hard_reg_full_preferences);
959 else
960 IOR_HARD_REG_SET (temp2,
961 allocno[allocno2].hard_reg_full_preferences);
965 AND_COMPL_HARD_REG_SET (temp, allocno[num].hard_reg_full_preferences);
966 IOR_HARD_REG_SET (temp, temp2);
967 COPY_HARD_REG_SET (allocno[num].regs_someone_prefers, temp);
969 free (allocno_to_order);
972 /* Assign a hard register to allocno NUM; look for one that is the beginning
973 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
974 The registers marked in PREFREGS are tried first.
976 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
977 be used for this allocation.
979 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
980 Otherwise ignore that preferred class and use the alternate class.
982 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
983 will have to be saved and restored at calls.
985 RETRYING is nonzero if this is called from retry_global_alloc.
987 If we find one, record it in reg_renumber.
988 If not, do nothing. */
990 static void
991 find_reg (int num, HARD_REG_SET losers, int alt_regs_p, int accept_call_clobbered, int retrying)
993 int i, best_reg, pass;
994 HARD_REG_SET used, used1, used2;
996 enum reg_class class = (alt_regs_p
997 ? reg_alternate_class (allocno[num].reg)
998 : reg_preferred_class (allocno[num].reg));
999 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno[num].reg);
1001 if (accept_call_clobbered)
1002 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
1003 else if (allocno[num].calls_crossed == 0)
1004 COPY_HARD_REG_SET (used1, fixed_reg_set);
1005 else
1006 COPY_HARD_REG_SET (used1, call_used_reg_set);
1008 /* Some registers should not be allocated in global-alloc. */
1009 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
1010 if (losers)
1011 IOR_HARD_REG_SET (used1, losers);
1013 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
1015 #ifdef EH_RETURN_DATA_REGNO
1016 if (allocno[num].no_eh_reg)
1018 unsigned int j;
1019 for (j = 0; ; ++j)
1021 unsigned int regno = EH_RETURN_DATA_REGNO (j);
1022 if (regno == INVALID_REGNUM)
1023 break;
1024 SET_HARD_REG_BIT (used1, regno);
1027 #endif
1029 COPY_HARD_REG_SET (used2, used1);
1031 IOR_HARD_REG_SET (used1, allocno[num].hard_reg_conflicts);
1033 #ifdef CANNOT_CHANGE_MODE_CLASS
1034 cannot_change_mode_set_regs (&used1, mode, allocno[num].reg);
1035 #endif
1037 /* Try each hard reg to see if it fits. Do this in two passes.
1038 In the first pass, skip registers that are preferred by some other pseudo
1039 to give it a better chance of getting one of those registers. Only if
1040 we can't get a register when excluding those do we take one of them.
1041 However, we never allocate a register for the first time in pass 0. */
1043 COPY_HARD_REG_SET (used, used1);
1044 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
1045 IOR_HARD_REG_SET (used, allocno[num].regs_someone_prefers);
1047 best_reg = -1;
1048 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
1049 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
1050 pass++)
1052 if (pass == 1)
1053 COPY_HARD_REG_SET (used, used1);
1054 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1056 #ifdef REG_ALLOC_ORDER
1057 int regno = reg_alloc_order[i];
1058 #else
1059 int regno = i;
1060 #endif
1061 if (! TEST_HARD_REG_BIT (used, regno)
1062 && HARD_REGNO_MODE_OK (regno, mode)
1063 && (allocno[num].calls_crossed == 0
1064 || accept_call_clobbered
1065 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
1067 int j;
1068 int lim = end_hard_regno (mode, regno);
1069 for (j = regno + 1;
1070 (j < lim
1071 && ! TEST_HARD_REG_BIT (used, j));
1072 j++);
1073 if (j == lim)
1075 best_reg = regno;
1076 break;
1078 #ifndef REG_ALLOC_ORDER
1079 i = j; /* Skip starting points we know will lose */
1080 #endif
1085 /* See if there is a preferred register with the same class as the register
1086 we allocated above. Making this restriction prevents register
1087 preferencing from creating worse register allocation.
1089 Remove from the preferred registers and conflicting registers. Note that
1090 additional conflicts may have been added after `prune_preferences' was
1091 called.
1093 First do this for those register with copy preferences, then all
1094 preferred registers. */
1096 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, used);
1097 if (!hard_reg_set_empty_p (allocno[num].hard_reg_copy_preferences)
1098 && best_reg >= 0)
1100 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1101 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_copy_preferences, i)
1102 && HARD_REGNO_MODE_OK (i, mode)
1103 && (allocno[num].calls_crossed == 0
1104 || accept_call_clobbered
1105 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1106 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1107 || reg_class_subset_p (REGNO_REG_CLASS (i),
1108 REGNO_REG_CLASS (best_reg))
1109 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1110 REGNO_REG_CLASS (i))))
1112 int j;
1113 int lim = end_hard_regno (mode, i);
1114 for (j = i + 1;
1115 (j < lim
1116 && ! TEST_HARD_REG_BIT (used, j)
1117 && (REGNO_REG_CLASS (j)
1118 == REGNO_REG_CLASS (best_reg + (j - i))
1119 || reg_class_subset_p (REGNO_REG_CLASS (j),
1120 REGNO_REG_CLASS (best_reg + (j - i)))
1121 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1122 REGNO_REG_CLASS (j))));
1123 j++);
1124 if (j == lim)
1126 best_reg = i;
1127 goto no_prefs;
1132 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, used);
1133 if (!hard_reg_set_empty_p (allocno[num].hard_reg_preferences)
1134 && best_reg >= 0)
1136 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1137 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_preferences, i)
1138 && HARD_REGNO_MODE_OK (i, mode)
1139 && (allocno[num].calls_crossed == 0
1140 || accept_call_clobbered
1141 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1142 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1143 || reg_class_subset_p (REGNO_REG_CLASS (i),
1144 REGNO_REG_CLASS (best_reg))
1145 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1146 REGNO_REG_CLASS (i))))
1148 int j;
1149 int lim = end_hard_regno (mode, i);
1150 for (j = i + 1;
1151 (j < lim
1152 && ! TEST_HARD_REG_BIT (used, j)
1153 && (REGNO_REG_CLASS (j)
1154 == REGNO_REG_CLASS (best_reg + (j - i))
1155 || reg_class_subset_p (REGNO_REG_CLASS (j),
1156 REGNO_REG_CLASS (best_reg + (j - i)))
1157 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1158 REGNO_REG_CLASS (j))));
1159 j++);
1160 if (j == lim)
1162 best_reg = i;
1163 break;
1167 no_prefs:
1169 /* If we haven't succeeded yet, try with caller-saves.
1170 We need not check to see if the current function has nonlocal
1171 labels because we don't put any pseudos that are live over calls in
1172 registers in that case. */
1174 if (flag_caller_saves && best_reg < 0)
1176 /* Did not find a register. If it would be profitable to
1177 allocate a call-clobbered register and save and restore it
1178 around calls, do that. Don't do this if it crosses any calls
1179 that might throw. */
1180 if (! accept_call_clobbered
1181 && allocno[num].calls_crossed != 0
1182 && allocno[num].throwing_calls_crossed == 0
1183 && CALLER_SAVE_PROFITABLE (optimize_size ? allocno[num].n_refs : allocno[num].freq,
1184 optimize_size ? allocno[num].calls_crossed
1185 : allocno[num].freq_calls_crossed))
1187 HARD_REG_SET new_losers;
1188 if (! losers)
1189 CLEAR_HARD_REG_SET (new_losers);
1190 else
1191 COPY_HARD_REG_SET (new_losers, losers);
1193 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1194 find_reg (num, new_losers, alt_regs_p, 1, retrying);
1195 if (reg_renumber[allocno[num].reg] >= 0)
1197 caller_save_needed = 1;
1198 return;
1203 /* If we haven't succeeded yet,
1204 see if some hard reg that conflicts with us
1205 was utilized poorly by local-alloc.
1206 If so, kick out the regs that were put there by local-alloc
1207 so we can use it instead. */
1208 if (best_reg < 0 && !retrying
1209 /* Let's not bother with multi-reg allocnos. */
1210 && allocno[num].size == 1
1211 && REG_BASIC_BLOCK (allocno[num].reg) == REG_BLOCK_GLOBAL)
1213 /* Count from the end, to find the least-used ones first. */
1214 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1216 #ifdef REG_ALLOC_ORDER
1217 int regno = reg_alloc_order[i];
1218 #else
1219 int regno = i;
1220 #endif
1222 if (local_reg_n_refs[regno] != 0
1223 /* Don't use a reg no good for this pseudo. */
1224 && ! TEST_HARD_REG_BIT (used2, regno)
1225 && HARD_REGNO_MODE_OK (regno, mode)
1226 /* The code below assumes that we need only a single
1227 register, but the check of allocno[num].size above
1228 was not enough. Sometimes we need more than one
1229 register for a single-word value. */
1230 && hard_regno_nregs[regno][mode] == 1
1231 && (allocno[num].calls_crossed == 0
1232 || accept_call_clobbered
1233 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
1234 #ifdef CANNOT_CHANGE_MODE_CLASS
1235 && ! invalid_mode_change_p (regno, REGNO_REG_CLASS (regno),
1236 mode)
1237 #endif
1238 #ifdef STACK_REGS
1239 && (!allocno[num].no_stack_reg
1240 || regno < FIRST_STACK_REG || regno > LAST_STACK_REG)
1241 #endif
1244 /* We explicitly evaluate the divide results into temporary
1245 variables so as to avoid excess precision problems that occur
1246 on an i386-unknown-sysv4.2 (unixware) host. */
1248 double tmp1 = ((double) local_reg_freq[regno] * local_reg_n_refs[regno]
1249 / local_reg_live_length[regno]);
1250 double tmp2 = ((double) allocno[num].freq * allocno[num].n_refs
1251 / allocno[num].live_length);
1253 if (tmp1 < tmp2)
1255 /* Hard reg REGNO was used less in total by local regs
1256 than it would be used by this one allocno! */
1257 int k;
1258 if (dump_file)
1260 fprintf (dump_file, "Regno %d better for global %d, ",
1261 regno, allocno[num].reg);
1262 fprintf (dump_file, "fr:%d, ll:%d, nr:%d ",
1263 allocno[num].freq, allocno[num].live_length,
1264 allocno[num].n_refs);
1265 fprintf (dump_file, "(was: fr:%d, ll:%d, nr:%d)\n",
1266 local_reg_freq[regno],
1267 local_reg_live_length[regno],
1268 local_reg_n_refs[regno]);
1271 for (k = 0; k < max_regno; k++)
1272 if (reg_renumber[k] >= 0)
1274 int r = reg_renumber[k];
1275 int endregno
1276 = end_hard_regno (PSEUDO_REGNO_MODE (k), r);
1278 if (regno >= r && regno < endregno)
1280 if (dump_file)
1281 fprintf (dump_file,
1282 "Local Reg %d now on stack\n", k);
1283 reg_renumber[k] = -1;
1287 best_reg = regno;
1288 break;
1294 /* Did we find a register? */
1296 if (best_reg >= 0)
1298 int lim, j;
1299 HARD_REG_SET this_reg;
1300 adjacency_iter ai;
1302 /* Yes. Record it as the hard register of this pseudo-reg. */
1303 reg_renumber[allocno[num].reg] = best_reg;
1305 /* Make a set of the hard regs being allocated. */
1306 CLEAR_HARD_REG_SET (this_reg);
1307 lim = end_hard_regno (mode, best_reg);
1308 for (j = best_reg; j < lim; j++)
1310 SET_HARD_REG_BIT (this_reg, j);
1311 SET_HARD_REG_BIT (regs_used_so_far, j);
1312 /* This is no longer a reg used just by local regs. */
1313 local_reg_n_refs[j] = 0;
1314 local_reg_freq[j] = 0;
1316 /* For each other pseudo-reg conflicting with this one,
1317 mark it as conflicting with the hard regs this one occupies. */
1318 FOR_EACH_CONFLICT (num, j, ai)
1320 IOR_HARD_REG_SET (allocno[j].hard_reg_conflicts, this_reg);
1325 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1326 Perhaps it had previously seemed not worth a hard reg,
1327 or perhaps its old hard reg has been commandeered for reloads.
1328 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1329 they do not appear to be allocated.
1330 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1332 void
1333 retry_global_alloc (int regno, HARD_REG_SET forbidden_regs)
1335 int alloc_no = reg_allocno[regno];
1336 if (alloc_no >= 0)
1338 /* If we have more than one register class,
1339 first try allocating in the class that is cheapest
1340 for this pseudo-reg. If that fails, try any reg. */
1341 if (N_REG_CLASSES > 1)
1342 find_reg (alloc_no, forbidden_regs, 0, 0, 1);
1343 if (reg_renumber[regno] < 0
1344 && reg_alternate_class (regno) != NO_REGS)
1345 find_reg (alloc_no, forbidden_regs, 1, 0, 1);
1347 /* If we found a register, modify the RTL for the register to
1348 show the hard register, and mark that register live. */
1349 if (reg_renumber[regno] >= 0)
1351 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
1352 mark_home_live (regno);
1357 /* Indicate that hard register number FROM was eliminated and replaced with
1358 an offset from hard register number TO. The status of hard registers live
1359 at the start of a basic block is updated by replacing a use of FROM with
1360 a use of TO. */
1362 void
1363 mark_elimination (int from, int to)
1365 basic_block bb;
1367 FOR_EACH_BB (bb)
1369 regset r = DF_LIVE_IN (bb);
1370 if (REGNO_REG_SET_P (r, from))
1372 CLEAR_REGNO_REG_SET (r, from);
1373 SET_REGNO_REG_SET (r, to);
1378 /* Print chain C to FILE. */
1380 static void
1381 print_insn_chain (FILE *file, struct insn_chain *c)
1383 fprintf (file, "insn=%d, ", INSN_UID(c->insn));
1384 bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
1385 bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
1389 /* Print all reload_insn_chains to FILE. */
1391 static void
1392 print_insn_chains (FILE *file)
1394 struct insn_chain *c;
1395 for (c = reload_insn_chain; c ; c = c->next)
1396 print_insn_chain (file, c);
1400 /* Walk the insns of the current function and build reload_insn_chain,
1401 and record register life information. */
1403 static void
1404 build_insn_chain (void)
1406 unsigned int i;
1407 struct insn_chain **p = &reload_insn_chain;
1408 basic_block bb;
1409 struct insn_chain *c = NULL;
1410 struct insn_chain *next = NULL;
1411 bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
1412 bitmap elim_regset = BITMAP_ALLOC (NULL);
1413 /* live_subregs is a vector used to keep accurate information about
1414 which hardregs are live in multiword pseudos. live_subregs and
1415 live_subregs_used are indexed by pseudo number. The live_subreg
1416 entry for a particular pseudo is only used if the corresponding
1417 element is non zero in live_subregs_used. The value in
1418 live_subregs_used is number of bytes that the pseudo can
1419 occupy. */
1420 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
1421 int *live_subregs_used = XNEWVEC (int, max_regno);
1423 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1424 if (TEST_HARD_REG_BIT (eliminable_regset, i))
1425 bitmap_set_bit (elim_regset, i);
1427 FOR_EACH_BB_REVERSE (bb)
1429 bitmap_iterator bi;
1430 rtx insn;
1432 CLEAR_REG_SET (live_relevant_regs);
1433 memset (live_subregs_used, 0, max_regno * sizeof (int));
1435 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi)
1437 if (i >= FIRST_PSEUDO_REGISTER)
1438 break;
1439 bitmap_set_bit (live_relevant_regs, i);
1442 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), FIRST_PSEUDO_REGISTER, i, bi)
1444 if (reg_renumber[i] >= 0)
1445 bitmap_set_bit (live_relevant_regs, i);
1448 FOR_BB_INSNS_REVERSE (bb, insn)
1450 if (!NOTE_P (insn) && !BARRIER_P (insn))
1452 unsigned int uid = INSN_UID (insn);
1453 struct df_ref **def_rec;
1454 struct df_ref **use_rec;
1456 c = new_insn_chain ();
1457 c->next = next;
1458 next = c;
1459 *p = c;
1460 p = &c->prev;
1462 c->insn = insn;
1463 c->block = bb->index;
1465 if (INSN_P (insn))
1466 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1468 struct df_ref *def = *def_rec;
1469 unsigned int regno = DF_REF_REGNO (def);
1471 /* Ignore may clobbers because these are generated
1472 from calls. However, every other kind of def is
1473 added to dead_or_set. */
1474 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1476 if (regno < FIRST_PSEUDO_REGISTER)
1478 if (!fixed_regs[regno])
1479 bitmap_set_bit (&c->dead_or_set, regno);
1481 else if (reg_renumber[regno] >= 0)
1482 bitmap_set_bit (&c->dead_or_set, regno);
1485 if ((regno < FIRST_PSEUDO_REGISTER || reg_renumber[regno] >= 0)
1486 && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
1488 rtx reg = DF_REF_REG (def);
1490 /* We can model subregs, but not if they are
1491 wrapped in ZERO_EXTRACTS. */
1492 if (GET_CODE (reg) == SUBREG
1493 && !DF_REF_FLAGS_IS_SET (def, DF_REF_EXTRACT))
1495 unsigned int start = SUBREG_BYTE (reg);
1496 unsigned int last = start
1497 + GET_MODE_SIZE (GET_MODE (reg));
1499 ra_init_live_subregs (bitmap_bit_p (live_relevant_regs,
1500 regno),
1501 live_subregs,
1502 live_subregs_used,
1503 regno, reg);
1505 if (!DF_REF_FLAGS_IS_SET
1506 (def, DF_REF_STRICT_LOWER_PART))
1508 /* Expand the range to cover entire words.
1509 Bytes added here are "don't care". */
1510 start = start / UNITS_PER_WORD * UNITS_PER_WORD;
1511 last = ((last + UNITS_PER_WORD - 1)
1512 / UNITS_PER_WORD * UNITS_PER_WORD);
1515 /* Ignore the paradoxical bits. */
1516 if ((int)last > live_subregs_used[regno])
1517 last = live_subregs_used[regno];
1519 while (start < last)
1521 RESET_BIT (live_subregs[regno], start);
1522 start++;
1525 if (sbitmap_empty_p (live_subregs[regno]))
1527 live_subregs_used[regno] = 0;
1528 bitmap_clear_bit (live_relevant_regs, regno);
1530 else
1531 /* Set live_relevant_regs here because
1532 that bit has to be true to get us to
1533 look at the live_subregs fields. */
1534 bitmap_set_bit (live_relevant_regs, regno);
1536 else
1538 /* DF_REF_PARTIAL is generated for
1539 subregs, STRICT_LOW_PART, and
1540 ZERO_EXTRACT. We handle the subreg
1541 case above so here we have to keep from
1542 modeling the def as a killing def. */
1543 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
1545 bitmap_clear_bit (live_relevant_regs, regno);
1546 live_subregs_used[regno] = 0;
1552 bitmap_and_compl_into (live_relevant_regs, elim_regset);
1553 bitmap_copy (&c->live_throughout, live_relevant_regs);
1555 if (INSN_P (insn))
1556 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1558 struct df_ref *use = *use_rec;
1559 unsigned int regno = DF_REF_REGNO (use);
1560 rtx reg = DF_REF_REG (use);
1562 /* DF_REF_READ_WRITE on a use means that this use
1563 is fabricated from a def that is a partial set
1564 to a multiword reg. Here, we only model the
1565 subreg case that is not wrapped in ZERO_EXTRACT
1566 precisely so we do not need to look at the
1567 fabricated use. */
1568 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
1569 && !DF_REF_FLAGS_IS_SET (use, DF_REF_EXTRACT)
1570 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
1571 continue;
1573 /* Add the last use of each var to dead_or_set. */
1574 if (!bitmap_bit_p (live_relevant_regs, regno))
1576 if (regno < FIRST_PSEUDO_REGISTER)
1578 if (!fixed_regs[regno])
1579 bitmap_set_bit (&c->dead_or_set, regno);
1581 else if (reg_renumber[regno] >= 0)
1582 bitmap_set_bit (&c->dead_or_set, regno);
1585 if (regno < FIRST_PSEUDO_REGISTER || reg_renumber[regno] >= 0)
1587 if (GET_CODE (reg) == SUBREG
1588 && !DF_REF_FLAGS_IS_SET (use, DF_REF_EXTRACT))
1590 unsigned int start = SUBREG_BYTE (reg);
1591 unsigned int last = start
1592 + GET_MODE_SIZE (GET_MODE (reg));
1594 ra_init_live_subregs (bitmap_bit_p (live_relevant_regs,
1595 regno),
1596 live_subregs,
1597 live_subregs_used,
1598 regno, reg);
1600 /* Ignore the paradoxical bits. */
1601 if ((int)last > live_subregs_used[regno])
1602 last = live_subregs_used[regno];
1604 while (start < last)
1606 SET_BIT (live_subregs[regno], start);
1607 start++;
1610 else
1611 /* Resetting the live_subregs_used is
1612 effectively saying do not use the subregs
1613 because we are reading the whole
1614 pseudo. */
1615 live_subregs_used[regno] = 0;
1616 bitmap_set_bit (live_relevant_regs, regno);
1622 /* FIXME!! The following code is a disaster. Reload needs to see the
1623 labels and jump tables that are just hanging out in between
1624 the basic blocks. See pr33676. */
1625 insn = BB_HEAD (bb);
1627 /* Skip over the barriers and cruft. */
1628 while (insn && (BARRIER_P (insn) || NOTE_P (insn)
1629 || BLOCK_FOR_INSN (insn) == bb))
1630 insn = PREV_INSN (insn);
1632 /* While we add anything except barriers and notes, the focus is
1633 to get the labels and jump tables into the
1634 reload_insn_chain. */
1635 while (insn)
1637 if (!NOTE_P (insn) && !BARRIER_P (insn))
1639 if (BLOCK_FOR_INSN (insn))
1640 break;
1642 c = new_insn_chain ();
1643 c->next = next;
1644 next = c;
1645 *p = c;
1646 p = &c->prev;
1648 /* The block makes no sense here, but it is what the old
1649 code did. */
1650 c->block = bb->index;
1651 c->insn = insn;
1652 bitmap_copy (&c->live_throughout, live_relevant_regs);
1654 insn = PREV_INSN (insn);
1658 for (i = 0; i < (unsigned int) max_regno; i++)
1659 if (live_subregs[i])
1660 free (live_subregs[i]);
1662 reload_insn_chain = c;
1663 *p = NULL;
1665 free (live_subregs);
1666 free (live_subregs_used);
1667 BITMAP_FREE (live_relevant_regs);
1668 BITMAP_FREE (elim_regset);
1670 if (dump_file)
1671 print_insn_chains (dump_file);
1674 /* Print debugging trace information if -dg switch is given,
1675 showing the information on which the allocation decisions are based. */
1677 static void
1678 dump_conflicts (FILE *file)
1680 int i;
1681 int regno;
1682 int has_preferences;
1683 int nregs;
1684 nregs = 0;
1685 for (i = 0; i < max_allocno; i++)
1687 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1688 continue;
1689 nregs++;
1691 fprintf (file, ";; %d regs to allocate:", nregs);
1692 for (regno = 0; regno < max_regno; regno++)
1693 if ((i = reg_allocno[regno]) >= 0)
1695 int j;
1696 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1697 continue;
1698 fprintf (file, " %d", allocno[allocno_order[i]].reg);
1699 for (j = 0; j < max_regno; j++)
1700 if (reg_allocno[j] == allocno_order[i]
1701 && j != allocno[allocno_order[i]].reg)
1702 fprintf (file, "+%d", j);
1703 if (allocno[allocno_order[i]].size != 1)
1704 fprintf (file, " (%d)", allocno[allocno_order[i]].size);
1706 fprintf (file, "\n");
1708 for (regno = 0; regno < max_regno; regno++)
1709 if ((i = reg_allocno[regno]) >= 0)
1711 int j;
1712 adjacency_iter ai;
1713 fprintf (file, ";; %d conflicts:", allocno[i].reg);
1714 FOR_EACH_CONFLICT (i, j, ai)
1716 fprintf (file, " %d", allocno[j].reg);
1718 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1719 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_conflicts, j)
1720 && !fixed_regs[j])
1721 fprintf (file, " %d", j);
1722 fprintf (file, "\n");
1724 has_preferences = 0;
1725 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1726 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1727 has_preferences = 1;
1729 if (!has_preferences)
1730 continue;
1731 fprintf (file, ";; %d preferences:", allocno[i].reg);
1732 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1733 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1734 fprintf (file, " %d", j);
1735 fprintf (file, "\n");
1737 fprintf (file, "\n");
1740 void
1741 dump_global_regs (FILE *file)
1743 int i, j;
1745 fprintf (file, ";; Register dispositions:\n");
1746 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1747 if (reg_renumber[i] >= 0)
1749 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1750 if (++j % 6 == 0)
1751 fprintf (file, "\n");
1754 fprintf (file, "\n\n;; Hard regs used: ");
1755 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1756 if (df_regs_ever_live_p (i))
1757 fprintf (file, " %d", i);
1758 fprintf (file, "\n\n");
1761 /* Run old register allocator. Return TRUE if we must exit
1762 rest_of_compilation upon return. */
1763 static unsigned int
1764 rest_of_handle_global_alloc (void)
1766 bool failure;
1768 /* If optimizing, allocate remaining pseudo-regs. Do the reload
1769 pass fixing up any insns that are invalid. */
1770 if (optimize && dbg_cnt (global_alloc_at_func))
1771 failure = global_alloc ();
1772 else
1774 /* There is just too much going on in the register allocators to
1775 keep things up to date. At the end we have to rescan anyway
1776 because things change when the reload_completed flag is set.
1777 So we just turn off scanning and we will rescan by hand. */
1778 df_set_flags (DF_NO_INSN_RESCAN);
1779 compute_regsets (&eliminable_regset, &no_global_alloc_regs);
1780 build_insn_chain ();
1781 df_set_flags (DF_NO_INSN_RESCAN);
1782 failure = reload (get_insns (), 0);
1785 if (dump_enabled_p (pass_global_alloc.static_pass_number))
1787 timevar_push (TV_DUMP);
1788 dump_global_regs (dump_file);
1789 timevar_pop (TV_DUMP);
1792 /* FIXME: This appears on the surface to be wrong thing to be doing.
1793 So much of the compiler is designed to check reload_completed to
1794 see if it is running after reload that seems doomed to failure.
1795 We should be returning a value that says that we have found
1796 errors so that nothing but the cleanup passes are run
1797 afterwards. */
1798 gcc_assert (reload_completed || failure);
1799 reload_completed = !failure;
1801 /* The world has changed so much that at this point we might as well
1802 just rescan everything. Note that df_rescan_all_insns is not
1803 going to help here because it does not touch the artificial uses
1804 and defs. */
1805 df_finish_pass (true);
1806 if (optimize > 1)
1807 df_live_add_problem ();
1808 df_scan_alloc (NULL);
1809 df_scan_blocks ();
1811 if (optimize)
1812 df_analyze ();
1814 regstat_free_n_sets_and_refs ();
1815 regstat_free_ri ();
1816 return 0;
1819 struct tree_opt_pass pass_global_alloc =
1821 "greg", /* name */
1822 NULL, /* gate */
1823 rest_of_handle_global_alloc, /* execute */
1824 NULL, /* sub */
1825 NULL, /* next */
1826 0, /* static_pass_number */
1827 TV_GLOBAL_ALLOC, /* tv_id */
1828 0, /* properties_required */
1829 0, /* properties_provided */
1830 0, /* properties_destroyed */
1831 0, /* todo_flags_start */
1832 TODO_dump_func | TODO_verify_rtl_sharing
1833 | TODO_ggc_collect, /* todo_flags_finish */
1834 'g' /* letter */