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