![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to global-alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / cmd / gcc|
Return to global-alloc.c CVS log | Up to [Research Unix] / researchv10dc / cmd / gcc |
1.1 root 1: /* Allocate registers for pseudo-registers that span basic blocks.
2: Copyright (C) 1987, 1988 Free Software Foundation, Inc.
3:
4: This file is part of GNU CC.
5:
6: GNU CC is distributed in the hope that it will be useful,
7: but WITHOUT ANY WARRANTY. No author or distributor
8: accepts responsibility to anyone for the consequences of using it
9: or for whether it serves any particular purpose or works at all,
10: unless he says so in writing. Refer to the GNU CC General Public
11: License for full details.
12:
13: Everyone is granted permission to copy, modify and redistribute
14: GNU CC, but only under the conditions described in the
15: GNU CC General Public License. A copy of this license is
16: supposed to have been given to you along with GNU CC so you
17: can know your rights and responsibilities. It should be in a
18: file named COPYING. Among other things, the copyright notice
19: and this notice must be preserved on all copies. */
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:
31: /* This pass of the compiler performs global register allocation.
32: It assigns hard register numbers to all the pseudo registers
33: that were not handled in local_alloc. Assignments are recorded
34: in the vector reg_renumber, not by changing the rtl code.
35: (Such changes are made by final). The entry point is
36: the function global_alloc.
37:
38: After allocation is complete, the reload pass is run as a subroutine
39: of this pass, so that when a pseudo reg loses its hard reg due to
40: spilling it is possible to make a second attempt to find a hard
41: reg for it. The reload pass is independent in other respects
42: and it is run even when stupid register allocation is in use.
43:
44: 1. count the pseudo-registers still needing allocation
45: and assign allocation-numbers (allocnos) to them.
46: Set up tables reg_allocno and allocno_reg to map
47: reg numbers to allocnos and vice versa.
48: max_allocno gets the number of allocnos in use.
49:
50: 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
51: Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
52: for conflicts between allocnos and explicit hard register use
53: (which includes use of pseudo-registers allocated by local_alloc).
54:
55: 3. for each basic block
56: walk forward through the block, recording which
57: unallocated registers and which hardware registers are live.
58: Build the conflict matrix between the unallocated registers
59: and another of unallocated registers versus hardware registers.
60: Someday also record the preferred hardware registers
61: for each unallocated one.
62:
63: 4. Sort a table of the allocnos into order of
64: desirability of the variables.
65:
66: 5. Allocate the variables in that order; each if possible into
67: an preferred register, else into another register. */
68:
69: /* Number of pseudo-registers still requiring allocation
70: (not allocated by local_allocate). */
71:
72: static int max_allocno;
73:
74: /* Indexed by (pseudo) reg number, gives the allocno, or -1
75: for pseudo registers already allocated by local_allocate. */
76:
77: static int *reg_allocno;
78:
79: /* Indexed by allocno, gives the reg number. */
80:
81: static int *allocno_reg;
82:
83: /* A vector of the integers from 0 to max_allocno-1,
84: sorted in the order of first-to-be-allocated first. */
85:
86: static int *allocno_order;
87:
88: /* Indexed by an allocno, gives the number of consecutive
89: hard registers needed by that pseudo reg. */
90:
91: static int *allocno_size;
92:
93: /* Indexed by allocno, gives number of preferred hard reg, or -1 if none. */
94:
95: static int *allocno_preferred_reg;
96:
97: /* max_allocno by max_allocno array of bits,
98: recording whether two allocno's conflict (can't go in the same
99: hardware register).
100:
101: `conflicts' is not symmetric; a conflict between allocno's i and j
102: is recorded either in element i,j or in element j,i. */
103:
104: static int *conflicts;
105:
106: /* Number of ints require to hold max_allocno bits.
107: This is the length of a row in `conflicts'. */
108:
109: static int allocno_row_words;
110:
111: /* Two macros to test or store 1 in an element of `conflicts'. */
112:
113: #define CONFLICTP(I, J) \
114: (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
115: & (1 << ((J) % INT_BITS)))
116:
117: #define SET_CONFLICT(I, J) \
118: (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
119: |= (1 << ((J) % INT_BITS)))
120:
121: /* Set of hard regs currently live (during scan of all insns). */
122:
123: static HARD_REG_SET hard_regs_live;
124:
125: /* Indexed by N, set of hard regs conflicting with allocno N. */
126:
127: static HARD_REG_SET *hard_reg_conflicts;
128:
129: #if 0
130: /* Indexed by N, set of hard regs preferred by allocno N.
131: This was intended to be used to make allocnos go into regs
132: that they are loaded from, when possible, to reduce register shuffling. */
133:
134: static HARD_REG_SET *hard_reg_preferences;
135: #endif
136:
137: /* Test a bit in TABLE, a vector of HARD_REG_SETs,
138: for vector element I, and hard register number J. */
139:
140: #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
141:
142: /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
143:
144: #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
145:
146: /* Bit mask for allocnos live at current point in the scan. */
147:
148: static int *allocnos_live;
149:
150: #define INT_BITS HOST_BITS_PER_INT
151:
152: /* Test, set or clear bit number I in allocnos_live,
153: a bit vector indexed by allocno. */
154:
155: #define ALLOCNO_LIVE_P(I) \
156: (allocnos_live[(I) / INT_BITS] & (1 << ((I) % INT_BITS)))
157:
158: #define SET_ALLOCNO_LIVE(I) \
159: (allocnos_live[(I) / INT_BITS] |= (1 << ((I) % INT_BITS)))
160:
161: #define CLEAR_ALLOCNO_LIVE(I) \
162: (allocnos_live[(I) / INT_BITS] &= ~(1 << ((I) % INT_BITS)))
163:
164: static int allocno_compare ();
165: static void mark_reg_store ();
166: static void mark_reg_live_nc ();
167: static void mark_reg_death ();
168: static void dump_conflicts ();
169: static void find_reg ();
170: static void global_conflicts ();
171: static void record_conflicts ();
172:
173:
174: /* Tables describing and classifying the hardware registers. */
175:
176: /* Perform allocation of pseudo-registers not allocated by local_alloc.
177: FILE is a file to output debugging information on,
178: or zero if such output is not desired. */
179:
180: void
181: global_alloc (file)
182: FILE *file;
183: {
184: register int i;
185:
186: max_allocno = 0;
187:
188: /* Establish mappings from register number to allocation number
189: and vice versa. In the process, count the allocnos. */
190:
191: reg_allocno = (int *) alloca (max_regno * sizeof (int));
192:
193: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
194: reg_allocno[i] = -1;
195:
196: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
197: /* Note that reg_live_length[i] < 0 indicates a "constant" reg
198: that we are supposed to refrain from putting in a hard reg.
199: -2 means do make an allocno but don't allocate it. */
200: if (reg_n_refs[i] != 0 && reg_renumber[i] < 0 && reg_live_length[i] != -1)
201: {
202: reg_allocno[i] = max_allocno++;
203: if (reg_live_length[i] == 0)
204: abort ();
205: }
206: else
207: reg_allocno[i] = -1;
208:
209: allocno_reg = (int *) alloca (max_allocno * sizeof (int));
210: allocno_size = (int *) alloca (max_allocno * sizeof (int));
211: allocno_preferred_reg = (int *) alloca (max_allocno * sizeof (int));
212: bzero (allocno_size, max_allocno * sizeof (int));
213:
214: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
215: if (reg_allocno[i] >= 0)
216: {
217: allocno_reg[reg_allocno[i]] = i;
218: allocno_size[reg_allocno[i]] = PSEUDO_REGNO_SIZE (i);
219: allocno_preferred_reg[reg_allocno[i]] = -1;
220: }
221:
222: /* Allocate the space for the conflict tables. */
223:
224: hard_reg_conflicts = (HARD_REG_SET *)
225: alloca (max_allocno * sizeof (HARD_REG_SET));
226: bzero (hard_reg_conflicts, max_allocno * sizeof (HARD_REG_SET));
227:
228: #if 0
229: hard_reg_preferences = (HARD_REG_SET *)
230: alloca (max_allocno * sizeof (HARD_REG_SET));
231: bzero (hard_reg_preferences, max_allocno * sizeof (HARD_REG_SET));
232: #endif
233:
234: allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
235:
236: conflicts = (int *)
237: alloca (max_allocno * allocno_row_words * sizeof (int));
238: bzero (conflicts, max_allocno * allocno_row_words * sizeof (int));
239:
240: allocnos_live = (int *) alloca (allocno_row_words * sizeof (int));
241:
242: /* If there is work to be done (at least one reg to allocate),
243: perform global conflict analysis and allocate the regs. */
244:
245: if (max_allocno > 0)
246: {
247: /* Scan all the insns and compute the conflicts among allocnos
248: and between allocnos and hard regs. */
249:
250: global_conflicts ();
251:
252: /* Determine the order to allocate the remaining pseudo registers. */
253:
254: allocno_order = (int *) alloca (max_allocno * sizeof (int));
255: for (i = 0; i < max_allocno; i++)
256: allocno_order[i] = i;
257:
258: /* Default the size to 1, since allocno_compare uses it to divide by. */
259:
260: for (i = 0; i < max_allocno; i++)
261: if (allocno_size[i] == 0)
262: allocno_size[i] = 1;
263:
264: qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
265:
266: if (file)
267: dump_conflicts (file);
268:
269: /* Try allocating them, one by one, in that order,
270: except for parameters marked with reg_live_length[regno] == -2. */
271:
272: for (i = 0; i < max_allocno; i++)
273: if (reg_live_length[allocno_reg[allocno_order[i]]] >= 0)
274: {
275: /* If we have a preferred hard register, try that first. */
276: if (allocno_preferred_reg[allocno_order[i]] >= 0)
277: {
278: find_reg (allocno_order[i], 0, 0,
279: allocno_preferred_reg[allocno_order[i]]);
280: if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
281: continue;
282: }
283: /* If we have more than one register class,
284: first try allocating in the class that is cheapest
285: for this pseudo-reg. If that fails, try any reg. */
286: if (N_REG_CLASSES > 1)
287: {
288: find_reg (allocno_order[i], 0, 0, -1);
289: if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
290: continue;
291: }
292: if (!reg_preferred_or_nothing (allocno_reg[allocno_order[i]]))
293: find_reg (allocno_order[i], 0, 1, -1);
294: }
295: }
296:
297: /* Do the reloads now while the allocno data still exist, so that we can
298: try to assign new hard regs to any pseudo regs that are spilled. */
299:
300: if (n_basic_blocks > 0)
301: reload (basic_block_head[0], 1, file);
302: }
303:
304: /* Sort predicate for ordering the allocnos.
305: Returns -1 (1) if *v1 should be allocated before (after) *v2. */
306:
307: static int
308: allocno_compare (v1, v2)
309: int *v1, *v2;
310: {
311: register int r1 = allocno_reg[*v1];
312: register int r2 = allocno_reg[*v2];
313: register double v
314: = ((double) (floor_log2 (reg_n_refs[r1]) * reg_n_refs[r1])
315: / (reg_live_length[r1] * allocno_size[*v1]))
316: - ((double) (floor_log2 (reg_n_refs[r2]) * reg_n_refs[r2])
317: / (reg_live_length[r2] * allocno_size[*v2]));
318: if (v < 0)
319: return 1;
320: if (v > 0)
321: return -1;
322: return 0;
323: }
324:
325: /* Scan the rtl code and record all conflicts in the conflict matrices. */
326:
327: static void
328: global_conflicts ()
329: {
330: register int b, i;
331: register rtx insn;
332: short *block_start_allocnos;
333:
334: block_start_allocnos = (short *) alloca (max_allocno * sizeof (short));
335:
336: for (b = 0; b < n_basic_blocks; b++)
337: {
338: bzero (allocnos_live, allocno_row_words * sizeof (int));
339:
340: /* Initialize table of registers currently live
341: to the state at the beginning of this basic block.
342: This also marks the conflicts among them.
343:
344: For pseudo-regs, there is only one bit for each one
345: no matter how many hard regs it occupies.
346: This is ok; we know the size from PSEUDO_REGNO_SIZE.
347: For explicit hard regs, we cannot know the size that way
348: since one hard reg can be used with various sizes.
349: Therefore, we must require that all the hard regs
350: implicitly live as part of a multi-word hard reg
351: are explicitly marked in basic_block_live_at_start. */
352:
353: {
354: register int offset, bit;
355: register regset old = basic_block_live_at_start[b];
356: int ax = 0;
357:
358: #ifdef HARD_REG_SET
359: hard_regs_live = old[0];
360: #else
361: COPY_HARD_REG_SET (hard_regs_live, old);
362: #endif
363: for (offset = 0, i = 0; offset < regset_size; offset++)
364: if (old[offset] == 0)
365: i += HOST_BITS_PER_INT;
366: else
367: for (bit = 1; bit; bit <<= 1, i++)
368: {
369: if (i >= max_regno)
370: break;
371: if (old[offset] & bit)
372: {
373: register int a = reg_allocno[i];
374: if (a >= 0)
375: {
376: SET_ALLOCNO_LIVE (a);
377: block_start_allocnos[ax++] = a;
378: }
379: else if ((a = reg_renumber[i]) >= 0)
380: mark_reg_live_nc (a, PSEUDO_REGNO_MODE (i));
381: }
382: }
383:
384: /* Record that each allocno now live conflicts with each other
385: allocno now live, and with each hard reg now live. */
386:
387: record_conflicts (block_start_allocnos, ax);
388: }
389:
390: insn = basic_block_head[b];
391:
392: /* Scan the code of this basic block, noting which allocnos
393: and hard regs are born or die. When one is born,
394: record a conflict with all others currently live. */
395:
396: while (1)
397: {
398: register RTX_CODE code = GET_CODE (insn);
399: register rtx link;
400: rtx regs_set[MAX_SETS_PER_INSN + MAX_CLOBBERS_PER_INSN];
401: int n_regs_set = 0;
402:
403: if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
404: {
405: /* Mark any registers dead after INSN as dead now. */
406:
407: for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
408: if (REG_NOTE_KIND (link) == REG_DEAD)
409: mark_reg_death (XEXP (link, 0));
410:
411: /* Mark any registers set in INSN as live,
412: and mark them as conflicting with all other live regs. */
413:
414: if ((GET_CODE (PATTERN (insn)) == SET
415: || GET_CODE (PATTERN (insn)) == CLOBBER)
416: && GET_CODE (SET_DEST (PATTERN (insn))) == REG)
417: {
418: register rtx z = SET_DEST (PATTERN (insn));
419: regs_set[n_regs_set++] = z;
420: mark_reg_store (z);
421: }
422: if ((GET_CODE (PATTERN (insn)) == SET
423: || GET_CODE (PATTERN (insn)) == CLOBBER)
424: && GET_CODE (SET_DEST (PATTERN (insn))) == SUBREG)
425: {
426: register rtx z = SUBREG_REG (SET_DEST (PATTERN (insn)));
427: if (GET_CODE (z) == REG)
428: {
429: regs_set[n_regs_set++] = z;
430: mark_reg_store (z);
431: }
432: }
433: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
434: {
435: register rtx y = PATTERN (insn);
436: for (i = XVECLEN (y, 0) - 1;
437: i >= 0; i--)
438: if (GET_CODE (XVECEXP (y, 0, i)) == SET
439: || GET_CODE (XVECEXP (y, 0, i)) == CLOBBER)
440: {
441: rtx z = SET_DEST (XVECEXP (y, 0, i));
442: if (GET_CODE (z) == REG)
443: {
444: regs_set[n_regs_set++] = z;
445: mark_reg_store (z);
446: }
447: if (GET_CODE (z) == SUBREG
448: && GET_CODE (SUBREG_REG (z)) == REG)
449: {
450: regs_set[n_regs_set++] = SUBREG_REG (z);
451: mark_reg_store (SUBREG_REG (z));
452: }
453: }
454: }
455:
456: /* Mark any registers both set and dead after INSN as dead.
457: This is not redundant!
458: A register may be set and killed in the same insn.
459: It is necessary to mark them as live, above, to get
460: the right conflicts within the insn. */
461:
462: while (n_regs_set > 0)
463: if (find_regno_note (insn, REG_DEAD, REGNO (regs_set[--n_regs_set])))
464: mark_reg_death (regs_set[n_regs_set]);
465:
466: /* Likewise for regs set by incrementation. */
467:
468: for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
469: if (REG_NOTE_KIND (link) == REG_INC
470: && find_regno_note (insn, REG_DEAD, REGNO (XEXP (link, 0))))
471: mark_reg_death (XEXP (link, 0));
472: }
473:
474: if (insn == basic_block_end[b])
475: break;
476: insn = NEXT_INSN (insn);
477: }
478: }
479: }
480:
481: /* Assign a hard register to ALLOCNO; look for one that is the beginning
482: of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
483: If PREFREG is >= 0, try that hard reg first.
484:
485: If ALL_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
486: Otherwise ignore that preferred class.
487:
488: If we find one, record it in reg_renumber.
489: If not, do nothing. */
490:
491: static void
492: find_reg (allocno, losers, all_regs_p, prefreg)
493: int allocno;
494: register short *losers;
495: int all_regs_p;
496: int prefreg;
497: {
498: register int i;
499: #ifdef HARD_REG_SET
500: register /* Declare it register if it's a scalar. */
501: #endif
502: HARD_REG_SET used;
503:
504: enum reg_class class
505: = all_regs_p ? GENERAL_REGS : reg_preferred_class (allocno_reg[allocno]);
506: enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]);
507:
508: COPY_HARD_REG_SET (used,
509: (reg_crosses_call[allocno_reg[allocno]]
510: ? call_used_reg_set : fixed_reg_set));
511:
512: IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]);
513: IOR_HARD_REG_SET (used, hard_reg_conflicts[allocno]);
514: if (frame_pointer_needed)
515: SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM);
516:
517: /* If a preferred register was specified, try it first. */
518:
519: i = -1;
520: if (prefreg >= 0)
521: if (! TEST_HARD_REG_BIT (used, prefreg)
522: && (losers == 0 || losers[prefreg] < 0)
523: && HARD_REGNO_MODE_OK (prefreg, mode))
524: {
525: register int j;
526: register int lim = prefreg + HARD_REGNO_NREGS (prefreg, mode);
527: for (j = prefreg + 1;
528: (j < lim
529: && ! TEST_HARD_REG_BIT (used, j)
530: && (losers == 0 || losers[j] < 0));
531: j++);
532: if (j == lim)
533: i = prefreg;
534: }
535:
536: /* Otherwise try each hard reg to see if it fits. */
537:
538: if (i < 0)
539: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
540: if (! TEST_HARD_REG_BIT (used, i)
541: && (losers == 0 || losers[i] < 0)
542: && HARD_REGNO_MODE_OK (i, mode))
543: {
544: register int j;
545: register int lim = i + HARD_REGNO_NREGS (i, mode);
546: for (j = i + 1;
547: (j < lim
548: && ! TEST_HARD_REG_BIT (used, j)
549: && (losers == 0 || losers[j] < 0));
550: j++);
551: if (j == lim)
552: break;
553: i = j; /* Skip starting points we know will lose */
554: }
555:
556: /* Did we find a register? */
557:
558: if (i < FIRST_PSEUDO_REGISTER)
559: {
560: register int lim, j;
561: HARD_REG_SET this_reg;
562:
563: /* Yes. Record it as the hard register of this pseudo-reg. */
564: reg_renumber[allocno_reg[allocno]] = i;
565: /* For each other pseudo-reg conflicting with this one,
566: mark it as conflicting with the hard regs this one occupies. */
567: CLEAR_HARD_REG_SET (this_reg);
568: lim = i + HARD_REGNO_NREGS (i, mode);
569: for (j = i; j < lim; j++)
570: SET_HARD_REG_BIT (this_reg, j);
571: lim = allocno;
572: for (j = 0; j < max_allocno; j++)
573: if (CONFLICTP (lim, j) || CONFLICTP (j, lim))
574: {
575: IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
576: }
577: }
578: }
579:
580: /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
581: Perhaps it had previously seemed not worth a hard reg,
582: or perhaps its old hard reg has been commandeered for reloads.
583: FORBIDDEN_REGS is a vector that indicates certain hard regs
584: that may not be used, even if they do not appear to be allocated.
585: A nonnegative element means the corresponding hard reg is forbidden.
586: If FORBIDDEN_REGS is zero, no regs are forbidden. */
587:
588: void
589: retry_global_alloc (regno, forbidden_regs)
590: int regno;
591: short *forbidden_regs;
592: {
593: int allocno = reg_allocno[regno];
594: if (allocno >= 0)
595: {
596: /* If we have more than one register class,
597: first try allocating in the class that is cheapest
598: for this pseudo-reg. If that fails, try any reg. */
599: if (N_REG_CLASSES > 1)
600: find_reg (allocno, forbidden_regs, 0, -1);
601: if (reg_renumber[regno] < 0
602: && !reg_preferred_or_nothing (regno))
603: find_reg (allocno, forbidden_regs, 1, -1);
604: }
605: }
606:
607: /* Called from reload pass to see if current function's pseudo regs
608: require a frame pointer to be allocated and set up.
609:
610: Return 1 if so, 0 otherwise.
611: We may alter the hard-reg allocation of the pseudo regs
612: in order to make the frame pointer unnecessary.
613: However, if the value is 1, nothing has been altered.
614:
615: Args grant access to some tables used in reload1.c.
616: See there for info on them. */
617:
618: int
619: check_frame_pointer_required (reg_equiv_constant, reg_equiv_mem)
620: rtx *reg_equiv_constant, *reg_equiv_mem;
621: {
622: register int i;
623: HARD_REG_SET *old_hard_reg_conflicts;
624: short *old_reg_renumber;
625: char old_regs_ever_live[FIRST_PSEUDO_REGISTER];
626:
627: /* If any pseudo reg has no hard reg and no equivalent,
628: we must have a frame pointer. */
629:
630: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
631: if (reg_renumber[i] < 0 && reg_equiv_mem[i] == 0
632: && reg_equiv_constant[i] == 0 && reg_n_refs[i] > 0)
633: return 1;
634:
635: /* If we might not need a frame pointer,
636: try finding a hard reg for any pseudo that has a memory equivalent.
637: That is because the memory equivalent probably refers to a frame
638: pointer. */
639:
640: old_reg_renumber = (short *) alloca (max_regno * sizeof (short));
641: old_hard_reg_conflicts = (HARD_REG_SET *)
642: alloca (max_allocno * sizeof (HARD_REG_SET));
643:
644: bcopy (reg_renumber, old_reg_renumber, max_regno * sizeof (short));
645: bcopy (hard_reg_conflicts, old_hard_reg_conflicts,
646: max_allocno * sizeof (HARD_REG_SET));
647: bcopy (regs_ever_live, old_regs_ever_live, sizeof regs_ever_live);
648:
649: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
650: if (reg_renumber[i] < 0 && reg_equiv_mem[i] != 0)
651: {
652: retry_global_alloc (i, 0);
653: /* If we can't find a hard reg for ALL of them,
654: or if a previously unneeded hard reg is used that requires saving,
655: we fail: set all those pseudos back as they were. */
656: if (reg_renumber[i] < 0
657: || (! old_regs_ever_live[reg_renumber[i]]
658: && ! call_used_regs[reg_renumber[i]]))
659: {
660: bcopy (old_reg_renumber, reg_renumber,
661: max_regno * sizeof (short));
662: bcopy (old_hard_reg_conflicts, hard_reg_conflicts,
663: max_allocno * sizeof (HARD_REG_SET));
664: bcopy (old_regs_ever_live, regs_ever_live, sizeof regs_ever_live);
665: return 1;
666: }
667: mark_home_live (i);
668: }
669:
670: return 0;
671: }
672:
673: /* Record a conflict between register REGNO
674: and everything currently live.
675: REGNO must not be a pseudo reg that was allocated
676: by local_alloc; such numbers must be translated through
677: reg_renumber before calling here. */
678:
679: static void
680: record_one_conflict (regno)
681: int regno;
682: {
683: register int j;
684:
685: if (regno < FIRST_PSEUDO_REGISTER)
686: /* When a hard register becomes live,
687: record conflicts with live pseudo regs. */
688: for (j = 0; j < max_allocno; j++)
689: {
690: if (ALLOCNO_LIVE_P (j))
691: SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
692: }
693: else
694: /* When a pseudo-register becomes live,
695: record conflicts first with hard regs,
696: then with other pseudo regs. */
697: {
698: register int ialloc = reg_allocno[regno];
699: register int ialloc_prod = ialloc * allocno_row_words;
700: IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live);
701: for (j = allocno_row_words - 1; j >= 0; j--)
702: conflicts[ialloc_prod + j] |= allocnos_live[j];
703: }
704: }
705:
706: /* Record all allocnos currently live as conflicting
707: with each other and with all hard regs currently live.
708: ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
709: are currently live. Their bits are also flagged in allocnos_live. */
710:
711: static void
712: record_conflicts (allocno_vec, len)
713: register short *allocno_vec;
714: register int len;
715: {
716: register int allocno;
717: register int j;
718: register int ialloc_prod;
719:
720: while (--len >= 0)
721: {
722: allocno = allocno_vec[len];
723: ialloc_prod = allocno * allocno_row_words;
724: IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live);
725: for (j = allocno_row_words - 1; j >= 0; j--)
726: conflicts[ialloc_prod + j] |= allocnos_live[j];
727: }
728: }
729:
730: /* Handle the case where REG is set by the insn being scanned,
731: during the forward scan to accumulate conflicts.
732: Store a 1 in regs_live or allocnos_live for this register, record how many
733: consecutive hardware registers it actually needs,
734: and record a conflict with all other registers already live.
735:
736: Note that even if REG does not remain alive after this insn,
737: we must mark it here as live, to ensure a conflict between
738: REG and any other regs set in this insn that really do live.
739: This is because those other regs could be considered after this. */
740:
741: static void
742: mark_reg_store (reg)
743: rtx reg;
744: {
745: register int regno = REGNO (reg);
746:
747: if (reg_renumber[regno] >= 0)
748: regno = reg_renumber[regno];
749:
750: /* Either this is one of the max_allocno pseudo regs not allocated,
751: or it is or has a hardware reg. First handle the pseudo-regs. */
752: if (regno >= FIRST_PSEUDO_REGISTER)
753: {
754: if (reg_allocno[regno] >= 0)
755: {
756: SET_ALLOCNO_LIVE (reg_allocno[regno]);
757: record_one_conflict (regno);
758: }
759: }
760: /* Handle hardware regs (and pseudos allocated to hard regs). */
761: else if (! fixed_regs[regno])
762: {
763: register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
764: while (regno < last)
765: {
766: record_one_conflict (regno);
767: SET_HARD_REG_BIT (hard_regs_live, regno);
768: regno++;
769: }
770: }
771: }
772:
773: /* Mark REG as being dead (following the insn being scanned now).
774: Store a 0 in regs_live or allocnos_live for this register. */
775:
776: static void
777: mark_reg_death (reg)
778: rtx reg;
779: {
780: register int regno = REGNO (reg);
781:
782: /* For pseudo reg, see if it has been assigned a hardware reg. */
783: if (reg_renumber[regno] >= 0)
784: regno = reg_renumber[regno];
785:
786: /* Either this is one of the max_allocno pseudo regs not allocated,
787: or it is a hardware reg. First handle the pseudo-regs. */
788: if (regno >= FIRST_PSEUDO_REGISTER)
789: {
790: if (reg_allocno[regno] >= 0)
791: CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
792: }
793: /* Handle hardware regs (and pseudos allocated to hard regs). */
794: else if (! fixed_regs[regno])
795: {
796: /* Pseudo regs already assigned hardware regs are treated
797: almost the same as explicit hardware regs. */
798: register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
799: while (regno < last)
800: {
801: CLEAR_HARD_REG_BIT (hard_regs_live, regno);
802: regno++;
803: }
804: }
805: }
806:
807: /* Mark hard reg REGNO as currently live, assuming machine mode MODE
808: for the value stored in it. MODE determines how many consecutive
809: registers are actually in use. Do not record conflicts;
810: it is assumed that the caller will do that. */
811:
812: static void
813: mark_reg_live_nc (regno, mode)
814: register int regno;
815: enum machine_mode mode;
816: {
817: register int last = regno + HARD_REGNO_NREGS (regno, mode);
818: while (regno < last)
819: {
820: SET_HARD_REG_BIT (hard_regs_live, regno);
821: regno++;
822: }
823: }
824:
825: /* Print debugging trace information if -greg switch is given,
826: showing the information on which the allocation decisions are based. */
827:
828: static void
829: dump_conflicts (file)
830: FILE *file;
831: {
832: register int i;
833: fprintf (file, ";; %d regs to allocate:", max_allocno);
834: for (i = 0; i < max_allocno; i++)
835: {
836: fprintf (file, " %d", allocno_reg[allocno_order[i]]);
837: if (allocno_size[allocno_order[i]] != 1)
838: fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
839: }
840: fprintf (file, "\n");
841:
842: for (i = 0; i < max_allocno; i++)
843: {
844: register int j;
845: fprintf (file, ";; %d conflicts:", allocno_reg[i],
846: reg_renumber[allocno_reg[i]]);
847: for (j = 0; j < max_allocno; j++)
848: if (CONFLICTP (i, j) || CONFLICTP (j, i))
849: fprintf (file, " %d", allocno_reg[j]);
850: for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
851: if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j))
852: fprintf (file, " %d", j);
853: fprintf (file, "\n");
854: }
855: fprintf (file, "\n");
856: }
857:
858: void
859: dump_global_regs (file)
860: FILE *file;
861: {
862: register int i;
863:
864: fprintf (file, ";; Register dispositions:");
865: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
866: {
867: if (reg_renumber[i] >= 0)
868: fprintf (file, " %d in %d ", i, reg_renumber[i]);
869: }
870:
871: fprintf (file, "\n\n;; Hard regs used: ");
872: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
873: if (regs_ever_live[i])
874: fprintf (file, " %d", i);
875: fprintf (file, "\n\n");
876: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.