![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to global.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 2.x] / gcc|
Return to global.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Allocate registers for pseudo-registers that span basic blocks.
1.1.1.4 root 2: Copyright (C) 1987, 1988, 1991, 1994 Free Software Foundation, Inc.
1.1 root 3:
4: This file is part of GNU CC.
5:
6: GNU CC is free software; you can redistribute it and/or modify
7: it under the terms of the GNU General Public License as published by
8: the Free Software Foundation; either version 2, or (at your option)
9: any later version.
10:
11: GNU CC is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14: GNU General Public License for more details.
15:
16: You should have received a copy of the GNU General Public License
17: along with GNU CC; see the file COPYING. If not, write to
1.1.1.5 ! root 18: the Free Software Foundation, 59 Temple Place - Suite 330,
! 19: Boston, MA 02111-1307, USA. */
1.1 root 20:
21:
22: #include <stdio.h>
23: #include "config.h"
24: #include "rtl.h"
25: #include "flags.h"
26: #include "basic-block.h"
27: #include "hard-reg-set.h"
28: #include "regs.h"
29: #include "insn-config.h"
30: #include "output.h"
31:
32: /* This pass of the compiler performs global register allocation.
33: It assigns hard register numbers to all the pseudo registers
34: that were not handled in local_alloc. Assignments are recorded
35: in the vector reg_renumber, not by changing the rtl code.
36: (Such changes are made by final). The entry point is
37: the function global_alloc.
38:
39: After allocation is complete, the reload pass is run as a subroutine
40: of this pass, so that when a pseudo reg loses its hard reg due to
41: spilling it is possible to make a second attempt to find a hard
42: reg for it. The reload pass is independent in other respects
43: and it is run even when stupid register allocation is in use.
44:
45: 1. count the pseudo-registers still needing allocation
46: and assign allocation-numbers (allocnos) to them.
47: Set up tables reg_allocno and allocno_reg to map
48: reg numbers to allocnos and vice versa.
49: max_allocno gets the number of allocnos in use.
50:
51: 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
52: Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
53: for conflicts between allocnos and explicit hard register use
54: (which includes use of pseudo-registers allocated by local_alloc).
55:
56: 3. for each basic block
57: walk forward through the block, recording which
58: unallocated registers and which hardware registers are live.
59: Build the conflict matrix between the unallocated registers
60: and another of unallocated registers versus hardware registers.
61: Also record the preferred hardware registers
62: for each unallocated one.
63:
64: 4. Sort a table of the allocnos into order of
65: desirability of the variables.
66:
67: 5. Allocate the variables in that order; each if possible into
68: a preferred register, else into another register. */
69:
70: /* Number of pseudo-registers still requiring allocation
71: (not allocated by local_allocate). */
72:
73: static int max_allocno;
74:
75: /* Indexed by (pseudo) reg number, gives the allocno, or -1
76: for pseudo registers already allocated by local_allocate. */
77:
78: static int *reg_allocno;
79:
80: /* Indexed by allocno, gives the reg number. */
81:
82: static int *allocno_reg;
83:
84: /* A vector of the integers from 0 to max_allocno-1,
85: sorted in the order of first-to-be-allocated first. */
86:
87: static int *allocno_order;
88:
89: /* Indexed by an allocno, gives the number of consecutive
90: hard registers needed by that pseudo reg. */
91:
92: static int *allocno_size;
93:
94: /* Indexed by (pseudo) reg number, gives the number of another
95: lower-numbered pseudo reg which can share a hard reg with this pseudo
96: *even if the two pseudos would otherwise appear to conflict*. */
97:
98: static int *reg_may_share;
99:
100: /* Define the number of bits in each element of `conflicts' and what
101: type that element has. We use the largest integer format on the
102: host machine. */
103:
104: #define INT_BITS HOST_BITS_PER_WIDE_INT
105: #define INT_TYPE HOST_WIDE_INT
106:
107: /* max_allocno by max_allocno array of bits,
108: recording whether two allocno's conflict (can't go in the same
109: hardware register).
110:
111: `conflicts' is not symmetric; a conflict between allocno's i and j
112: is recorded either in element i,j or in element j,i. */
113:
114: static INT_TYPE *conflicts;
115:
116: /* Number of ints require to hold max_allocno bits.
117: This is the length of a row in `conflicts'. */
118:
119: static int allocno_row_words;
120:
121: /* Two macros to test or store 1 in an element of `conflicts'. */
122:
123: #define CONFLICTP(I, J) \
124: (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
125: & ((INT_TYPE) 1 << ((J) % INT_BITS)))
126:
127: #define SET_CONFLICT(I, J) \
128: (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
129: |= ((INT_TYPE) 1 << ((J) % INT_BITS)))
130:
131: /* Set of hard regs currently live (during scan of all insns). */
132:
133: static HARD_REG_SET hard_regs_live;
134:
135: /* Indexed by N, set of hard regs conflicting with allocno N. */
136:
137: static HARD_REG_SET *hard_reg_conflicts;
138:
139: /* Indexed by N, set of hard regs preferred by allocno N.
140: This is used to make allocnos go into regs that are copied to or from them,
141: when possible, to reduce register shuffling. */
142:
143: static HARD_REG_SET *hard_reg_preferences;
144:
145: /* Similar, but just counts register preferences made in simple copy
146: operations, rather than arithmetic. These are given priority because
147: we can always eliminate an insn by using these, but using a register
148: in the above list won't always eliminate an insn. */
149:
150: static HARD_REG_SET *hard_reg_copy_preferences;
151:
152: /* Similar to hard_reg_preferences, but includes bits for subsequent
153: registers when an allocno is multi-word. The above variable is used for
154: allocation while this is used to build reg_someone_prefers, below. */
155:
156: static HARD_REG_SET *hard_reg_full_preferences;
157:
158: /* Indexed by N, set of hard registers that some later allocno has a
159: preference for. */
160:
161: static HARD_REG_SET *regs_someone_prefers;
162:
163: /* Set of registers that global-alloc isn't supposed to use. */
164:
165: static HARD_REG_SET no_global_alloc_regs;
166:
167: /* Set of registers used so far. */
168:
169: static HARD_REG_SET regs_used_so_far;
170:
171: /* Number of calls crossed by each allocno. */
172:
173: static int *allocno_calls_crossed;
174:
175: /* Number of refs (weighted) to each allocno. */
176:
177: static int *allocno_n_refs;
178:
179: /* Guess at live length of each allocno.
180: This is actually the max of the live lengths of the regs. */
181:
182: static int *allocno_live_length;
183:
184: /* Number of refs (weighted) to each hard reg, as used by local alloc.
185: It is zero for a reg that contains global pseudos or is explicitly used. */
186:
187: static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
188:
189: /* Guess at live length of each hard reg, as used by local alloc.
190: This is actually the sum of the live lengths of the specific regs. */
191:
192: static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
193:
194: /* Test a bit in TABLE, a vector of HARD_REG_SETs,
195: for vector element I, and hard register number J. */
196:
197: #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
198:
199: /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
200:
201: #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
202:
203: /* Bit mask for allocnos live at current point in the scan. */
204:
205: static INT_TYPE *allocnos_live;
206:
207: /* Test, set or clear bit number I in allocnos_live,
208: a bit vector indexed by allocno. */
209:
210: #define ALLOCNO_LIVE_P(I) \
211: (allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS)))
212:
213: #define SET_ALLOCNO_LIVE(I) \
214: (allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS)))
215:
216: #define CLEAR_ALLOCNO_LIVE(I) \
217: (allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((I) % INT_BITS)))
218:
219: /* This is turned off because it doesn't work right for DImode.
220: (And it is only used for DImode, so the other cases are worthless.)
221: The problem is that it isn't true that there is NO possibility of conflict;
222: only that there is no conflict if the two pseudos get the exact same regs.
223: If they were allocated with a partial overlap, there would be a conflict.
224: We can't safely turn off the conflict unless we have another way to
225: prevent the partial overlap.
226:
227: Idea: change hard_reg_conflicts so that instead of recording which
228: hard regs the allocno may not overlap, it records where the allocno
229: may not start. Change both where it is used and where it is updated.
230: Then there is a way to record that (reg:DI 108) may start at 10
231: but not at 9 or 11. There is still the question of how to record
232: this semi-conflict between two pseudos. */
233: #if 0
234: /* Reg pairs for which conflict after the current insn
235: is inhibited by a REG_NO_CONFLICT note.
236: If the table gets full, we ignore any other notes--that is conservative. */
237: #define NUM_NO_CONFLICT_PAIRS 4
238: /* Number of pairs in use in this insn. */
239: int n_no_conflict_pairs;
240: static struct { int allocno1, allocno2;}
241: no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
242: #endif /* 0 */
243:
244: /* Record all regs that are set in any one insn.
245: Communication from mark_reg_{store,clobber} and global_conflicts. */
246:
247: static rtx *regs_set;
248: static int n_regs_set;
249:
1.1.1.4 root 250: /* All registers that can be eliminated. */
1.1 root 251:
252: static HARD_REG_SET eliminable_regset;
253:
1.1.1.4 root 254: static int allocno_compare PROTO((int *, int *));
255: static void global_conflicts PROTO((void));
256: static void expand_preferences PROTO((void));
257: static void prune_preferences PROTO((void));
258: static void find_reg PROTO((int, HARD_REG_SET, int, int, int));
259: static void record_one_conflict PROTO((int));
260: static void record_conflicts PROTO((short *, int));
261: static void mark_reg_store PROTO((rtx, rtx));
262: static void mark_reg_clobber PROTO((rtx, rtx));
263: static void mark_reg_conflicts PROTO((rtx));
264: static void mark_reg_death PROTO((rtx));
265: static void mark_reg_live_nc PROTO((int, enum machine_mode));
266: static void set_preference PROTO((rtx, rtx));
267: static void dump_conflicts PROTO((FILE *));
1.1 root 268:
269: /* Perform allocation of pseudo-registers not allocated by local_alloc.
270: FILE is a file to output debugging information on,
271: or zero if such output is not desired.
272:
273: Return value is nonzero if reload failed
274: and we must not do any more for this function. */
275:
276: int
277: global_alloc (file)
278: FILE *file;
279: {
280: #ifdef ELIMINABLE_REGS
281: static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
282: #endif
1.1.1.4 root 283: int need_fp
284: = (! flag_omit_frame_pointer
285: #ifdef EXIT_IGNORE_STACK
286: || (current_function_calls_alloca && EXIT_IGNORE_STACK)
287: #endif
288: || FRAME_POINTER_REQUIRED);
289:
1.1 root 290: register int i;
291: rtx x;
292:
293: max_allocno = 0;
294:
295: /* A machine may have certain hard registers that
296: are safe to use only within a basic block. */
297:
298: CLEAR_HARD_REG_SET (no_global_alloc_regs);
299: #ifdef OVERLAPPING_REGNO_P
300: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
301: if (OVERLAPPING_REGNO_P (i))
302: SET_HARD_REG_BIT (no_global_alloc_regs, i);
303: #endif
304:
305: /* Build the regset of all eliminable registers and show we can't use those
306: that we already know won't be eliminated. */
307: #ifdef ELIMINABLE_REGS
308: for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
309: {
310: SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
311:
312: if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
1.1.1.4 root 313: || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp))
1.1 root 314: SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from);
315: }
1.1.1.3 root 316: #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1.1.1.4 root 317: SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
318: if (need_fp)
1.1.1.3 root 319: SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM);
320: #endif
1.1.1.4 root 321:
1.1 root 322: #else
323: SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
1.1.1.4 root 324: if (need_fp)
1.1 root 325: SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
326: #endif
327:
328: /* Track which registers have already been used. Start with registers
329: explicitly in the rtl, then registers allocated by local register
330: allocation. */
331:
332: CLEAR_HARD_REG_SET (regs_used_so_far);
333: #ifdef LEAF_REGISTERS
334: /* If we are doing the leaf function optimization, and this is a leaf
335: function, it means that the registers that take work to save are those
336: that need a register window. So prefer the ones that can be used in
337: a leaf function. */
338: {
339: char *cheap_regs;
340: static char leaf_regs[] = LEAF_REGISTERS;
341:
342: if (only_leaf_regs_used () && leaf_function_p ())
343: cheap_regs = leaf_regs;
344: else
345: cheap_regs = call_used_regs;
346: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
347: if (regs_ever_live[i] || cheap_regs[i])
348: SET_HARD_REG_BIT (regs_used_so_far, i);
349: }
350: #else
351: /* We consider registers that do not have to be saved over calls as if
352: they were already used since there is no cost in using them. */
353: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
354: if (regs_ever_live[i] || call_used_regs[i])
355: SET_HARD_REG_BIT (regs_used_so_far, i);
356: #endif
357:
358: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
359: if (reg_renumber[i] >= 0)
360: SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
361:
362: /* Establish mappings from register number to allocation number
363: and vice versa. In the process, count the allocnos. */
364:
365: reg_allocno = (int *) alloca (max_regno * sizeof (int));
366:
367: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
368: reg_allocno[i] = -1;
369:
370: /* Initialize the shared-hard-reg mapping
371: from the list of pairs that may share. */
372: reg_may_share = (int *) alloca (max_regno * sizeof (int));
1.1.1.4 root 373: bzero ((char *) reg_may_share, max_regno * sizeof (int));
1.1 root 374: for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
375: {
376: int r1 = REGNO (XEXP (x, 0));
377: int r2 = REGNO (XEXP (XEXP (x, 1), 0));
378: if (r1 > r2)
379: reg_may_share[r1] = r2;
380: else
381: reg_may_share[r2] = r1;
382: }
383:
384: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
385: /* Note that reg_live_length[i] < 0 indicates a "constant" reg
386: that we are supposed to refrain from putting in a hard reg.
387: -2 means do make an allocno but don't allocate it. */
388: if (reg_n_refs[i] != 0 && reg_renumber[i] < 0 && reg_live_length[i] != -1
389: /* Don't allocate pseudos that cross calls,
390: if this function receives a nonlocal goto. */
391: && (! current_function_has_nonlocal_label
392: || reg_n_calls_crossed[i] == 0))
393: {
394: if (reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
395: reg_allocno[i] = reg_allocno[reg_may_share[i]];
396: else
397: reg_allocno[i] = max_allocno++;
398: if (reg_live_length[i] == 0)
399: abort ();
400: }
401: else
402: reg_allocno[i] = -1;
403:
404: allocno_reg = (int *) alloca (max_allocno * sizeof (int));
405: allocno_size = (int *) alloca (max_allocno * sizeof (int));
406: allocno_calls_crossed = (int *) alloca (max_allocno * sizeof (int));
407: allocno_n_refs = (int *) alloca (max_allocno * sizeof (int));
408: allocno_live_length = (int *) alloca (max_allocno * sizeof (int));
1.1.1.4 root 409: bzero ((char *) allocno_size, max_allocno * sizeof (int));
410: bzero ((char *) allocno_calls_crossed, max_allocno * sizeof (int));
411: bzero ((char *) allocno_n_refs, max_allocno * sizeof (int));
412: bzero ((char *) allocno_live_length, max_allocno * sizeof (int));
1.1 root 413:
414: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
415: if (reg_allocno[i] >= 0)
416: {
417: int allocno = reg_allocno[i];
418: allocno_reg[allocno] = i;
419: allocno_size[allocno] = PSEUDO_REGNO_SIZE (i);
420: allocno_calls_crossed[allocno] += reg_n_calls_crossed[i];
421: allocno_n_refs[allocno] += reg_n_refs[i];
422: if (allocno_live_length[allocno] < reg_live_length[i])
423: allocno_live_length[allocno] = reg_live_length[i];
424: }
425:
426: /* Calculate amount of usage of each hard reg by pseudos
427: allocated by local-alloc. This is to see if we want to
428: override it. */
1.1.1.4 root 429: bzero ((char *) local_reg_live_length, sizeof local_reg_live_length);
430: bzero ((char *) local_reg_n_refs, sizeof local_reg_n_refs);
1.1 root 431: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
432: if (reg_allocno[i] < 0 && reg_renumber[i] >= 0)
433: {
434: int regno = reg_renumber[i];
435: int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
436: int j;
437:
438: for (j = regno; j < endregno; j++)
439: {
440: local_reg_n_refs[j] += reg_n_refs[i];
441: local_reg_live_length[j] += reg_live_length[i];
442: }
443: }
444:
445: /* We can't override local-alloc for a reg used not just by local-alloc. */
446: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
447: if (regs_ever_live[i])
448: local_reg_n_refs[i] = 0;
449:
1.1.1.4 root 450: /* Likewise for regs used in a SCRATCH. */
451: for (i = 0; i < scratch_list_length; i++)
452: if (scratch_list[i])
453: {
454: int regno = REGNO (scratch_list[i]);
455: int lim = regno + HARD_REGNO_NREGS (regno, GET_MODE (scratch_list[i]));
456: int j;
457:
458: for (j = regno; j < lim; j++)
459: local_reg_n_refs[j] = 0;
460: }
461:
1.1 root 462: /* Allocate the space for the conflict and preference tables and
463: initialize them. */
464:
465: hard_reg_conflicts
466: = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
1.1.1.4 root 467: bzero ((char *) hard_reg_conflicts, max_allocno * sizeof (HARD_REG_SET));
1.1 root 468:
469: hard_reg_preferences
470: = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
1.1.1.4 root 471: bzero ((char *) hard_reg_preferences, max_allocno * sizeof (HARD_REG_SET));
1.1 root 472:
473: hard_reg_copy_preferences
474: = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
1.1.1.4 root 475: bzero ((char *) hard_reg_copy_preferences,
476: max_allocno * sizeof (HARD_REG_SET));
1.1 root 477:
478: hard_reg_full_preferences
479: = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
1.1.1.4 root 480: bzero ((char *) hard_reg_full_preferences,
481: max_allocno * sizeof (HARD_REG_SET));
1.1 root 482:
483: regs_someone_prefers
484: = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
1.1.1.4 root 485: bzero ((char *) regs_someone_prefers, max_allocno * sizeof (HARD_REG_SET));
1.1 root 486:
487: allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
488:
489: conflicts = (INT_TYPE *) alloca (max_allocno * allocno_row_words
490: * sizeof (INT_TYPE));
1.1.1.4 root 491: bzero ((char *) conflicts,
492: max_allocno * allocno_row_words * sizeof (INT_TYPE));
1.1 root 493:
494: allocnos_live = (INT_TYPE *) alloca (allocno_row_words * sizeof (INT_TYPE));
495:
496: /* If there is work to be done (at least one reg to allocate),
497: perform global conflict analysis and allocate the regs. */
498:
499: if (max_allocno > 0)
500: {
501: /* Scan all the insns and compute the conflicts among allocnos
502: and between allocnos and hard regs. */
503:
504: global_conflicts ();
505:
506: /* Eliminate conflicts between pseudos and eliminable registers. If
507: the register is not eliminated, the pseudo won't really be able to
508: live in the eliminable register, so the conflict doesn't matter.
509: If we do eliminate the register, the conflict will no longer exist.
510: So in either case, we can ignore the conflict. Likewise for
511: preferences. */
512:
513: for (i = 0; i < max_allocno; i++)
514: {
515: AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
516: AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i],
517: eliminable_regset);
518: AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
519: }
520:
521: /* Try to expand the preferences by merging them between allocnos. */
522:
523: expand_preferences ();
524:
525: /* Determine the order to allocate the remaining pseudo registers. */
526:
527: allocno_order = (int *) alloca (max_allocno * sizeof (int));
528: for (i = 0; i < max_allocno; i++)
529: allocno_order[i] = i;
530:
531: /* Default the size to 1, since allocno_compare uses it to divide by.
532: Also convert allocno_live_length of zero to -1. A length of zero
533: can occur when all the registers for that allocno have reg_live_length
534: equal to -2. In this case, we want to make an allocno, but not
535: allocate it. So avoid the divide-by-zero and set it to a low
536: priority. */
537:
538: for (i = 0; i < max_allocno; i++)
539: {
540: if (allocno_size[i] == 0)
541: allocno_size[i] = 1;
542: if (allocno_live_length[i] == 0)
543: allocno_live_length[i] = -1;
544: }
545:
546: qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
547:
548: prune_preferences ();
549:
550: if (file)
551: dump_conflicts (file);
552:
553: /* Try allocating them, one by one, in that order,
554: except for parameters marked with reg_live_length[regno] == -2. */
555:
556: for (i = 0; i < max_allocno; i++)
557: if (reg_live_length[allocno_reg[allocno_order[i]]] >= 0)
558: {
559: /* If we have more than one register class,
560: first try allocating in the class that is cheapest
561: for this pseudo-reg. If that fails, try any reg. */
562: if (N_REG_CLASSES > 1)
563: {
564: find_reg (allocno_order[i], HARD_CONST (0), 0, 0, 0);
565: if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
566: continue;
567: }
568: if (reg_alternate_class (allocno_reg[allocno_order[i]]) != NO_REGS)
569: find_reg (allocno_order[i], HARD_CONST (0), 1, 0, 0);
570: }
571: }
572:
573: /* Do the reloads now while the allocno data still exist, so that we can
574: try to assign new hard regs to any pseudo regs that are spilled. */
575:
576: #if 0 /* We need to eliminate regs even if there is no rtl code,
577: for the sake of debugging information. */
578: if (n_basic_blocks > 0)
579: #endif
580: return reload (get_insns (), 1, file);
581: }
582:
583: /* Sort predicate for ordering the allocnos.
584: Returns -1 (1) if *v1 should be allocated before (after) *v2. */
585:
586: static int
587: allocno_compare (v1, v2)
588: int *v1, *v2;
589: {
590: /* Note that the quotient will never be bigger than
591: the value of floor_log2 times the maximum number of
592: times a register can occur in one insn (surely less than 100).
593: Multiplying this by 10000 can't overflow. */
594: register int pri1
595: = (((double) (floor_log2 (allocno_n_refs[*v1]) * allocno_n_refs[*v1])
1.1.1.4 root 596: / allocno_live_length[*v1])
597: * 10000 * allocno_size[*v1]);
1.1 root 598: register int pri2
599: = (((double) (floor_log2 (allocno_n_refs[*v2]) * allocno_n_refs[*v2])
1.1.1.4 root 600: / allocno_live_length[*v2])
601: * 10000 * allocno_size[*v2]);
1.1 root 602: if (pri2 - pri1)
603: return pri2 - pri1;
604:
605: /* If regs are equally good, sort by allocno,
606: so that the results of qsort leave nothing to chance. */
607: return *v1 - *v2;
608: }
609:
610: /* Scan the rtl code and record all conflicts and register preferences in the
611: conflict matrices and preference tables. */
612:
613: static void
614: global_conflicts ()
615: {
616: register int b, i;
617: register rtx insn;
618: short *block_start_allocnos;
619:
620: /* Make a vector that mark_reg_{store,clobber} will store in. */
621: regs_set = (rtx *) alloca (max_parallel * sizeof (rtx) * 2);
622:
623: block_start_allocnos = (short *) alloca (max_allocno * sizeof (short));
624:
625: for (b = 0; b < n_basic_blocks; b++)
626: {
1.1.1.4 root 627: bzero ((char *) allocnos_live, allocno_row_words * sizeof (INT_TYPE));
1.1 root 628:
629: /* Initialize table of registers currently live
630: to the state at the beginning of this basic block.
631: This also marks the conflicts among them.
632:
633: For pseudo-regs, there is only one bit for each one
634: no matter how many hard regs it occupies.
635: This is ok; we know the size from PSEUDO_REGNO_SIZE.
636: For explicit hard regs, we cannot know the size that way
637: since one hard reg can be used with various sizes.
638: Therefore, we must require that all the hard regs
639: implicitly live as part of a multi-word hard reg
640: are explicitly marked in basic_block_live_at_start. */
641:
642: {
643: register int offset;
644: REGSET_ELT_TYPE bit;
645: register regset old = basic_block_live_at_start[b];
646: int ax = 0;
647:
648: #ifdef HARD_REG_SET
649: hard_regs_live = old[0];
650: #else
651: COPY_HARD_REG_SET (hard_regs_live, old);
652: #endif
653: for (offset = 0, i = 0; offset < regset_size; offset++)
654: if (old[offset] == 0)
655: i += REGSET_ELT_BITS;
656: else
657: for (bit = 1; bit; bit <<= 1, i++)
658: {
659: if (i >= max_regno)
660: break;
661: if (old[offset] & bit)
662: {
663: register int a = reg_allocno[i];
664: if (a >= 0)
665: {
666: SET_ALLOCNO_LIVE (a);
667: block_start_allocnos[ax++] = a;
668: }
669: else if ((a = reg_renumber[i]) >= 0)
670: mark_reg_live_nc (a, PSEUDO_REGNO_MODE (i));
671: }
672: }
673:
674: /* Record that each allocno now live conflicts with each other
675: allocno now live, and with each hard reg now live. */
676:
677: record_conflicts (block_start_allocnos, ax);
678: }
679:
680: insn = basic_block_head[b];
681:
682: /* Scan the code of this basic block, noting which allocnos
683: and hard regs are born or die. When one is born,
684: record a conflict with all others currently live. */
685:
686: while (1)
687: {
688: register RTX_CODE code = GET_CODE (insn);
689: register rtx link;
690:
691: /* Make regs_set an empty set. */
692:
693: n_regs_set = 0;
694:
695: if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
696: {
697:
698: #if 0
1.1.1.4 root 699: int i = 0;
1.1 root 700: for (link = REG_NOTES (insn);
701: link && i < NUM_NO_CONFLICT_PAIRS;
702: link = XEXP (link, 1))
703: if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
704: {
705: no_conflict_pairs[i].allocno1
706: = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
707: no_conflict_pairs[i].allocno2
708: = reg_allocno[REGNO (XEXP (link, 0))];
709: i++;
710: }
711: #endif /* 0 */
712:
713: /* Mark any registers clobbered by INSN as live,
714: so they conflict with the inputs. */
715:
716: note_stores (PATTERN (insn), mark_reg_clobber);
717:
718: /* Mark any registers dead after INSN as dead now. */
719:
720: for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
721: if (REG_NOTE_KIND (link) == REG_DEAD)
722: mark_reg_death (XEXP (link, 0));
723:
724: /* Mark any registers set in INSN as live,
725: and mark them as conflicting with all other live regs.
726: Clobbers are processed again, so they conflict with
727: the registers that are set. */
728:
729: note_stores (PATTERN (insn), mark_reg_store);
730:
731: #ifdef AUTO_INC_DEC
732: for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
733: if (REG_NOTE_KIND (link) == REG_INC)
734: mark_reg_store (XEXP (link, 0), NULL_RTX);
735: #endif
736:
737: /* If INSN has multiple outputs, then any reg that dies here
738: and is used inside of an output
739: must conflict with the other outputs. */
740:
741: if (GET_CODE (PATTERN (insn)) == PARALLEL && !single_set (insn))
742: for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
743: if (REG_NOTE_KIND (link) == REG_DEAD)
744: {
745: int used_in_output = 0;
746: int i;
747: rtx reg = XEXP (link, 0);
748:
749: for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
750: {
751: rtx set = XVECEXP (PATTERN (insn), 0, i);
752: if (GET_CODE (set) == SET
753: && GET_CODE (SET_DEST (set)) != REG
754: && !rtx_equal_p (reg, SET_DEST (set))
755: && reg_overlap_mentioned_p (reg, SET_DEST (set)))
756: used_in_output = 1;
757: }
758: if (used_in_output)
759: mark_reg_conflicts (reg);
760: }
761:
762: /* Mark any registers set in INSN and then never used. */
763:
764: while (n_regs_set > 0)
765: if (find_regno_note (insn, REG_UNUSED,
766: REGNO (regs_set[--n_regs_set])))
767: mark_reg_death (regs_set[n_regs_set]);
768: }
769:
770: if (insn == basic_block_end[b])
771: break;
772: insn = NEXT_INSN (insn);
773: }
774: }
775: }
776: /* Expand the preference information by looking for cases where one allocno
777: dies in an insn that sets an allocno. If those two allocnos don't conflict,
778: merge any preferences between those allocnos. */
779:
780: static void
781: expand_preferences ()
782: {
783: rtx insn;
784: rtx link;
785: rtx set;
786:
787: /* We only try to handle the most common cases here. Most of the cases
788: where this wins are reg-reg copies. */
789:
790: for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
791: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
792: && (set = single_set (insn)) != 0
793: && GET_CODE (SET_DEST (set)) == REG
794: && reg_allocno[REGNO (SET_DEST (set))] >= 0)
795: for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
796: if (REG_NOTE_KIND (link) == REG_DEAD
797: && GET_CODE (XEXP (link, 0)) == REG
798: && reg_allocno[REGNO (XEXP (link, 0))] >= 0
799: && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
800: reg_allocno[REGNO (XEXP (link, 0))])
801: && ! CONFLICTP (reg_allocno[REGNO (XEXP (link, 0))],
802: reg_allocno[REGNO (SET_DEST (set))]))
803: {
804: int a1 = reg_allocno[REGNO (SET_DEST (set))];
805: int a2 = reg_allocno[REGNO (XEXP (link, 0))];
806:
807: if (XEXP (link, 0) == SET_SRC (set))
808: {
809: IOR_HARD_REG_SET (hard_reg_copy_preferences[a1],
810: hard_reg_copy_preferences[a2]);
811: IOR_HARD_REG_SET (hard_reg_copy_preferences[a2],
812: hard_reg_copy_preferences[a1]);
813: }
814:
815: IOR_HARD_REG_SET (hard_reg_preferences[a1],
816: hard_reg_preferences[a2]);
817: IOR_HARD_REG_SET (hard_reg_preferences[a2],
818: hard_reg_preferences[a1]);
819: IOR_HARD_REG_SET (hard_reg_full_preferences[a1],
820: hard_reg_full_preferences[a2]);
821: IOR_HARD_REG_SET (hard_reg_full_preferences[a2],
822: hard_reg_full_preferences[a1]);
823: }
824: }
825:
826: /* Prune the preferences for global registers to exclude registers that cannot
827: be used.
828:
829: Compute `regs_someone_prefers', which is a bitmask of the hard registers
830: that are preferred by conflicting registers of lower priority. If possible,
831: we will avoid using these registers. */
832:
833: static void
834: prune_preferences ()
835: {
836: int i, j;
837: int allocno;
838:
839: /* Scan least most important to most important.
840: For each allocno, remove from preferences registers that cannot be used,
841: either because of conflicts or register type. Then compute all registers
842: preferred by each lower-priority register that conflicts. */
843:
844: for (i = max_allocno - 1; i >= 0; i--)
845: {
846: HARD_REG_SET temp;
847:
848: allocno = allocno_order[i];
849: COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]);
850:
851: if (allocno_calls_crossed[allocno] == 0)
852: IOR_HARD_REG_SET (temp, fixed_reg_set);
853: else
854: IOR_HARD_REG_SET (temp, call_used_reg_set);
855:
856: IOR_COMPL_HARD_REG_SET
857: (temp,
858: reg_class_contents[(int) reg_preferred_class (allocno_reg[allocno])]);
859:
860: AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], temp);
861: AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], temp);
862: AND_COMPL_HARD_REG_SET (hard_reg_full_preferences[allocno], temp);
863:
864: CLEAR_HARD_REG_SET (regs_someone_prefers[allocno]);
865:
866: /* Merge in the preferences of lower-priority registers (they have
867: already been pruned). If we also prefer some of those registers,
868: don't exclude them unless we are of a smaller size (in which case
869: we want to give the lower-priority allocno the first chance for
870: these registers). */
871: for (j = i + 1; j < max_allocno; j++)
872: if (CONFLICTP (allocno, allocno_order[j]))
873: {
874: COPY_HARD_REG_SET (temp,
875: hard_reg_full_preferences[allocno_order[j]]);
876: if (allocno_size[allocno_order[j]] <= allocno_size[allocno])
877: AND_COMPL_HARD_REG_SET (temp,
878: hard_reg_full_preferences[allocno]);
879:
880: IOR_HARD_REG_SET (regs_someone_prefers[allocno], temp);
881: }
882: }
883: }
884:
885: /* Assign a hard register to ALLOCNO; look for one that is the beginning
886: of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
887: The registers marked in PREFREGS are tried first.
888:
889: LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
890: be used for this allocation.
891:
892: If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
893: Otherwise ignore that preferred class and use the alternate class.
894:
895: If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
896: will have to be saved and restored at calls.
897:
898: RETRYING is nonzero if this is called from retry_global_alloc.
899:
900: If we find one, record it in reg_renumber.
901: If not, do nothing. */
902:
903: static void
904: find_reg (allocno, losers, alt_regs_p, accept_call_clobbered, retrying)
905: int allocno;
906: HARD_REG_SET losers;
907: int alt_regs_p;
908: int accept_call_clobbered;
909: int retrying;
910: {
911: register int i, best_reg, pass;
912: #ifdef HARD_REG_SET
913: register /* Declare it register if it's a scalar. */
914: #endif
915: HARD_REG_SET used, used1, used2;
916:
917: enum reg_class class = (alt_regs_p
918: ? reg_alternate_class (allocno_reg[allocno])
919: : reg_preferred_class (allocno_reg[allocno]));
920: enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]);
921:
922: if (accept_call_clobbered)
923: COPY_HARD_REG_SET (used1, call_fixed_reg_set);
924: else if (allocno_calls_crossed[allocno] == 0)
925: COPY_HARD_REG_SET (used1, fixed_reg_set);
926: else
927: COPY_HARD_REG_SET (used1, call_used_reg_set);
928:
929: /* Some registers should not be allocated in global-alloc. */
930: IOR_HARD_REG_SET (used1, no_global_alloc_regs);
931: if (losers)
932: IOR_HARD_REG_SET (used1, losers);
933:
934: IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
935: COPY_HARD_REG_SET (used2, used1);
936:
937: IOR_HARD_REG_SET (used1, hard_reg_conflicts[allocno]);
938:
1.1.1.4 root 939: #ifdef CLASS_CANNOT_CHANGE_SIZE
940: if (reg_changes_size[allocno_reg[allocno]])
941: IOR_HARD_REG_SET (used1,
942: reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]);
943: #endif
944:
1.1 root 945: /* Try each hard reg to see if it fits. Do this in two passes.
946: In the first pass, skip registers that are preferred by some other pseudo
947: to give it a better chance of getting one of those registers. Only if
948: we can't get a register when excluding those do we take one of them.
949: However, we never allocate a register for the first time in pass 0. */
950:
951: COPY_HARD_REG_SET (used, used1);
952: IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
953: IOR_HARD_REG_SET (used, regs_someone_prefers[allocno]);
954:
955: best_reg = -1;
956: for (i = FIRST_PSEUDO_REGISTER, pass = 0;
957: pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
958: pass++)
959: {
960: if (pass == 1)
961: COPY_HARD_REG_SET (used, used1);
962: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
963: {
964: #ifdef REG_ALLOC_ORDER
965: int regno = reg_alloc_order[i];
966: #else
967: int regno = i;
968: #endif
969: if (! TEST_HARD_REG_BIT (used, regno)
970: && HARD_REGNO_MODE_OK (regno, mode))
971: {
972: register int j;
973: register int lim = regno + HARD_REGNO_NREGS (regno, mode);
974: for (j = regno + 1;
975: (j < lim
976: && ! TEST_HARD_REG_BIT (used, j));
977: j++);
978: if (j == lim)
979: {
980: best_reg = regno;
981: break;
982: }
983: #ifndef REG_ALLOC_ORDER
984: i = j; /* Skip starting points we know will lose */
985: #endif
986: }
987: }
988: }
989:
990: /* See if there is a preferred register with the same class as the register
991: we allocated above. Making this restriction prevents register
992: preferencing from creating worse register allocation.
993:
994: Remove from the preferred registers and conflicting registers. Note that
995: additional conflicts may have been added after `prune_preferences' was
996: called.
997:
998: First do this for those register with copy preferences, then all
999: preferred registers. */
1000:
1001: AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], used);
1002: GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences[allocno],
1003: reg_class_contents[(int) NO_REGS], no_copy_prefs);
1004:
1005: if (best_reg >= 0)
1006: {
1007: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1008: if (TEST_HARD_REG_BIT (hard_reg_copy_preferences[allocno], i)
1009: && HARD_REGNO_MODE_OK (i, mode)
1010: && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1011: || reg_class_subset_p (REGNO_REG_CLASS (i),
1012: REGNO_REG_CLASS (best_reg))
1013: || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1014: REGNO_REG_CLASS (i))))
1015: {
1016: register int j;
1017: register int lim = i + HARD_REGNO_NREGS (i, mode);
1018: for (j = i + 1;
1019: (j < lim
1020: && ! TEST_HARD_REG_BIT (used, j)
1021: && (REGNO_REG_CLASS (j)
1022: == REGNO_REG_CLASS (best_reg + (j - i))
1023: || reg_class_subset_p (REGNO_REG_CLASS (j),
1024: REGNO_REG_CLASS (best_reg + (j - i)))
1025: || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1026: REGNO_REG_CLASS (j))));
1027: j++);
1028: if (j == lim)
1029: {
1030: best_reg = i;
1031: goto no_prefs;
1032: }
1033: }
1034: }
1035: no_copy_prefs:
1036:
1037: AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], used);
1038: GO_IF_HARD_REG_SUBSET (hard_reg_preferences[allocno],
1039: reg_class_contents[(int) NO_REGS], no_prefs);
1040:
1041: if (best_reg >= 0)
1042: {
1043: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1044: if (TEST_HARD_REG_BIT (hard_reg_preferences[allocno], i)
1045: && HARD_REGNO_MODE_OK (i, mode)
1046: && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1047: || reg_class_subset_p (REGNO_REG_CLASS (i),
1048: REGNO_REG_CLASS (best_reg))
1049: || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1050: REGNO_REG_CLASS (i))))
1051: {
1052: register int j;
1053: register int lim = i + HARD_REGNO_NREGS (i, mode);
1054: for (j = i + 1;
1055: (j < lim
1056: && ! TEST_HARD_REG_BIT (used, j)
1057: && (REGNO_REG_CLASS (j)
1058: == REGNO_REG_CLASS (best_reg + (j - i))
1059: || reg_class_subset_p (REGNO_REG_CLASS (j),
1060: REGNO_REG_CLASS (best_reg + (j - i)))
1061: || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1062: REGNO_REG_CLASS (j))));
1063: j++);
1064: if (j == lim)
1065: {
1066: best_reg = i;
1067: break;
1068: }
1069: }
1070: }
1071: no_prefs:
1072:
1.1.1.2 root 1073: /* If we haven't succeeded yet, try with caller-saves.
1074: We need not check to see if the current function has nonlocal
1075: labels because we don't put any pseudos that are live over calls in
1076: registers in that case. */
1077:
1.1 root 1078: if (flag_caller_saves && best_reg < 0)
1079: {
1080: /* Did not find a register. If it would be profitable to
1081: allocate a call-clobbered register and save and restore it
1082: around calls, do that. */
1083: if (! accept_call_clobbered
1084: && allocno_calls_crossed[allocno] != 0
1085: && CALLER_SAVE_PROFITABLE (allocno_n_refs[allocno],
1086: allocno_calls_crossed[allocno]))
1087: {
1088: find_reg (allocno, losers, alt_regs_p, 1, retrying);
1089: if (reg_renumber[allocno_reg[allocno]] >= 0)
1090: {
1091: caller_save_needed = 1;
1092: return;
1093: }
1094: }
1095: }
1096:
1097: /* If we haven't succeeded yet,
1098: see if some hard reg that conflicts with us
1099: was utilized poorly by local-alloc.
1100: If so, kick out the regs that were put there by local-alloc
1101: so we can use it instead. */
1102: if (best_reg < 0 && !retrying
1103: /* Let's not bother with multi-reg allocnos. */
1104: && allocno_size[allocno] == 1)
1105: {
1106: /* Count from the end, to find the least-used ones first. */
1107: for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1.1.1.4 root 1108: {
1109: #ifdef REG_ALLOC_ORDER
1110: int regno = reg_alloc_order[i];
1111: #else
1112: int regno = i;
1113: #endif
1114:
1115: if (local_reg_n_refs[regno] != 0
1116: /* Don't use a reg no good for this pseudo. */
1117: && ! TEST_HARD_REG_BIT (used2, regno)
1118: && HARD_REGNO_MODE_OK (regno, mode)
1119: #ifdef CLASS_CANNOT_CHANGE_SIZE
1120: && ! (reg_changes_size[allocno_reg[allocno]]
1121: && (TEST_HARD_REG_BIT
1122: (reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE],
1123: regno)))
1124: #endif
1125: )
1126: {
1127: /* We explicitly evaluate the divide results into temporary
1128: variables so as to avoid excess precision problems that occur
1129: on a i386-unknown-sysv4.2 (unixware) host. */
1130:
1131: double tmp1 = ((double) local_reg_n_refs[regno]
1132: / local_reg_live_length[regno]);
1133: double tmp2 = ((double) allocno_n_refs[allocno]
1134: / allocno_live_length[allocno]);
1135:
1136: if (tmp1 < tmp2)
1.1 root 1137: {
1.1.1.4 root 1138: /* Hard reg REGNO was used less in total by local regs
1139: than it would be used by this one allocno! */
1140: int k;
1141: for (k = 0; k < max_regno; k++)
1142: if (reg_renumber[k] >= 0)
1143: {
1144: int r = reg_renumber[k];
1145: int endregno
1146: = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k));
1.1 root 1147:
1.1.1.4 root 1148: if (regno >= r && regno < endregno)
1149: reg_renumber[k] = -1;
1150: }
1.1 root 1151:
1.1.1.4 root 1152: best_reg = regno;
1153: break;
1154: }
1155: }
1156: }
1.1 root 1157: }
1158:
1159: /* Did we find a register? */
1160:
1161: if (best_reg >= 0)
1162: {
1163: register int lim, j;
1164: HARD_REG_SET this_reg;
1165:
1166: /* Yes. Record it as the hard register of this pseudo-reg. */
1167: reg_renumber[allocno_reg[allocno]] = best_reg;
1168: /* Also of any pseudo-regs that share with it. */
1169: if (reg_may_share[allocno_reg[allocno]])
1170: for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1171: if (reg_allocno[j] == allocno)
1172: reg_renumber[j] = best_reg;
1173:
1174: /* Make a set of the hard regs being allocated. */
1175: CLEAR_HARD_REG_SET (this_reg);
1176: lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1177: for (j = best_reg; j < lim; j++)
1178: {
1179: SET_HARD_REG_BIT (this_reg, j);
1180: SET_HARD_REG_BIT (regs_used_so_far, j);
1181: /* This is no longer a reg used just by local regs. */
1182: local_reg_n_refs[j] = 0;
1183: }
1184: /* For each other pseudo-reg conflicting with this one,
1185: mark it as conflicting with the hard regs this one occupies. */
1186: lim = allocno;
1187: for (j = 0; j < max_allocno; j++)
1188: if (CONFLICTP (lim, j) || CONFLICTP (j, lim))
1189: {
1190: IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
1191: }
1192: }
1193: }
1194:
1195: /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1196: Perhaps it had previously seemed not worth a hard reg,
1197: or perhaps its old hard reg has been commandeered for reloads.
1198: FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1199: they do not appear to be allocated.
1200: If FORBIDDEN_REGS is zero, no regs are forbidden. */
1201:
1202: void
1203: retry_global_alloc (regno, forbidden_regs)
1204: int regno;
1205: HARD_REG_SET forbidden_regs;
1206: {
1207: int allocno = reg_allocno[regno];
1208: if (allocno >= 0)
1209: {
1210: /* If we have more than one register class,
1211: first try allocating in the class that is cheapest
1212: for this pseudo-reg. If that fails, try any reg. */
1213: if (N_REG_CLASSES > 1)
1214: find_reg (allocno, forbidden_regs, 0, 0, 1);
1215: if (reg_renumber[regno] < 0
1216: && reg_alternate_class (regno) != NO_REGS)
1217: find_reg (allocno, forbidden_regs, 1, 0, 1);
1218:
1219: /* If we found a register, modify the RTL for the register to
1220: show the hard register, and mark that register live. */
1221: if (reg_renumber[regno] >= 0)
1222: {
1223: REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1224: mark_home_live (regno);
1225: }
1226: }
1227: }
1228:
1229: /* Record a conflict between register REGNO
1230: and everything currently live.
1231: REGNO must not be a pseudo reg that was allocated
1232: by local_alloc; such numbers must be translated through
1233: reg_renumber before calling here. */
1234:
1235: static void
1236: record_one_conflict (regno)
1237: int regno;
1238: {
1239: register int j;
1240:
1241: if (regno < FIRST_PSEUDO_REGISTER)
1242: /* When a hard register becomes live,
1243: record conflicts with live pseudo regs. */
1244: for (j = 0; j < max_allocno; j++)
1245: {
1246: if (ALLOCNO_LIVE_P (j))
1247: SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
1248: }
1249: else
1250: /* When a pseudo-register becomes live,
1251: record conflicts first with hard regs,
1252: then with other pseudo regs. */
1253: {
1254: register int ialloc = reg_allocno[regno];
1255: register int ialloc_prod = ialloc * allocno_row_words;
1256: IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live);
1257: for (j = allocno_row_words - 1; j >= 0; j--)
1258: {
1259: #if 0
1260: int k;
1261: for (k = 0; k < n_no_conflict_pairs; k++)
1262: if (! ((j == no_conflict_pairs[k].allocno1
1263: && ialloc == no_conflict_pairs[k].allocno2)
1264: ||
1265: (j == no_conflict_pairs[k].allocno2
1266: && ialloc == no_conflict_pairs[k].allocno1)))
1267: #endif /* 0 */
1268: conflicts[ialloc_prod + j] |= allocnos_live[j];
1269: }
1270: }
1271: }
1272:
1273: /* Record all allocnos currently live as conflicting
1274: with each other and with all hard regs currently live.
1275: ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1276: are currently live. Their bits are also flagged in allocnos_live. */
1277:
1278: static void
1279: record_conflicts (allocno_vec, len)
1280: register short *allocno_vec;
1281: register int len;
1282: {
1283: register int allocno;
1284: register int j;
1285: register int ialloc_prod;
1286:
1287: while (--len >= 0)
1288: {
1289: allocno = allocno_vec[len];
1290: ialloc_prod = allocno * allocno_row_words;
1291: IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live);
1292: for (j = allocno_row_words - 1; j >= 0; j--)
1293: conflicts[ialloc_prod + j] |= allocnos_live[j];
1294: }
1295: }
1296:
1297: /* Handle the case where REG is set by the insn being scanned,
1298: during the forward scan to accumulate conflicts.
1299: Store a 1 in regs_live or allocnos_live for this register, record how many
1300: consecutive hardware registers it actually needs,
1301: and record a conflict with all other registers already live.
1302:
1303: Note that even if REG does not remain alive after this insn,
1304: we must mark it here as live, to ensure a conflict between
1305: REG and any other regs set in this insn that really do live.
1306: This is because those other regs could be considered after this.
1307:
1308: REG might actually be something other than a register;
1309: if so, we do nothing.
1310:
1311: SETTER is 0 if this register was modified by an auto-increment (i.e.,
1312: a REG_INC note was found for it).
1313:
1314: CLOBBERs are processed here by calling mark_reg_clobber. */
1315:
1316: static void
1317: mark_reg_store (orig_reg, setter)
1318: rtx orig_reg, setter;
1319: {
1320: register int regno;
1321: register rtx reg = orig_reg;
1322:
1323: /* WORD is which word of a multi-register group is being stored.
1324: For the case where the store is actually into a SUBREG of REG.
1325: Except we don't use it; I believe the entire REG needs to be
1326: made live. */
1327: int word = 0;
1328:
1329: if (GET_CODE (reg) == SUBREG)
1330: {
1331: word = SUBREG_WORD (reg);
1332: reg = SUBREG_REG (reg);
1333: }
1334:
1335: if (GET_CODE (reg) != REG)
1336: return;
1337:
1338: if (setter && GET_CODE (setter) == CLOBBER)
1339: {
1340: /* A clobber of a register should be processed here too. */
1341: mark_reg_clobber (orig_reg, setter);
1342: return;
1343: }
1344:
1345: regs_set[n_regs_set++] = reg;
1346:
1347: if (setter)
1348: set_preference (reg, SET_SRC (setter));
1349:
1350: regno = REGNO (reg);
1351:
1352: if (reg_renumber[regno] >= 0)
1353: regno = reg_renumber[regno] /* + word */;
1354:
1355: /* Either this is one of the max_allocno pseudo regs not allocated,
1356: or it is or has a hardware reg. First handle the pseudo-regs. */
1357: if (regno >= FIRST_PSEUDO_REGISTER)
1358: {
1359: if (reg_allocno[regno] >= 0)
1360: {
1361: SET_ALLOCNO_LIVE (reg_allocno[regno]);
1362: record_one_conflict (regno);
1363: }
1364: }
1365: /* Handle hardware regs (and pseudos allocated to hard regs). */
1366: else if (! fixed_regs[regno])
1367: {
1368: register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1369: while (regno < last)
1370: {
1371: record_one_conflict (regno);
1372: SET_HARD_REG_BIT (hard_regs_live, regno);
1373: regno++;
1374: }
1375: }
1376: }
1377:
1378: /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1379:
1380: static void
1381: mark_reg_clobber (reg, setter)
1382: rtx reg, setter;
1383: {
1384: register int regno;
1385:
1386: /* WORD is which word of a multi-register group is being stored.
1387: For the case where the store is actually into a SUBREG of REG.
1388: Except we don't use it; I believe the entire REG needs to be
1389: made live. */
1390: int word = 0;
1391:
1392: if (GET_CODE (setter) != CLOBBER)
1393: return;
1394:
1395: if (GET_CODE (reg) == SUBREG)
1396: {
1397: word = SUBREG_WORD (reg);
1398: reg = SUBREG_REG (reg);
1399: }
1400:
1401: if (GET_CODE (reg) != REG)
1402: return;
1403:
1404: regs_set[n_regs_set++] = reg;
1405:
1406: regno = REGNO (reg);
1407:
1408: if (reg_renumber[regno] >= 0)
1409: regno = reg_renumber[regno] /* + word */;
1410:
1411: /* Either this is one of the max_allocno pseudo regs not allocated,
1412: or it is or has a hardware reg. First handle the pseudo-regs. */
1413: if (regno >= FIRST_PSEUDO_REGISTER)
1414: {
1415: if (reg_allocno[regno] >= 0)
1416: {
1417: SET_ALLOCNO_LIVE (reg_allocno[regno]);
1418: record_one_conflict (regno);
1419: }
1420: }
1421: /* Handle hardware regs (and pseudos allocated to hard regs). */
1422: else if (! fixed_regs[regno])
1423: {
1424: register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1425: while (regno < last)
1426: {
1427: record_one_conflict (regno);
1428: SET_HARD_REG_BIT (hard_regs_live, regno);
1429: regno++;
1430: }
1431: }
1432: }
1433:
1434: /* Record that REG has conflicts with all the regs currently live.
1435: Do not mark REG itself as live. */
1436:
1437: static void
1438: mark_reg_conflicts (reg)
1439: rtx reg;
1440: {
1441: register int regno;
1442:
1443: if (GET_CODE (reg) == SUBREG)
1444: reg = SUBREG_REG (reg);
1445:
1446: if (GET_CODE (reg) != REG)
1447: return;
1448:
1449: regno = REGNO (reg);
1450:
1451: if (reg_renumber[regno] >= 0)
1452: regno = reg_renumber[regno];
1453:
1454: /* Either this is one of the max_allocno pseudo regs not allocated,
1455: or it is or has a hardware reg. First handle the pseudo-regs. */
1456: if (regno >= FIRST_PSEUDO_REGISTER)
1457: {
1458: if (reg_allocno[regno] >= 0)
1459: record_one_conflict (regno);
1460: }
1461: /* Handle hardware regs (and pseudos allocated to hard regs). */
1462: else if (! fixed_regs[regno])
1463: {
1464: register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1465: while (regno < last)
1466: {
1467: record_one_conflict (regno);
1468: regno++;
1469: }
1470: }
1471: }
1472:
1473: /* Mark REG as being dead (following the insn being scanned now).
1474: Store a 0 in regs_live or allocnos_live for this register. */
1475:
1476: static void
1477: mark_reg_death (reg)
1478: rtx reg;
1479: {
1480: register int regno = REGNO (reg);
1481:
1482: /* For pseudo reg, see if it has been assigned a hardware reg. */
1483: if (reg_renumber[regno] >= 0)
1484: regno = reg_renumber[regno];
1485:
1486: /* Either this is one of the max_allocno pseudo regs not allocated,
1487: or it is a hardware reg. First handle the pseudo-regs. */
1488: if (regno >= FIRST_PSEUDO_REGISTER)
1489: {
1490: if (reg_allocno[regno] >= 0)
1491: CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1492: }
1493: /* Handle hardware regs (and pseudos allocated to hard regs). */
1494: else if (! fixed_regs[regno])
1495: {
1496: /* Pseudo regs already assigned hardware regs are treated
1497: almost the same as explicit hardware regs. */
1498: register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1499: while (regno < last)
1500: {
1501: CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1502: regno++;
1503: }
1504: }
1505: }
1506:
1507: /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1508: for the value stored in it. MODE determines how many consecutive
1509: registers are actually in use. Do not record conflicts;
1510: it is assumed that the caller will do that. */
1511:
1512: static void
1513: mark_reg_live_nc (regno, mode)
1514: register int regno;
1515: enum machine_mode mode;
1516: {
1517: register int last = regno + HARD_REGNO_NREGS (regno, mode);
1518: while (regno < last)
1519: {
1520: SET_HARD_REG_BIT (hard_regs_live, regno);
1521: regno++;
1522: }
1523: }
1524:
1525: /* Try to set a preference for an allocno to a hard register.
1526: We are passed DEST and SRC which are the operands of a SET. It is known
1527: that SRC is a register. If SRC or the first operand of SRC is a register,
1528: try to set a preference. If one of the two is a hard register and the other
1529: is a pseudo-register, mark the preference.
1530:
1531: Note that we are not as aggressive as local-alloc in trying to tie a
1532: pseudo-register to a hard register. */
1533:
1534: static void
1535: set_preference (dest, src)
1536: rtx dest, src;
1537: {
1538: int src_regno, dest_regno;
1539: /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1540: to compensate for subregs in SRC or DEST. */
1541: int offset = 0;
1542: int i;
1543: int copy = 1;
1544:
1545: if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1546: src = XEXP (src, 0), copy = 0;
1547:
1548: /* Get the reg number for both SRC and DEST.
1549: If neither is a reg, give up. */
1550:
1551: if (GET_CODE (src) == REG)
1552: src_regno = REGNO (src);
1553: else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1554: {
1555: src_regno = REGNO (SUBREG_REG (src));
1556: offset += SUBREG_WORD (src);
1557: }
1558: else
1559: return;
1560:
1561: if (GET_CODE (dest) == REG)
1562: dest_regno = REGNO (dest);
1563: else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1564: {
1565: dest_regno = REGNO (SUBREG_REG (dest));
1566: offset -= SUBREG_WORD (dest);
1567: }
1568: else
1569: return;
1570:
1571: /* Convert either or both to hard reg numbers. */
1572:
1573: if (reg_renumber[src_regno] >= 0)
1574: src_regno = reg_renumber[src_regno];
1575:
1576: if (reg_renumber[dest_regno] >= 0)
1577: dest_regno = reg_renumber[dest_regno];
1578:
1579: /* Now if one is a hard reg and the other is a global pseudo
1580: then give the other a preference. */
1581:
1582: if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1583: && reg_allocno[src_regno] >= 0)
1584: {
1585: dest_regno -= offset;
1586: if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER)
1587: {
1588: if (copy)
1589: SET_REGBIT (hard_reg_copy_preferences,
1590: reg_allocno[src_regno], dest_regno);
1591:
1592: SET_REGBIT (hard_reg_preferences,
1593: reg_allocno[src_regno], dest_regno);
1594: for (i = dest_regno;
1595: i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1596: i++)
1597: SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1598: }
1599: }
1600:
1601: if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1602: && reg_allocno[dest_regno] >= 0)
1603: {
1604: src_regno += offset;
1605: if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER)
1606: {
1607: if (copy)
1608: SET_REGBIT (hard_reg_copy_preferences,
1609: reg_allocno[dest_regno], src_regno);
1610:
1611: SET_REGBIT (hard_reg_preferences,
1612: reg_allocno[dest_regno], src_regno);
1613: for (i = src_regno;
1614: i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1615: i++)
1616: SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1617: }
1618: }
1619: }
1620:
1621: /* Indicate that hard register number FROM was eliminated and replaced with
1622: an offset from hard register number TO. The status of hard registers live
1623: at the start of a basic block is updated by replacing a use of FROM with
1624: a use of TO. */
1625:
1626: void
1627: mark_elimination (from, to)
1628: int from, to;
1629: {
1630: int i;
1631:
1632: for (i = 0; i < n_basic_blocks; i++)
1633: if ((basic_block_live_at_start[i][from / REGSET_ELT_BITS]
1634: & ((REGSET_ELT_TYPE) 1 << (from % REGSET_ELT_BITS))) != 0)
1635: {
1636: basic_block_live_at_start[i][from / REGSET_ELT_BITS]
1637: &= ~ ((REGSET_ELT_TYPE) 1 << (from % REGSET_ELT_BITS));
1638: basic_block_live_at_start[i][to / REGSET_ELT_BITS]
1639: |= ((REGSET_ELT_TYPE) 1 << (to % REGSET_ELT_BITS));
1640: }
1641: }
1642:
1643: /* Print debugging trace information if -greg switch is given,
1644: showing the information on which the allocation decisions are based. */
1645:
1646: static void
1647: dump_conflicts (file)
1648: FILE *file;
1649: {
1650: register int i;
1651: register int has_preferences;
1652: fprintf (file, ";; %d regs to allocate:", max_allocno);
1653: for (i = 0; i < max_allocno; i++)
1654: {
1655: int j;
1656: fprintf (file, " %d", allocno_reg[allocno_order[i]]);
1657: for (j = 0; j < max_regno; j++)
1658: if (reg_allocno[j] == allocno_order[i]
1659: && j != allocno_reg[allocno_order[i]])
1660: fprintf (file, "+%d", j);
1661: if (allocno_size[allocno_order[i]] != 1)
1662: fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
1663: }
1664: fprintf (file, "\n");
1665:
1666: for (i = 0; i < max_allocno; i++)
1667: {
1668: register int j;
1669: fprintf (file, ";; %d conflicts:", allocno_reg[i]);
1670: for (j = 0; j < max_allocno; j++)
1671: if (CONFLICTP (i, j) || CONFLICTP (j, i))
1672: fprintf (file, " %d", allocno_reg[j]);
1673: for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1674: if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j))
1675: fprintf (file, " %d", j);
1676: fprintf (file, "\n");
1677:
1678: has_preferences = 0;
1679: for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1680: if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1681: has_preferences = 1;
1682:
1683: if (! has_preferences)
1684: continue;
1685: fprintf (file, ";; %d preferences:", allocno_reg[i]);
1686: for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1687: if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1688: fprintf (file, " %d", j);
1689: fprintf (file, "\n");
1690: }
1691: fprintf (file, "\n");
1692: }
1693:
1694: void
1695: dump_global_regs (file)
1696: FILE *file;
1697: {
1698: register int i, j;
1699:
1700: fprintf (file, ";; Register dispositions:\n");
1701: for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1702: if (reg_renumber[i] >= 0)
1703: {
1704: fprintf (file, "%d in %d ", i, reg_renumber[i]);
1705: if (++j % 6 == 0)
1706: fprintf (file, "\n");
1707: }
1708:
1709: fprintf (file, "\n\n;; Hard regs used: ");
1710: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1711: if (regs_ever_live[i])
1712: fprintf (file, " %d", i);
1713: fprintf (file, "\n\n");
1714: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.