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