Fix PR#.
[official-gcc.git] / gcc / global.c
blob690a80c8a85fc9f5562c5cd63d3f1fa5fd90b23f
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 /* Return true if *LOC contains an asm. */
136 static int
137 insn_contains_asm_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
139 if ( !*loc)
140 return 0;
141 if (GET_CODE (*loc) == ASM_OPERANDS)
142 return 1;
143 return 0;
147 /* Return true if INSN contains an ASM. */
149 static int
150 insn_contains_asm (rtx insn)
152 return for_each_rtx (&insn, insn_contains_asm_1, NULL);
156 static void
157 compute_regs_asm_clobbered (char *regs_asm_clobbered)
159 basic_block bb;
161 memset (regs_asm_clobbered, 0, sizeof (char) * FIRST_PSEUDO_REGISTER);
163 FOR_EACH_BB (bb)
165 rtx insn;
166 FOR_BB_INSNS_REVERSE (bb, insn)
168 struct df_ref **def_rec;
169 if (insn_contains_asm (insn))
170 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
172 struct df_ref *def = *def_rec;
173 unsigned int dregno = DF_REF_REGNO (def);
174 if (dregno < FIRST_PSEUDO_REGISTER)
176 unsigned int i;
177 enum machine_mode mode = GET_MODE (DF_REF_REAL_REG (def));
178 unsigned int end = dregno
179 + hard_regno_nregs[dregno][mode] - 1;
180 for (i = dregno; i <= end; ++i)
181 regs_asm_clobbered[i] = 1;
189 /* All registers that can be eliminated. */
191 static HARD_REG_SET eliminable_regset;
193 static int regno_compare (const void *, const void *);
194 static int allocno_compare (const void *, const void *);
195 static void expand_preferences (void);
196 static void prune_preferences (void);
197 static void set_preferences (void);
198 static void find_reg (int, HARD_REG_SET, int, int, int);
199 static void dump_conflicts (FILE *);
200 static void build_insn_chain (void);
203 /* Look through the list of eliminable registers. Set ELIM_SET to the
204 set of registers which may be eliminated. Set NO_GLOBAL_SET to the
205 set of registers which may not be used across blocks.
207 This will normally be called with ELIM_SET as the file static
208 variable eliminable_regset, and NO_GLOBAL_SET as the file static
209 variable NO_GLOBAL_ALLOC_REGS.
211 It also initializes global flag frame_pointer_needed. */
213 static void
214 compute_regsets (HARD_REG_SET *elim_set,
215 HARD_REG_SET *no_global_set)
218 /* Like regs_ever_live, but 1 if a reg is set or clobbered from an asm.
219 Unlike regs_ever_live, elements of this array corresponding to
220 eliminable regs like the frame pointer are set if an asm sets them. */
221 char *regs_asm_clobbered = XALLOCAVEC (char, FIRST_PSEUDO_REGISTER);
223 #ifdef ELIMINABLE_REGS
224 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
225 size_t i;
226 #endif
228 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
229 sp for alloca. So we can't eliminate the frame pointer in that
230 case. At some point, we should improve this by emitting the
231 sp-adjusting insns for this case. */
232 int need_fp
233 = (! flag_omit_frame_pointer
234 || (cfun->calls_alloca && EXIT_IGNORE_STACK)
235 || crtl->accesses_prior_frames
236 || crtl->stack_realign_needed
237 || FRAME_POINTER_REQUIRED);
239 frame_pointer_needed = need_fp;
241 max_regno = max_reg_num ();
242 compact_blocks ();
244 max_allocno = 0;
246 /* A machine may have certain hard registers that
247 are safe to use only within a basic block. */
249 CLEAR_HARD_REG_SET (*no_global_set);
250 CLEAR_HARD_REG_SET (*elim_set);
252 compute_regs_asm_clobbered (regs_asm_clobbered);
253 /* Build the regset of all eliminable registers and show we can't use those
254 that we already know won't be eliminated. */
255 #ifdef ELIMINABLE_REGS
256 for (i = 0; i < ARRAY_SIZE (eliminables); i++)
258 bool cannot_elim
259 = (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
260 || (eliminables[i].to == STACK_POINTER_REGNUM
261 && need_fp
262 && (! SUPPORTS_STACK_ALIGNMENT
263 || ! stack_realign_fp)));
265 if (!regs_asm_clobbered[eliminables[i].from])
267 SET_HARD_REG_BIT (*elim_set, eliminables[i].from);
269 if (cannot_elim)
270 SET_HARD_REG_BIT (*no_global_set, eliminables[i].from);
272 else if (cannot_elim)
273 error ("%s cannot be used in asm here",
274 reg_names[eliminables[i].from]);
275 else
276 df_set_regs_ever_live (eliminables[i].from, true);
278 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
279 if (!regs_asm_clobbered[HARD_FRAME_POINTER_REGNUM])
281 SET_HARD_REG_BIT (*elim_set, HARD_FRAME_POINTER_REGNUM);
282 if (need_fp)
283 SET_HARD_REG_BIT (*no_global_set, HARD_FRAME_POINTER_REGNUM);
285 else if (need_fp)
286 error ("%s cannot be used in asm here",
287 reg_names[HARD_FRAME_POINTER_REGNUM]);
288 else
289 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
290 #endif
292 #else
293 if (!regs_asm_clobbered[FRAME_POINTER_REGNUM])
295 SET_HARD_REG_BIT (*elim_set, FRAME_POINTER_REGNUM);
296 if (need_fp)
297 SET_HARD_REG_BIT (*no_global_set, FRAME_POINTER_REGNUM);
299 else if (need_fp)
300 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
301 else
302 df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
303 #endif
306 /* Perform allocation of pseudo-registers not allocated by local_alloc.
308 Return value is nonzero if reload failed
309 and we must not do any more for this function. */
311 static int
312 global_alloc (void)
314 int retval;
315 size_t i;
316 int max_blk;
317 int *num_allocnos_per_blk;
319 compute_regsets (&eliminable_regset, &no_global_alloc_regs);
321 /* Track which registers have already been used. Start with registers
322 explicitly in the rtl, then registers allocated by local register
323 allocation. */
325 CLEAR_HARD_REG_SET (regs_used_so_far);
326 #ifdef LEAF_REGISTERS
327 /* If we are doing the leaf function optimization, and this is a leaf
328 function, it means that the registers that take work to save are those
329 that need a register window. So prefer the ones that can be used in
330 a leaf function. */
332 const char *cheap_regs;
333 const char *const leaf_regs = LEAF_REGISTERS;
335 if (only_leaf_regs_used () && leaf_function_p ())
336 cheap_regs = leaf_regs;
337 else
338 cheap_regs = call_used_regs;
339 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
340 if (df_regs_ever_live_p (i) || cheap_regs[i])
341 SET_HARD_REG_BIT (regs_used_so_far, i);
343 #else
344 /* We consider registers that do not have to be saved over calls as if
345 they were already used since there is no cost in using them. */
346 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
347 if (df_regs_ever_live_p (i) || call_used_regs[i])
348 SET_HARD_REG_BIT (regs_used_so_far, i);
349 #endif
351 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
352 if (reg_renumber[i] >= 0)
353 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
355 /* Establish mappings from register number to allocation number
356 and vice versa. In the process, count the allocnos. */
358 reg_allocno = XNEWVEC (int, max_regno);
360 /* Initially fill the reg_allocno array with regno's... */
361 max_blk = 0;
362 max_allocno = 0;
363 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
364 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
365 that we are supposed to refrain from putting in a hard reg.
366 -2 means do make an allocno but don't allocate it. */
367 if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
368 /* Don't allocate pseudos that cross calls,
369 if this function receives a nonlocal goto. */
370 && (! cfun->has_nonlocal_label
371 || REG_N_CALLS_CROSSED (i) == 0))
373 int blk = regno_basic_block (i);
374 reg_allocno[max_allocno++] = i;
375 if (blk > max_blk)
376 max_blk = blk;
377 gcc_assert (REG_LIVE_LENGTH (i));
380 allocno = XCNEWVEC (struct allocno, max_allocno);
381 partial_bitnum = XNEWVEC (HOST_WIDE_INT, max_allocno);
382 num_allocnos_per_blk = XCNEWVEC (int, max_blk + 1);
384 /* ...so we can sort them in the order we want them to receive
385 their allocnos. */
386 qsort (reg_allocno, max_allocno, sizeof (int), regno_compare);
388 for (i = 0; i < (size_t) max_allocno; i++)
390 int regno = reg_allocno[i];
391 int blk = regno_basic_block (regno);
392 num_allocnos_per_blk[blk]++;
393 allocno[i].reg = regno;
394 allocno[i].size = PSEUDO_REGNO_SIZE (regno);
395 allocno[i].calls_crossed += REG_N_CALLS_CROSSED (regno);
396 allocno[i].freq_calls_crossed += REG_FREQ_CALLS_CROSSED (regno);
397 allocno[i].throwing_calls_crossed
398 += REG_N_THROWING_CALLS_CROSSED (regno);
399 allocno[i].n_refs += REG_N_REFS (regno);
400 allocno[i].freq += REG_FREQ (regno);
401 if (allocno[i].live_length < REG_LIVE_LENGTH (regno))
402 allocno[i].live_length = REG_LIVE_LENGTH (regno);
405 /* The "global" block must contain all allocnos. */
406 num_allocnos_per_blk[0] = max_allocno;
408 /* Now reinitialize the reg_allocno array in terms of the
409 optimized regno to allocno mapping we created above. */
410 for (i = 0; i < (size_t) max_regno; i++)
411 reg_allocno[i] = -1;
413 max_bitnum = 0;
414 for (i = 0; i < (size_t) max_allocno; i++)
416 int regno = allocno[i].reg;
417 int blk = regno_basic_block (regno);
418 int row_size = --num_allocnos_per_blk[blk];
419 reg_allocno[regno] = (int) i;
420 partial_bitnum[i] = (row_size > 0) ? max_bitnum - ((int) i + 1) : -1;
421 max_bitnum += row_size;
424 #ifdef ENABLE_CHECKING
425 gcc_assert (max_bitnum <=
426 (((HOST_WIDE_INT) max_allocno *
427 ((HOST_WIDE_INT) max_allocno - 1)) / 2));
428 #endif
430 if (dump_file)
432 HOST_WIDE_INT num_bits, num_bytes, actual_bytes;
434 fprintf (dump_file, "## max_blk: %d\n", max_blk);
435 fprintf (dump_file, "## max_regno: %d\n", max_regno);
436 fprintf (dump_file, "## max_allocno: %d\n", max_allocno);
438 num_bits = max_bitnum;
439 num_bytes = CEIL (num_bits, 8);
440 actual_bytes = num_bytes;
441 fprintf (dump_file, "## Compressed triangular bitmatrix size: ");
442 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bits, ", num_bits);
443 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bytes\n", num_bytes);
445 num_bits = ((HOST_WIDE_INT) max_allocno *
446 ((HOST_WIDE_INT) max_allocno - 1)) / 2;
447 num_bytes = CEIL (num_bits, 8);
448 fprintf (dump_file, "## Standard triangular bitmatrix size: ");
449 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bits, ", num_bits);
450 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bytes [%.2f%%]\n",
451 num_bytes, 100.0 * ((double) actual_bytes / (double) num_bytes));
453 num_bits = (HOST_WIDE_INT) max_allocno * (HOST_WIDE_INT) max_allocno;
454 num_bytes = CEIL (num_bits, 8);
455 fprintf (dump_file, "## Square bitmatrix size: ");
456 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bits, ", num_bits);
457 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bytes [%.2f%%]\n",
458 num_bytes, 100.0 * ((double) actual_bytes / (double) num_bytes));
461 /* Calculate amount of usage of each hard reg by pseudos
462 allocated by local-alloc. This is to see if we want to
463 override it. */
464 memset (local_reg_live_length, 0, sizeof local_reg_live_length);
465 memset (local_reg_n_refs, 0, sizeof local_reg_n_refs);
466 memset (local_reg_freq, 0, sizeof local_reg_freq);
467 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
468 if (reg_renumber[i] >= 0)
470 int regno = reg_renumber[i];
471 int endregno = end_hard_regno (PSEUDO_REGNO_MODE (i), regno);
472 int j;
474 for (j = regno; j < endregno; j++)
476 local_reg_n_refs[j] += REG_N_REFS (i);
477 local_reg_freq[j] += REG_FREQ (i);
478 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
482 /* We can't override local-alloc for a reg used not just by local-alloc. */
483 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
484 if (df_regs_ever_live_p (i))
485 local_reg_n_refs[i] = 0, local_reg_freq[i] = 0;
487 if (dump_file)
489 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
491 fprintf (dump_file, "%d REG_N_REFS=%d, REG_FREQ=%d, REG_LIVE_LENGTH=%d\n",
492 (int)i, REG_N_REFS (i), REG_FREQ (i), REG_LIVE_LENGTH (i));
494 fprintf (dump_file, "regs_ever_live =");
495 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
496 if (df_regs_ever_live_p (i))
497 fprintf (dump_file, " %d", (int)i);
498 fprintf (dump_file, "\n");
501 conflicts = NULL;
502 adjacency = NULL;
503 adjacency_pool = NULL;
505 /* If there is work to be done (at least one reg to allocate),
506 perform global conflict analysis and allocate the regs. */
508 if (max_allocno > 0)
510 /* We used to use alloca here, but the size of what it would try to
511 allocate would occasionally cause it to exceed the stack limit and
512 cause unpredictable core dumps. Some examples were > 2Mb in size. */
513 conflicts = XCNEWVEC (HOST_WIDEST_FAST_INT,
514 CEIL(max_bitnum, HOST_BITS_PER_WIDEST_FAST_INT));
516 adjacency = XCNEWVEC (adjacency_t *, max_allocno);
517 adjacency_pool = create_alloc_pool ("global_alloc adjacency list pool",
518 sizeof (adjacency_t), 1024);
520 /* Scan all the insns and compute the conflicts among allocnos
521 and between allocnos and hard regs. */
523 global_conflicts ();
525 /* There is just too much going on in the register allocators to
526 keep things up to date. At the end we have to rescan anyway
527 because things change when the reload_completed flag is set.
528 So we just turn off scanning and we will rescan by hand.
530 However, we needed to do the rescanning before this point to
531 get the new insns scanned inserted by local_alloc scanned for
532 global_conflicts. */
533 df_set_flags (DF_NO_INSN_RESCAN);
535 /* Eliminate conflicts between pseudos and eliminable registers. If
536 the register is not eliminated, the pseudo won't really be able to
537 live in the eliminable register, so the conflict doesn't matter.
538 If we do eliminate the register, the conflict will no longer exist.
539 So in either case, we can ignore the conflict. Likewise for
540 preferences. */
542 set_preferences ();
544 for (i = 0; i < (size_t) max_allocno; i++)
546 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_conflicts,
547 eliminable_regset);
548 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_copy_preferences,
549 eliminable_regset);
550 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_preferences,
551 eliminable_regset);
554 /* Try to expand the preferences by merging them between allocnos. */
556 expand_preferences ();
558 /* Determine the order to allocate the remaining pseudo registers. */
560 allocno_order = XNEWVEC (int, max_allocno);
561 for (i = 0; i < (size_t) max_allocno; i++)
562 allocno_order[i] = i;
564 /* Default the size to 1, since allocno_compare uses it to divide by.
565 Also convert allocno_live_length of zero to -1. A length of zero
566 can occur when all the registers for that allocno have reg_live_length
567 equal to -2. In this case, we want to make an allocno, but not
568 allocate it. So avoid the divide-by-zero and set it to a low
569 priority. */
571 for (i = 0; i < (size_t) max_allocno; i++)
573 if (allocno[i].size == 0)
574 allocno[i].size = 1;
575 if (allocno[i].live_length == 0)
576 allocno[i].live_length = -1;
579 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
581 prune_preferences ();
583 if (dump_file)
584 dump_conflicts (dump_file);
586 /* Try allocating them, one by one, in that order,
587 except for parameters marked with reg_live_length[regno] == -2. */
589 for (i = 0; i < (size_t) max_allocno; i++)
590 if (reg_renumber[allocno[allocno_order[i]].reg] < 0
591 && REG_LIVE_LENGTH (allocno[allocno_order[i]].reg) >= 0)
593 if (!dbg_cnt (global_alloc_at_reg))
594 break;
595 /* If we have more than one register class,
596 first try allocating in the class that is cheapest
597 for this pseudo-reg. If that fails, try any reg. */
598 if (N_REG_CLASSES > 1)
600 find_reg (allocno_order[i], 0, 0, 0, 0);
601 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
602 continue;
604 if (reg_alternate_class (allocno[allocno_order[i]].reg) != NO_REGS)
605 find_reg (allocno_order[i], 0, 1, 0, 0);
608 free (allocno_order);
609 free (conflicts);
612 /* Do the reloads now while the allocno data still exists, so that we can
613 try to assign new hard regs to any pseudo regs that are spilled. */
615 #if 0 /* We need to eliminate regs even if there is no rtl code,
616 for the sake of debugging information. */
617 if (n_basic_blocks > NUM_FIXED_BLOCKS)
618 #endif
620 build_insn_chain ();
621 retval = reload (get_insns (), 1);
624 /* Clean up. */
625 free (reg_allocno);
626 free (num_allocnos_per_blk);
627 free (partial_bitnum);
628 free (allocno);
629 if (adjacency != NULL)
631 free_alloc_pool (adjacency_pool);
632 free (adjacency);
635 return retval;
638 /* Sort predicate for ordering the regnos. We want the regno to allocno
639 mapping to have the property that all "global" regnos (ie, regnos that
640 are referenced in more than one basic block) have smaller allocno values
641 than "local" regnos (ie, regnos referenced in only one basic block).
642 In addition, for two basic blocks "i" and "j" with i < j, all regnos
643 local to basic block i should have smaller allocno values than regnos
644 local to basic block j.
645 Returns -1 (1) if *v1p should be allocated before (after) *v2p. */
647 static int
648 regno_compare (const void *v1p, const void *v2p)
650 int regno1 = *(const int *)v1p;
651 int regno2 = *(const int *)v2p;
652 int blk1 = REG_BASIC_BLOCK (regno1);
653 int blk2 = REG_BASIC_BLOCK (regno2);
655 /* Prefer lower numbered basic blocks. Note that global and unknown
656 blocks have negative values, giving them high precedence. */
657 if (blk1 - blk2)
658 return blk1 - blk2;
660 /* If both regs are referenced from the same block, sort by regno. */
661 return regno1 - regno2;
664 /* Sort predicate for ordering the allocnos.
665 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
667 static int
668 allocno_compare (const void *v1p, const void *v2p)
670 int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
671 /* Note that the quotient will never be bigger than
672 the value of floor_log2 times the maximum number of
673 times a register can occur in one insn (surely less than 100)
674 weighted by the frequency (maximally REG_FREQ_MAX).
675 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
676 int pri1
677 = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].freq)
678 / allocno[v1].live_length)
679 * (10000 / REG_FREQ_MAX) * allocno[v1].size);
680 int pri2
681 = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].freq)
682 / allocno[v2].live_length)
683 * (10000 / REG_FREQ_MAX) * allocno[v2].size);
684 if (pri2 - pri1)
685 return pri2 - pri1;
687 /* If regs are equally good, sort by allocno,
688 so that the results of qsort leave nothing to chance. */
689 return v1 - v2;
692 /* Expand the preference information by looking for cases where one allocno
693 dies in an insn that sets an allocno. If those two allocnos don't conflict,
694 merge any preferences between those allocnos. */
696 static void
697 expand_preferences (void)
699 rtx insn;
700 rtx link;
701 rtx set;
703 /* We only try to handle the most common cases here. Most of the cases
704 where this wins are reg-reg copies. */
706 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
707 if (INSN_P (insn)
708 && (set = single_set (insn)) != 0
709 && REG_P (SET_DEST (set))
710 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
711 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
712 if (REG_NOTE_KIND (link) == REG_DEAD
713 && REG_P (XEXP (link, 0))
714 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
715 && ! conflict_p (reg_allocno[REGNO (SET_DEST (set))],
716 reg_allocno[REGNO (XEXP (link, 0))]))
718 int a1 = reg_allocno[REGNO (SET_DEST (set))];
719 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
721 if (XEXP (link, 0) == SET_SRC (set))
723 IOR_HARD_REG_SET (allocno[a1].hard_reg_copy_preferences,
724 allocno[a2].hard_reg_copy_preferences);
725 IOR_HARD_REG_SET (allocno[a2].hard_reg_copy_preferences,
726 allocno[a1].hard_reg_copy_preferences);
729 IOR_HARD_REG_SET (allocno[a1].hard_reg_preferences,
730 allocno[a2].hard_reg_preferences);
731 IOR_HARD_REG_SET (allocno[a2].hard_reg_preferences,
732 allocno[a1].hard_reg_preferences);
733 IOR_HARD_REG_SET (allocno[a1].hard_reg_full_preferences,
734 allocno[a2].hard_reg_full_preferences);
735 IOR_HARD_REG_SET (allocno[a2].hard_reg_full_preferences,
736 allocno[a1].hard_reg_full_preferences);
741 /* Try to set a preference for an allocno to a hard register.
742 We are passed DEST and SRC which are the operands of a SET. It is known
743 that SRC is a register. If SRC or the first operand of SRC is a register,
744 try to set a preference. If one of the two is a hard register and the other
745 is a pseudo-register, mark the preference.
747 Note that we are not as aggressive as local-alloc in trying to tie a
748 pseudo-register to a hard register. */
750 static void
751 set_preference (rtx dest, rtx src)
753 unsigned int src_regno, dest_regno, end_regno;
754 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
755 to compensate for subregs in SRC or DEST. */
756 int offset = 0;
757 unsigned int i;
758 int copy = 1;
760 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
761 src = XEXP (src, 0), copy = 0;
763 /* Get the reg number for both SRC and DEST.
764 If neither is a reg, give up. */
766 if (REG_P (src))
767 src_regno = REGNO (src);
768 else if (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src)))
770 src_regno = REGNO (SUBREG_REG (src));
772 if (REGNO (SUBREG_REG (src)) < FIRST_PSEUDO_REGISTER)
773 offset += subreg_regno_offset (REGNO (SUBREG_REG (src)),
774 GET_MODE (SUBREG_REG (src)),
775 SUBREG_BYTE (src),
776 GET_MODE (src));
777 else
778 offset += (SUBREG_BYTE (src)
779 / REGMODE_NATURAL_SIZE (GET_MODE (src)));
781 else
782 return;
784 if (REG_P (dest))
785 dest_regno = REGNO (dest);
786 else if (GET_CODE (dest) == SUBREG && REG_P (SUBREG_REG (dest)))
788 dest_regno = REGNO (SUBREG_REG (dest));
790 if (REGNO (SUBREG_REG (dest)) < FIRST_PSEUDO_REGISTER)
791 offset -= subreg_regno_offset (REGNO (SUBREG_REG (dest)),
792 GET_MODE (SUBREG_REG (dest)),
793 SUBREG_BYTE (dest),
794 GET_MODE (dest));
795 else
796 offset -= (SUBREG_BYTE (dest)
797 / REGMODE_NATURAL_SIZE (GET_MODE (dest)));
799 else
800 return;
802 /* Convert either or both to hard reg numbers. */
804 if (reg_renumber[src_regno] >= 0)
805 src_regno = reg_renumber[src_regno];
807 if (reg_renumber[dest_regno] >= 0)
808 dest_regno = reg_renumber[dest_regno];
810 /* Now if one is a hard reg and the other is a global pseudo
811 then give the other a preference. */
813 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
814 && reg_allocno[src_regno] >= 0)
816 dest_regno -= offset;
817 if (dest_regno < FIRST_PSEUDO_REGISTER)
819 if (copy)
820 SET_REGBIT (hard_reg_copy_preferences,
821 reg_allocno[src_regno], dest_regno);
823 SET_REGBIT (hard_reg_preferences,
824 reg_allocno[src_regno], dest_regno);
825 end_regno = end_hard_regno (GET_MODE (dest), dest_regno);
826 for (i = dest_regno; i < end_regno; i++)
827 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
831 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
832 && reg_allocno[dest_regno] >= 0)
834 src_regno += offset;
835 if (src_regno < FIRST_PSEUDO_REGISTER)
837 if (copy)
838 SET_REGBIT (hard_reg_copy_preferences,
839 reg_allocno[dest_regno], src_regno);
841 SET_REGBIT (hard_reg_preferences,
842 reg_allocno[dest_regno], src_regno);
843 end_regno = end_hard_regno (GET_MODE (src), src_regno);
844 for (i = src_regno; i < end_regno; i++)
845 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
850 /* Helper function for set_preferences. */
851 static void
852 set_preferences_1 (rtx reg, const_rtx setter, void *data ATTRIBUTE_UNUSED)
854 if (GET_CODE (reg) == SUBREG)
855 reg = SUBREG_REG (reg);
857 if (!REG_P (reg))
858 return;
860 gcc_assert (setter);
861 if (GET_CODE (setter) != CLOBBER)
862 set_preference (reg, SET_SRC (setter));
865 /* Scan all of the insns and initialize the preferences. */
867 static void
868 set_preferences (void)
870 basic_block bb;
871 rtx insn;
872 FOR_EACH_BB (bb)
873 FOR_BB_INSNS_REVERSE (bb, insn)
875 if (!INSN_P (insn))
876 continue;
878 note_stores (PATTERN (insn), set_preferences_1, NULL);
884 /* Prune the preferences for global registers to exclude registers that cannot
885 be used.
887 Compute `regs_someone_prefers', which is a bitmask of the hard registers
888 that are preferred by conflicting registers of lower priority. If possible,
889 we will avoid using these registers. */
891 static void
892 prune_preferences (void)
894 int i;
895 int num;
896 int *allocno_to_order = XNEWVEC (int, max_allocno);
898 /* Scan least most important to most important.
899 For each allocno, remove from preferences registers that cannot be used,
900 either because of conflicts or register type. Then compute all registers
901 preferred by each lower-priority register that conflicts. */
903 for (i = max_allocno - 1; i >= 0; i--)
905 HARD_REG_SET temp;
907 num = allocno_order[i];
908 allocno_to_order[num] = i;
909 COPY_HARD_REG_SET (temp, allocno[num].hard_reg_conflicts);
911 if (allocno[num].calls_crossed == 0)
912 IOR_HARD_REG_SET (temp, fixed_reg_set);
913 else
914 IOR_HARD_REG_SET (temp, call_used_reg_set);
916 IOR_COMPL_HARD_REG_SET
917 (temp,
918 reg_class_contents[(int) reg_preferred_class (allocno[num].reg)]);
920 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, temp);
921 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, temp);
922 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_full_preferences, temp);
925 for (i = max_allocno - 1; i >= 0; i--)
927 /* Merge in the preferences of lower-priority registers (they have
928 already been pruned). If we also prefer some of those registers,
929 don't exclude them unless we are of a smaller size (in which case
930 we want to give the lower-priority allocno the first chance for
931 these registers). */
932 HARD_REG_SET temp, temp2;
933 int allocno2;
934 adjacency_iter ai;
936 num = allocno_order[i];
938 CLEAR_HARD_REG_SET (temp);
939 CLEAR_HARD_REG_SET (temp2);
941 FOR_EACH_CONFLICT (num, allocno2, ai)
943 if (allocno_to_order[allocno2] > i)
945 if (allocno[allocno2].size <= allocno[num].size)
946 IOR_HARD_REG_SET (temp,
947 allocno[allocno2].hard_reg_full_preferences);
948 else
949 IOR_HARD_REG_SET (temp2,
950 allocno[allocno2].hard_reg_full_preferences);
954 AND_COMPL_HARD_REG_SET (temp, allocno[num].hard_reg_full_preferences);
955 IOR_HARD_REG_SET (temp, temp2);
956 COPY_HARD_REG_SET (allocno[num].regs_someone_prefers, temp);
958 free (allocno_to_order);
961 /* Assign a hard register to allocno NUM; look for one that is the beginning
962 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
963 The registers marked in PREFREGS are tried first.
965 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
966 be used for this allocation.
968 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
969 Otherwise ignore that preferred class and use the alternate class.
971 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
972 will have to be saved and restored at calls.
974 RETRYING is nonzero if this is called from retry_global_alloc.
976 If we find one, record it in reg_renumber.
977 If not, do nothing. */
979 static void
980 find_reg (int num, HARD_REG_SET losers, int alt_regs_p, int accept_call_clobbered, int retrying)
982 int i, best_reg, pass;
983 HARD_REG_SET used, used1, used2;
985 enum reg_class rclass = (alt_regs_p
986 ? reg_alternate_class (allocno[num].reg)
987 : reg_preferred_class (allocno[num].reg));
988 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno[num].reg);
990 if (accept_call_clobbered)
991 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
992 else if (allocno[num].calls_crossed == 0)
993 COPY_HARD_REG_SET (used1, fixed_reg_set);
994 else
995 COPY_HARD_REG_SET (used1, call_used_reg_set);
997 /* Some registers should not be allocated in global-alloc. */
998 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
999 if (losers)
1000 IOR_HARD_REG_SET (used1, losers);
1002 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) rclass]);
1004 #ifdef EH_RETURN_DATA_REGNO
1005 if (allocno[num].no_eh_reg)
1007 unsigned int j;
1008 for (j = 0; ; ++j)
1010 unsigned int regno = EH_RETURN_DATA_REGNO (j);
1011 if (regno == INVALID_REGNUM)
1012 break;
1013 SET_HARD_REG_BIT (used1, regno);
1016 #endif
1018 COPY_HARD_REG_SET (used2, used1);
1020 IOR_HARD_REG_SET (used1, allocno[num].hard_reg_conflicts);
1022 #ifdef CANNOT_CHANGE_MODE_CLASS
1023 cannot_change_mode_set_regs (&used1, mode, allocno[num].reg);
1024 #endif
1026 /* Try each hard reg to see if it fits. Do this in two passes.
1027 In the first pass, skip registers that are preferred by some other pseudo
1028 to give it a better chance of getting one of those registers. Only if
1029 we can't get a register when excluding those do we take one of them.
1030 However, we never allocate a register for the first time in pass 0. */
1032 COPY_HARD_REG_SET (used, used1);
1033 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
1034 IOR_HARD_REG_SET (used, allocno[num].regs_someone_prefers);
1036 best_reg = -1;
1037 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
1038 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
1039 pass++)
1041 if (pass == 1)
1042 COPY_HARD_REG_SET (used, used1);
1043 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1045 #ifdef REG_ALLOC_ORDER
1046 int regno = reg_alloc_order[i];
1047 #else
1048 int regno = i;
1049 #endif
1050 if (! TEST_HARD_REG_BIT (used, regno)
1051 && HARD_REGNO_MODE_OK (regno, mode)
1052 && (allocno[num].calls_crossed == 0
1053 || accept_call_clobbered
1054 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
1056 int j;
1057 int lim = end_hard_regno (mode, regno);
1058 for (j = regno + 1;
1059 (j < lim
1060 && ! TEST_HARD_REG_BIT (used, j));
1061 j++);
1062 if (j == lim)
1064 best_reg = regno;
1065 break;
1067 #ifndef REG_ALLOC_ORDER
1068 i = j; /* Skip starting points we know will lose */
1069 #endif
1074 /* See if there is a preferred register with the same class as the register
1075 we allocated above. Making this restriction prevents register
1076 preferencing from creating worse register allocation.
1078 Remove from the preferred registers and conflicting registers. Note that
1079 additional conflicts may have been added after `prune_preferences' was
1080 called.
1082 First do this for those register with copy preferences, then all
1083 preferred registers. */
1085 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, used);
1086 if (!hard_reg_set_empty_p (allocno[num].hard_reg_copy_preferences)
1087 && best_reg >= 0)
1089 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1090 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_copy_preferences, i)
1091 && HARD_REGNO_MODE_OK (i, mode)
1092 && (allocno[num].calls_crossed == 0
1093 || accept_call_clobbered
1094 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1095 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1096 || reg_class_subset_p (REGNO_REG_CLASS (i),
1097 REGNO_REG_CLASS (best_reg))
1098 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1099 REGNO_REG_CLASS (i))))
1101 int j;
1102 int lim = end_hard_regno (mode, i);
1103 for (j = i + 1;
1104 (j < lim
1105 && ! TEST_HARD_REG_BIT (used, j)
1106 && (REGNO_REG_CLASS (j)
1107 == REGNO_REG_CLASS (best_reg + (j - i))
1108 || reg_class_subset_p (REGNO_REG_CLASS (j),
1109 REGNO_REG_CLASS (best_reg + (j - i)))
1110 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1111 REGNO_REG_CLASS (j))));
1112 j++);
1113 if (j == lim)
1115 best_reg = i;
1116 goto no_prefs;
1121 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, used);
1122 if (!hard_reg_set_empty_p (allocno[num].hard_reg_preferences)
1123 && best_reg >= 0)
1125 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1126 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_preferences, i)
1127 && HARD_REGNO_MODE_OK (i, mode)
1128 && (allocno[num].calls_crossed == 0
1129 || accept_call_clobbered
1130 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1131 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1132 || reg_class_subset_p (REGNO_REG_CLASS (i),
1133 REGNO_REG_CLASS (best_reg))
1134 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1135 REGNO_REG_CLASS (i))))
1137 int j;
1138 int lim = end_hard_regno (mode, i);
1139 for (j = i + 1;
1140 (j < lim
1141 && ! TEST_HARD_REG_BIT (used, j)
1142 && (REGNO_REG_CLASS (j)
1143 == REGNO_REG_CLASS (best_reg + (j - i))
1144 || reg_class_subset_p (REGNO_REG_CLASS (j),
1145 REGNO_REG_CLASS (best_reg + (j - i)))
1146 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1147 REGNO_REG_CLASS (j))));
1148 j++);
1149 if (j == lim)
1151 best_reg = i;
1152 break;
1156 no_prefs:
1158 /* If we haven't succeeded yet, try with caller-saves.
1159 We need not check to see if the current function has nonlocal
1160 labels because we don't put any pseudos that are live over calls in
1161 registers in that case. */
1163 if (flag_caller_saves && best_reg < 0)
1165 /* Did not find a register. If it would be profitable to
1166 allocate a call-clobbered register and save and restore it
1167 around calls, do that. Don't do this if it crosses any calls
1168 that might throw. */
1169 if (! accept_call_clobbered
1170 && allocno[num].calls_crossed != 0
1171 && allocno[num].throwing_calls_crossed == 0
1172 && CALLER_SAVE_PROFITABLE (optimize_size ? allocno[num].n_refs : allocno[num].freq,
1173 optimize_size ? allocno[num].calls_crossed
1174 : allocno[num].freq_calls_crossed))
1176 HARD_REG_SET new_losers;
1177 if (! losers)
1178 CLEAR_HARD_REG_SET (new_losers);
1179 else
1180 COPY_HARD_REG_SET (new_losers, losers);
1182 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1183 find_reg (num, new_losers, alt_regs_p, 1, retrying);
1184 if (reg_renumber[allocno[num].reg] >= 0)
1186 caller_save_needed = 1;
1187 return;
1192 /* If we haven't succeeded yet,
1193 see if some hard reg that conflicts with us
1194 was utilized poorly by local-alloc.
1195 If so, kick out the regs that were put there by local-alloc
1196 so we can use it instead. */
1197 if (best_reg < 0 && !retrying
1198 /* Let's not bother with multi-reg allocnos. */
1199 && allocno[num].size == 1
1200 && REG_BASIC_BLOCK (allocno[num].reg) == REG_BLOCK_GLOBAL)
1202 /* Count from the end, to find the least-used ones first. */
1203 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1205 #ifdef REG_ALLOC_ORDER
1206 int regno = reg_alloc_order[i];
1207 #else
1208 int regno = i;
1209 #endif
1211 if (local_reg_n_refs[regno] != 0
1212 /* Don't use a reg no good for this pseudo. */
1213 && ! TEST_HARD_REG_BIT (used2, regno)
1214 && HARD_REGNO_MODE_OK (regno, mode)
1215 /* The code below assumes that we need only a single
1216 register, but the check of allocno[num].size above
1217 was not enough. Sometimes we need more than one
1218 register for a single-word value. */
1219 && hard_regno_nregs[regno][mode] == 1
1220 && (allocno[num].calls_crossed == 0
1221 || accept_call_clobbered
1222 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
1223 #ifdef CANNOT_CHANGE_MODE_CLASS
1224 && ! invalid_mode_change_p (regno, REGNO_REG_CLASS (regno),
1225 mode)
1226 #endif
1227 #ifdef STACK_REGS
1228 && (!allocno[num].no_stack_reg
1229 || regno < FIRST_STACK_REG || regno > LAST_STACK_REG)
1230 #endif
1233 /* We explicitly evaluate the divide results into temporary
1234 variables so as to avoid excess precision problems that occur
1235 on an i386-unknown-sysv4.2 (unixware) host. */
1237 double tmp1 = ((double) local_reg_freq[regno] * local_reg_n_refs[regno]
1238 / local_reg_live_length[regno]);
1239 double tmp2 = ((double) allocno[num].freq * allocno[num].n_refs
1240 / allocno[num].live_length);
1242 if (tmp1 < tmp2)
1244 /* Hard reg REGNO was used less in total by local regs
1245 than it would be used by this one allocno! */
1246 int k;
1247 if (dump_file)
1249 fprintf (dump_file, "Regno %d better for global %d, ",
1250 regno, allocno[num].reg);
1251 fprintf (dump_file, "fr:%d, ll:%d, nr:%d ",
1252 allocno[num].freq, allocno[num].live_length,
1253 allocno[num].n_refs);
1254 fprintf (dump_file, "(was: fr:%d, ll:%d, nr:%d)\n",
1255 local_reg_freq[regno],
1256 local_reg_live_length[regno],
1257 local_reg_n_refs[regno]);
1260 for (k = 0; k < max_regno; k++)
1261 if (reg_renumber[k] >= 0)
1263 int r = reg_renumber[k];
1264 int endregno
1265 = end_hard_regno (PSEUDO_REGNO_MODE (k), r);
1267 if (regno >= r && regno < endregno)
1269 if (dump_file)
1270 fprintf (dump_file,
1271 "Local Reg %d now on stack\n", k);
1272 reg_renumber[k] = -1;
1276 best_reg = regno;
1277 break;
1283 /* Did we find a register? */
1285 if (best_reg >= 0)
1287 int lim, j;
1288 HARD_REG_SET this_reg;
1289 adjacency_iter ai;
1291 /* Yes. Record it as the hard register of this pseudo-reg. */
1292 reg_renumber[allocno[num].reg] = best_reg;
1294 /* Make a set of the hard regs being allocated. */
1295 CLEAR_HARD_REG_SET (this_reg);
1296 lim = end_hard_regno (mode, best_reg);
1297 for (j = best_reg; j < lim; j++)
1299 SET_HARD_REG_BIT (this_reg, j);
1300 SET_HARD_REG_BIT (regs_used_so_far, j);
1301 /* This is no longer a reg used just by local regs. */
1302 local_reg_n_refs[j] = 0;
1303 local_reg_freq[j] = 0;
1305 /* For each other pseudo-reg conflicting with this one,
1306 mark it as conflicting with the hard regs this one occupies. */
1307 FOR_EACH_CONFLICT (num, j, ai)
1309 IOR_HARD_REG_SET (allocno[j].hard_reg_conflicts, this_reg);
1314 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1315 Perhaps it had previously seemed not worth a hard reg,
1316 or perhaps its old hard reg has been commandeered for reloads.
1317 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1318 they do not appear to be allocated.
1319 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1321 void
1322 retry_global_alloc (int regno, HARD_REG_SET forbidden_regs)
1324 int alloc_no = reg_allocno[regno];
1325 if (alloc_no >= 0)
1327 /* If we have more than one register class,
1328 first try allocating in the class that is cheapest
1329 for this pseudo-reg. If that fails, try any reg. */
1330 if (N_REG_CLASSES > 1)
1331 find_reg (alloc_no, forbidden_regs, 0, 0, 1);
1332 if (reg_renumber[regno] < 0
1333 && reg_alternate_class (regno) != NO_REGS)
1334 find_reg (alloc_no, forbidden_regs, 1, 0, 1);
1336 /* If we found a register, modify the RTL for the register to
1337 show the hard register, and mark that register live. */
1338 if (reg_renumber[regno] >= 0)
1340 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
1341 mark_home_live (regno);
1346 /* Indicate that hard register number FROM was eliminated and replaced with
1347 an offset from hard register number TO. The status of hard registers live
1348 at the start of a basic block is updated by replacing a use of FROM with
1349 a use of TO. */
1351 void
1352 mark_elimination (int from, int to)
1354 basic_block bb;
1356 FOR_EACH_BB (bb)
1358 regset r = DF_LIVE_IN (bb);
1359 if (REGNO_REG_SET_P (r, from))
1361 CLEAR_REGNO_REG_SET (r, from);
1362 SET_REGNO_REG_SET (r, to);
1367 /* Print chain C to FILE. */
1369 static void
1370 print_insn_chain (FILE *file, struct insn_chain *c)
1372 fprintf (file, "insn=%d, ", INSN_UID(c->insn));
1373 bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
1374 bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
1378 /* Print all reload_insn_chains to FILE. */
1380 static void
1381 print_insn_chains (FILE *file)
1383 struct insn_chain *c;
1384 for (c = reload_insn_chain; c ; c = c->next)
1385 print_insn_chain (file, c);
1389 /* Walk the insns of the current function and build reload_insn_chain,
1390 and record register life information. */
1392 static void
1393 build_insn_chain (void)
1395 unsigned int i;
1396 struct insn_chain **p = &reload_insn_chain;
1397 basic_block bb;
1398 struct insn_chain *c = NULL;
1399 struct insn_chain *next = NULL;
1400 bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
1401 bitmap elim_regset = BITMAP_ALLOC (NULL);
1402 /* live_subregs is a vector used to keep accurate information about
1403 which hardregs are live in multiword pseudos. live_subregs and
1404 live_subregs_used are indexed by pseudo number. The live_subreg
1405 entry for a particular pseudo is only used if the corresponding
1406 element is non zero in live_subregs_used. The value in
1407 live_subregs_used is number of bytes that the pseudo can
1408 occupy. */
1409 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
1410 int *live_subregs_used = XNEWVEC (int, max_regno);
1412 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1413 if (TEST_HARD_REG_BIT (eliminable_regset, i))
1414 bitmap_set_bit (elim_regset, i);
1416 FOR_EACH_BB_REVERSE (bb)
1418 bitmap_iterator bi;
1419 rtx insn;
1421 CLEAR_REG_SET (live_relevant_regs);
1422 memset (live_subregs_used, 0, max_regno * sizeof (int));
1424 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi)
1426 if (i >= FIRST_PSEUDO_REGISTER)
1427 break;
1428 bitmap_set_bit (live_relevant_regs, i);
1431 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), FIRST_PSEUDO_REGISTER, i, bi)
1433 if (reg_renumber[i] >= 0)
1434 bitmap_set_bit (live_relevant_regs, i);
1437 FOR_BB_INSNS_REVERSE (bb, insn)
1439 if (!NOTE_P (insn) && !BARRIER_P (insn))
1441 unsigned int uid = INSN_UID (insn);
1442 struct df_ref **def_rec;
1443 struct df_ref **use_rec;
1445 c = new_insn_chain ();
1446 c->next = next;
1447 next = c;
1448 *p = c;
1449 p = &c->prev;
1451 c->insn = insn;
1452 c->block = bb->index;
1454 if (INSN_P (insn))
1455 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1457 struct df_ref *def = *def_rec;
1458 unsigned int regno = DF_REF_REGNO (def);
1460 /* Ignore may clobbers because these are generated
1461 from calls. However, every other kind of def is
1462 added to dead_or_set. */
1463 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1465 if (regno < FIRST_PSEUDO_REGISTER)
1467 if (!fixed_regs[regno])
1468 bitmap_set_bit (&c->dead_or_set, regno);
1470 else if (reg_renumber[regno] >= 0)
1471 bitmap_set_bit (&c->dead_or_set, regno);
1474 if ((regno < FIRST_PSEUDO_REGISTER || reg_renumber[regno] >= 0)
1475 && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
1477 rtx reg = DF_REF_REG (def);
1479 /* We can model subregs, but not if they are
1480 wrapped in ZERO_EXTRACTS. */
1481 if (GET_CODE (reg) == SUBREG
1482 && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
1484 unsigned int start = SUBREG_BYTE (reg);
1485 unsigned int last = start
1486 + GET_MODE_SIZE (GET_MODE (reg));
1488 ra_init_live_subregs (bitmap_bit_p (live_relevant_regs,
1489 regno),
1490 live_subregs,
1491 live_subregs_used,
1492 regno, reg);
1494 if (!DF_REF_FLAGS_IS_SET
1495 (def, DF_REF_STRICT_LOW_PART))
1497 /* Expand the range to cover entire words.
1498 Bytes added here are "don't care". */
1499 start = start / UNITS_PER_WORD * UNITS_PER_WORD;
1500 last = ((last + UNITS_PER_WORD - 1)
1501 / UNITS_PER_WORD * UNITS_PER_WORD);
1504 /* Ignore the paradoxical bits. */
1505 if ((int)last > live_subregs_used[regno])
1506 last = live_subregs_used[regno];
1508 while (start < last)
1510 RESET_BIT (live_subregs[regno], start);
1511 start++;
1514 if (sbitmap_empty_p (live_subregs[regno]))
1516 live_subregs_used[regno] = 0;
1517 bitmap_clear_bit (live_relevant_regs, regno);
1519 else
1520 /* Set live_relevant_regs here because
1521 that bit has to be true to get us to
1522 look at the live_subregs fields. */
1523 bitmap_set_bit (live_relevant_regs, regno);
1525 else
1527 /* DF_REF_PARTIAL is generated for
1528 subregs, STRICT_LOW_PART, and
1529 ZERO_EXTRACT. We handle the subreg
1530 case above so here we have to keep from
1531 modeling the def as a killing def. */
1532 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
1534 bitmap_clear_bit (live_relevant_regs, regno);
1535 live_subregs_used[regno] = 0;
1541 bitmap_and_compl_into (live_relevant_regs, elim_regset);
1542 bitmap_copy (&c->live_throughout, live_relevant_regs);
1544 if (INSN_P (insn))
1545 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1547 struct df_ref *use = *use_rec;
1548 unsigned int regno = DF_REF_REGNO (use);
1549 rtx reg = DF_REF_REG (use);
1551 /* DF_REF_READ_WRITE on a use means that this use
1552 is fabricated from a def that is a partial set
1553 to a multiword reg. Here, we only model the
1554 subreg case that is not wrapped in ZERO_EXTRACT
1555 precisely so we do not need to look at the
1556 fabricated use. */
1557 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
1558 && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
1559 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
1560 continue;
1562 /* Add the last use of each var to dead_or_set. */
1563 if (!bitmap_bit_p (live_relevant_regs, regno))
1565 if (regno < FIRST_PSEUDO_REGISTER)
1567 if (!fixed_regs[regno])
1568 bitmap_set_bit (&c->dead_or_set, regno);
1570 else if (reg_renumber[regno] >= 0)
1571 bitmap_set_bit (&c->dead_or_set, regno);
1574 if (regno < FIRST_PSEUDO_REGISTER || reg_renumber[regno] >= 0)
1576 if (GET_CODE (reg) == SUBREG
1577 && !DF_REF_FLAGS_IS_SET (use,
1578 DF_REF_SIGN_EXTRACT | DF_REF_ZERO_EXTRACT))
1580 unsigned int start = SUBREG_BYTE (reg);
1581 unsigned int last = start
1582 + GET_MODE_SIZE (GET_MODE (reg));
1584 ra_init_live_subregs (bitmap_bit_p (live_relevant_regs,
1585 regno),
1586 live_subregs,
1587 live_subregs_used,
1588 regno, reg);
1590 /* Ignore the paradoxical bits. */
1591 if ((int)last > live_subregs_used[regno])
1592 last = live_subregs_used[regno];
1594 while (start < last)
1596 SET_BIT (live_subregs[regno], start);
1597 start++;
1600 else
1601 /* Resetting the live_subregs_used is
1602 effectively saying do not use the subregs
1603 because we are reading the whole
1604 pseudo. */
1605 live_subregs_used[regno] = 0;
1606 bitmap_set_bit (live_relevant_regs, regno);
1612 /* FIXME!! The following code is a disaster. Reload needs to see the
1613 labels and jump tables that are just hanging out in between
1614 the basic blocks. See pr33676. */
1615 insn = BB_HEAD (bb);
1617 /* Skip over the barriers and cruft. */
1618 while (insn && (BARRIER_P (insn) || NOTE_P (insn)
1619 || BLOCK_FOR_INSN (insn) == bb))
1620 insn = PREV_INSN (insn);
1622 /* While we add anything except barriers and notes, the focus is
1623 to get the labels and jump tables into the
1624 reload_insn_chain. */
1625 while (insn)
1627 if (!NOTE_P (insn) && !BARRIER_P (insn))
1629 if (BLOCK_FOR_INSN (insn))
1630 break;
1632 c = new_insn_chain ();
1633 c->next = next;
1634 next = c;
1635 *p = c;
1636 p = &c->prev;
1638 /* The block makes no sense here, but it is what the old
1639 code did. */
1640 c->block = bb->index;
1641 c->insn = insn;
1642 bitmap_copy (&c->live_throughout, live_relevant_regs);
1644 insn = PREV_INSN (insn);
1648 for (i = 0; i < (unsigned int) max_regno; i++)
1649 if (live_subregs[i])
1650 free (live_subregs[i]);
1652 reload_insn_chain = c;
1653 *p = NULL;
1655 free (live_subregs);
1656 free (live_subregs_used);
1657 BITMAP_FREE (live_relevant_regs);
1658 BITMAP_FREE (elim_regset);
1660 if (dump_file)
1661 print_insn_chains (dump_file);
1664 /* Print debugging trace information if -dg switch is given,
1665 showing the information on which the allocation decisions are based. */
1667 static void
1668 dump_conflicts (FILE *file)
1670 int i;
1671 int regno;
1672 int has_preferences;
1673 int nregs;
1674 nregs = 0;
1675 for (i = 0; i < max_allocno; i++)
1677 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1678 continue;
1679 nregs++;
1681 fprintf (file, ";; %d regs to allocate:", nregs);
1682 for (regno = 0; regno < max_regno; regno++)
1683 if ((i = reg_allocno[regno]) >= 0)
1685 int j;
1686 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1687 continue;
1688 fprintf (file, " %d", allocno[allocno_order[i]].reg);
1689 for (j = 0; j < max_regno; j++)
1690 if (reg_allocno[j] == allocno_order[i]
1691 && j != allocno[allocno_order[i]].reg)
1692 fprintf (file, "+%d", j);
1693 if (allocno[allocno_order[i]].size != 1)
1694 fprintf (file, " (%d)", allocno[allocno_order[i]].size);
1696 fprintf (file, "\n");
1698 for (regno = 0; regno < max_regno; regno++)
1699 if ((i = reg_allocno[regno]) >= 0)
1701 int j;
1702 adjacency_iter ai;
1703 fprintf (file, ";; %d conflicts:", allocno[i].reg);
1704 FOR_EACH_CONFLICT (i, j, ai)
1706 fprintf (file, " %d", allocno[j].reg);
1708 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1709 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_conflicts, j)
1710 && !fixed_regs[j])
1711 fprintf (file, " %d", j);
1712 fprintf (file, "\n");
1714 has_preferences = 0;
1715 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1716 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1717 has_preferences = 1;
1719 if (!has_preferences)
1720 continue;
1721 fprintf (file, ";; %d preferences:", allocno[i].reg);
1722 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1723 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1724 fprintf (file, " %d", j);
1725 fprintf (file, "\n");
1727 fprintf (file, "\n");
1730 void
1731 dump_global_regs (FILE *file)
1733 int i, j;
1735 fprintf (file, ";; Register dispositions:\n");
1736 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1737 if (reg_renumber[i] >= 0)
1739 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1740 if (++j % 6 == 0)
1741 fprintf (file, "\n");
1744 fprintf (file, "\n\n;; Hard regs used: ");
1745 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1746 if (df_regs_ever_live_p (i))
1747 fprintf (file, " %d", i);
1748 fprintf (file, "\n\n");
1751 /* Run old register allocator. Return TRUE if we must exit
1752 rest_of_compilation upon return. */
1753 static unsigned int
1754 rest_of_handle_global_alloc (void)
1756 bool failure;
1758 /* If optimizing, allocate remaining pseudo-regs. Do the reload
1759 pass fixing up any insns that are invalid. */
1760 if (optimize && dbg_cnt (global_alloc_at_func))
1761 failure = global_alloc ();
1762 else
1764 /* There is just too much going on in the register allocators to
1765 keep things up to date. At the end we have to rescan anyway
1766 because things change when the reload_completed flag is set.
1767 So we just turn off scanning and we will rescan by hand. */
1768 df_set_flags (DF_NO_INSN_RESCAN);
1769 compute_regsets (&eliminable_regset, &no_global_alloc_regs);
1770 build_insn_chain ();
1771 df_set_flags (DF_NO_INSN_RESCAN);
1772 failure = reload (get_insns (), 0);
1775 if (dump_enabled_p (pass_global_alloc.pass.static_pass_number))
1777 timevar_push (TV_DUMP);
1778 dump_global_regs (dump_file);
1779 timevar_pop (TV_DUMP);
1782 /* FIXME: This appears on the surface to be wrong thing to be doing.
1783 So much of the compiler is designed to check reload_completed to
1784 see if it is running after reload that seems doomed to failure.
1785 We should be returning a value that says that we have found
1786 errors so that nothing but the cleanup passes are run
1787 afterwards. */
1788 gcc_assert (reload_completed || failure);
1789 reload_completed = !failure;
1791 /* The world has changed so much that at this point we might as well
1792 just rescan everything. Note that df_rescan_all_insns is not
1793 going to help here because it does not touch the artificial uses
1794 and defs. */
1795 df_finish_pass (true);
1796 if (optimize > 1)
1797 df_live_add_problem ();
1798 df_scan_alloc (NULL);
1799 df_scan_blocks ();
1801 if (optimize)
1802 df_analyze ();
1804 regstat_free_n_sets_and_refs ();
1805 regstat_free_ri ();
1806 return 0;
1809 struct rtl_opt_pass pass_global_alloc =
1812 RTL_PASS,
1813 "greg", /* name */
1814 NULL, /* gate */
1815 rest_of_handle_global_alloc, /* execute */
1816 NULL, /* sub */
1817 NULL, /* next */
1818 0, /* static_pass_number */
1819 TV_GLOBAL_ALLOC, /* tv_id */
1820 0, /* properties_required */
1821 0, /* properties_provided */
1822 0, /* properties_destroyed */
1823 0, /* todo_flags_start */
1824 TODO_dump_func | TODO_verify_rtl_sharing
1825 | TODO_ggc_collect /* todo_flags_finish */