![[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:
1.1.1.2 ! root 1043: /* If we haven't succeeded yet, try with caller-saves.
! 1044: We need not check to see if the current function has nonlocal
! 1045: labels because we don't put any pseudos that are live over calls in
! 1046: registers in that case. */
! 1047:
1.1 root 1048: if (flag_caller_saves && best_reg < 0)
1049: {
1050: /* Did not find a register. If it would be profitable to
1051: allocate a call-clobbered register and save and restore it
1052: around calls, do that. */
1053: if (! accept_call_clobbered
1054: && allocno_calls_crossed[allocno] != 0
1055: && CALLER_SAVE_PROFITABLE (allocno_n_refs[allocno],
1056: allocno_calls_crossed[allocno]))
1057: {
1058: find_reg (allocno, losers, alt_regs_p, 1, retrying);
1059: if (reg_renumber[allocno_reg[allocno]] >= 0)
1060: {
1061: caller_save_needed = 1;
1062: return;
1063: }
1064: }
1065: }
1066:
1067: /* If we haven't succeeded yet,
1068: see if some hard reg that conflicts with us
1069: was utilized poorly by local-alloc.
1070: If so, kick out the regs that were put there by local-alloc
1071: so we can use it instead. */
1072: if (best_reg < 0 && !retrying
1073: /* Let's not bother with multi-reg allocnos. */
1074: && allocno_size[allocno] == 1)
1075: {
1076: /* Count from the end, to find the least-used ones first. */
1077: for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1078: if (local_reg_n_refs[i] != 0
1079: /* Don't use a reg no good for this pseudo. */
1080: && ! TEST_HARD_REG_BIT (used2, i)
1081: && HARD_REGNO_MODE_OK (i, mode)
1082: && ((double) local_reg_n_refs[i] / local_reg_live_length[i]
1083: < ((double) allocno_n_refs[allocno]
1084: / allocno_live_length[allocno])))
1085: {
1086: /* Hard reg I was used less in total by local regs
1087: than it would be used by this one allocno! */
1088: int k;
1089: for (k = 0; k < max_regno; k++)
1090: if (reg_renumber[k] >= 0)
1091: {
1092: int regno = reg_renumber[k];
1093: int endregno
1094: = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (k));
1095:
1096: if (i >= regno && i < endregno)
1097: reg_renumber[k] = -1;
1098: }
1099:
1100: best_reg = i;
1101: break;
1102: }
1103: }
1104:
1105: /* Did we find a register? */
1106:
1107: if (best_reg >= 0)
1108: {
1109: register int lim, j;
1110: HARD_REG_SET this_reg;
1111:
1112: /* Yes. Record it as the hard register of this pseudo-reg. */
1113: reg_renumber[allocno_reg[allocno]] = best_reg;
1114: /* Also of any pseudo-regs that share with it. */
1115: if (reg_may_share[allocno_reg[allocno]])
1116: for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1117: if (reg_allocno[j] == allocno)
1118: reg_renumber[j] = best_reg;
1119:
1120: /* Make a set of the hard regs being allocated. */
1121: CLEAR_HARD_REG_SET (this_reg);
1122: lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1123: for (j = best_reg; j < lim; j++)
1124: {
1125: SET_HARD_REG_BIT (this_reg, j);
1126: SET_HARD_REG_BIT (regs_used_so_far, j);
1127: /* This is no longer a reg used just by local regs. */
1128: local_reg_n_refs[j] = 0;
1129: }
1130: /* For each other pseudo-reg conflicting with this one,
1131: mark it as conflicting with the hard regs this one occupies. */
1132: lim = allocno;
1133: for (j = 0; j < max_allocno; j++)
1134: if (CONFLICTP (lim, j) || CONFLICTP (j, lim))
1135: {
1136: IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
1137: }
1138: }
1139: }
1140:
1141: /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1142: Perhaps it had previously seemed not worth a hard reg,
1143: or perhaps its old hard reg has been commandeered for reloads.
1144: FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1145: they do not appear to be allocated.
1146: If FORBIDDEN_REGS is zero, no regs are forbidden. */
1147:
1148: void
1149: retry_global_alloc (regno, forbidden_regs)
1150: int regno;
1151: HARD_REG_SET forbidden_regs;
1152: {
1153: int allocno = reg_allocno[regno];
1154: if (allocno >= 0)
1155: {
1156: /* If we have more than one register class,
1157: first try allocating in the class that is cheapest
1158: for this pseudo-reg. If that fails, try any reg. */
1159: if (N_REG_CLASSES > 1)
1160: find_reg (allocno, forbidden_regs, 0, 0, 1);
1161: if (reg_renumber[regno] < 0
1162: && reg_alternate_class (regno) != NO_REGS)
1163: find_reg (allocno, forbidden_regs, 1, 0, 1);
1164:
1165: /* If we found a register, modify the RTL for the register to
1166: show the hard register, and mark that register live. */
1167: if (reg_renumber[regno] >= 0)
1168: {
1169: REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1170: mark_home_live (regno);
1171: }
1172: }
1173: }
1174:
1175: /* Record a conflict between register REGNO
1176: and everything currently live.
1177: REGNO must not be a pseudo reg that was allocated
1178: by local_alloc; such numbers must be translated through
1179: reg_renumber before calling here. */
1180:
1181: static void
1182: record_one_conflict (regno)
1183: int regno;
1184: {
1185: register int j;
1186:
1187: if (regno < FIRST_PSEUDO_REGISTER)
1188: /* When a hard register becomes live,
1189: record conflicts with live pseudo regs. */
1190: for (j = 0; j < max_allocno; j++)
1191: {
1192: if (ALLOCNO_LIVE_P (j))
1193: SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
1194: }
1195: else
1196: /* When a pseudo-register becomes live,
1197: record conflicts first with hard regs,
1198: then with other pseudo regs. */
1199: {
1200: register int ialloc = reg_allocno[regno];
1201: register int ialloc_prod = ialloc * allocno_row_words;
1202: IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live);
1203: for (j = allocno_row_words - 1; j >= 0; j--)
1204: {
1205: #if 0
1206: int k;
1207: for (k = 0; k < n_no_conflict_pairs; k++)
1208: if (! ((j == no_conflict_pairs[k].allocno1
1209: && ialloc == no_conflict_pairs[k].allocno2)
1210: ||
1211: (j == no_conflict_pairs[k].allocno2
1212: && ialloc == no_conflict_pairs[k].allocno1)))
1213: #endif /* 0 */
1214: conflicts[ialloc_prod + j] |= allocnos_live[j];
1215: }
1216: }
1217: }
1218:
1219: /* Record all allocnos currently live as conflicting
1220: with each other and with all hard regs currently live.
1221: ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1222: are currently live. Their bits are also flagged in allocnos_live. */
1223:
1224: static void
1225: record_conflicts (allocno_vec, len)
1226: register short *allocno_vec;
1227: register int len;
1228: {
1229: register int allocno;
1230: register int j;
1231: register int ialloc_prod;
1232:
1233: while (--len >= 0)
1234: {
1235: allocno = allocno_vec[len];
1236: ialloc_prod = allocno * allocno_row_words;
1237: IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live);
1238: for (j = allocno_row_words - 1; j >= 0; j--)
1239: conflicts[ialloc_prod + j] |= allocnos_live[j];
1240: }
1241: }
1242:
1243: /* Handle the case where REG is set by the insn being scanned,
1244: during the forward scan to accumulate conflicts.
1245: Store a 1 in regs_live or allocnos_live for this register, record how many
1246: consecutive hardware registers it actually needs,
1247: and record a conflict with all other registers already live.
1248:
1249: Note that even if REG does not remain alive after this insn,
1250: we must mark it here as live, to ensure a conflict between
1251: REG and any other regs set in this insn that really do live.
1252: This is because those other regs could be considered after this.
1253:
1254: REG might actually be something other than a register;
1255: if so, we do nothing.
1256:
1257: SETTER is 0 if this register was modified by an auto-increment (i.e.,
1258: a REG_INC note was found for it).
1259:
1260: CLOBBERs are processed here by calling mark_reg_clobber. */
1261:
1262: static void
1263: mark_reg_store (orig_reg, setter)
1264: rtx orig_reg, setter;
1265: {
1266: register int regno;
1267: register rtx reg = orig_reg;
1268:
1269: /* WORD is which word of a multi-register group is being stored.
1270: For the case where the store is actually into a SUBREG of REG.
1271: Except we don't use it; I believe the entire REG needs to be
1272: made live. */
1273: int word = 0;
1274:
1275: if (GET_CODE (reg) == SUBREG)
1276: {
1277: word = SUBREG_WORD (reg);
1278: reg = SUBREG_REG (reg);
1279: }
1280:
1281: if (GET_CODE (reg) != REG)
1282: return;
1283:
1284: if (setter && GET_CODE (setter) == CLOBBER)
1285: {
1286: /* A clobber of a register should be processed here too. */
1287: mark_reg_clobber (orig_reg, setter);
1288: return;
1289: }
1290:
1291: regs_set[n_regs_set++] = reg;
1292:
1293: if (setter)
1294: set_preference (reg, SET_SRC (setter));
1295:
1296: regno = REGNO (reg);
1297:
1298: if (reg_renumber[regno] >= 0)
1299: regno = reg_renumber[regno] /* + word */;
1300:
1301: /* Either this is one of the max_allocno pseudo regs not allocated,
1302: or it is or has a hardware reg. First handle the pseudo-regs. */
1303: if (regno >= FIRST_PSEUDO_REGISTER)
1304: {
1305: if (reg_allocno[regno] >= 0)
1306: {
1307: SET_ALLOCNO_LIVE (reg_allocno[regno]);
1308: record_one_conflict (regno);
1309: }
1310: }
1311: /* Handle hardware regs (and pseudos allocated to hard regs). */
1312: else if (! fixed_regs[regno])
1313: {
1314: register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1315: while (regno < last)
1316: {
1317: record_one_conflict (regno);
1318: SET_HARD_REG_BIT (hard_regs_live, regno);
1319: regno++;
1320: }
1321: }
1322: }
1323:
1324: /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1325:
1326: static void
1327: mark_reg_clobber (reg, setter)
1328: rtx reg, setter;
1329: {
1330: register int regno;
1331:
1332: /* WORD is which word of a multi-register group is being stored.
1333: For the case where the store is actually into a SUBREG of REG.
1334: Except we don't use it; I believe the entire REG needs to be
1335: made live. */
1336: int word = 0;
1337:
1338: if (GET_CODE (setter) != CLOBBER)
1339: return;
1340:
1341: if (GET_CODE (reg) == SUBREG)
1342: {
1343: word = SUBREG_WORD (reg);
1344: reg = SUBREG_REG (reg);
1345: }
1346:
1347: if (GET_CODE (reg) != REG)
1348: return;
1349:
1350: regs_set[n_regs_set++] = reg;
1351:
1352: regno = REGNO (reg);
1353:
1354: if (reg_renumber[regno] >= 0)
1355: regno = reg_renumber[regno] /* + word */;
1356:
1357: /* Either this is one of the max_allocno pseudo regs not allocated,
1358: or it is or has a hardware reg. First handle the pseudo-regs. */
1359: if (regno >= FIRST_PSEUDO_REGISTER)
1360: {
1361: if (reg_allocno[regno] >= 0)
1362: {
1363: SET_ALLOCNO_LIVE (reg_allocno[regno]);
1364: record_one_conflict (regno);
1365: }
1366: }
1367: /* Handle hardware regs (and pseudos allocated to hard regs). */
1368: else if (! fixed_regs[regno])
1369: {
1370: register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1371: while (regno < last)
1372: {
1373: record_one_conflict (regno);
1374: SET_HARD_REG_BIT (hard_regs_live, regno);
1375: regno++;
1376: }
1377: }
1378: }
1379:
1380: /* Record that REG has conflicts with all the regs currently live.
1381: Do not mark REG itself as live. */
1382:
1383: static void
1384: mark_reg_conflicts (reg)
1385: rtx reg;
1386: {
1387: register int regno;
1388:
1389: if (GET_CODE (reg) == SUBREG)
1390: reg = SUBREG_REG (reg);
1391:
1392: if (GET_CODE (reg) != REG)
1393: return;
1394:
1395: regno = REGNO (reg);
1396:
1397: if (reg_renumber[regno] >= 0)
1398: regno = reg_renumber[regno];
1399:
1400: /* Either this is one of the max_allocno pseudo regs not allocated,
1401: or it is or has a hardware reg. First handle the pseudo-regs. */
1402: if (regno >= FIRST_PSEUDO_REGISTER)
1403: {
1404: if (reg_allocno[regno] >= 0)
1405: record_one_conflict (regno);
1406: }
1407: /* Handle hardware regs (and pseudos allocated to hard regs). */
1408: else if (! fixed_regs[regno])
1409: {
1410: register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1411: while (regno < last)
1412: {
1413: record_one_conflict (regno);
1414: regno++;
1415: }
1416: }
1417: }
1418:
1419: /* Mark REG as being dead (following the insn being scanned now).
1420: Store a 0 in regs_live or allocnos_live for this register. */
1421:
1422: static void
1423: mark_reg_death (reg)
1424: rtx reg;
1425: {
1426: register int regno = REGNO (reg);
1427:
1428: /* For pseudo reg, see if it has been assigned a hardware reg. */
1429: if (reg_renumber[regno] >= 0)
1430: regno = reg_renumber[regno];
1431:
1432: /* Either this is one of the max_allocno pseudo regs not allocated,
1433: or it is a hardware reg. First handle the pseudo-regs. */
1434: if (regno >= FIRST_PSEUDO_REGISTER)
1435: {
1436: if (reg_allocno[regno] >= 0)
1437: CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1438: }
1439: /* Handle hardware regs (and pseudos allocated to hard regs). */
1440: else if (! fixed_regs[regno])
1441: {
1442: /* Pseudo regs already assigned hardware regs are treated
1443: almost the same as explicit hardware regs. */
1444: register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1445: while (regno < last)
1446: {
1447: CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1448: regno++;
1449: }
1450: }
1451: }
1452:
1453: /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1454: for the value stored in it. MODE determines how many consecutive
1455: registers are actually in use. Do not record conflicts;
1456: it is assumed that the caller will do that. */
1457:
1458: static void
1459: mark_reg_live_nc (regno, mode)
1460: register int regno;
1461: enum machine_mode mode;
1462: {
1463: register int last = regno + HARD_REGNO_NREGS (regno, mode);
1464: while (regno < last)
1465: {
1466: SET_HARD_REG_BIT (hard_regs_live, regno);
1467: regno++;
1468: }
1469: }
1470:
1471: /* Try to set a preference for an allocno to a hard register.
1472: We are passed DEST and SRC which are the operands of a SET. It is known
1473: that SRC is a register. If SRC or the first operand of SRC is a register,
1474: try to set a preference. If one of the two is a hard register and the other
1475: is a pseudo-register, mark the preference.
1476:
1477: Note that we are not as aggressive as local-alloc in trying to tie a
1478: pseudo-register to a hard register. */
1479:
1480: static void
1481: set_preference (dest, src)
1482: rtx dest, src;
1483: {
1484: int src_regno, dest_regno;
1485: /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1486: to compensate for subregs in SRC or DEST. */
1487: int offset = 0;
1488: int i;
1489: int copy = 1;
1490:
1491: if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1492: src = XEXP (src, 0), copy = 0;
1493:
1494: /* Get the reg number for both SRC and DEST.
1495: If neither is a reg, give up. */
1496:
1497: if (GET_CODE (src) == REG)
1498: src_regno = REGNO (src);
1499: else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1500: {
1501: src_regno = REGNO (SUBREG_REG (src));
1502: offset += SUBREG_WORD (src);
1503: }
1504: else
1505: return;
1506:
1507: if (GET_CODE (dest) == REG)
1508: dest_regno = REGNO (dest);
1509: else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1510: {
1511: dest_regno = REGNO (SUBREG_REG (dest));
1512: offset -= SUBREG_WORD (dest);
1513: }
1514: else
1515: return;
1516:
1517: /* Convert either or both to hard reg numbers. */
1518:
1519: if (reg_renumber[src_regno] >= 0)
1520: src_regno = reg_renumber[src_regno];
1521:
1522: if (reg_renumber[dest_regno] >= 0)
1523: dest_regno = reg_renumber[dest_regno];
1524:
1525: /* Now if one is a hard reg and the other is a global pseudo
1526: then give the other a preference. */
1527:
1528: if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1529: && reg_allocno[src_regno] >= 0)
1530: {
1531: dest_regno -= offset;
1532: if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER)
1533: {
1534: if (copy)
1535: SET_REGBIT (hard_reg_copy_preferences,
1536: reg_allocno[src_regno], dest_regno);
1537:
1538: SET_REGBIT (hard_reg_preferences,
1539: reg_allocno[src_regno], dest_regno);
1540: for (i = dest_regno;
1541: i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1542: i++)
1543: SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1544: }
1545: }
1546:
1547: if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1548: && reg_allocno[dest_regno] >= 0)
1549: {
1550: src_regno += offset;
1551: if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER)
1552: {
1553: if (copy)
1554: SET_REGBIT (hard_reg_copy_preferences,
1555: reg_allocno[dest_regno], src_regno);
1556:
1557: SET_REGBIT (hard_reg_preferences,
1558: reg_allocno[dest_regno], src_regno);
1559: for (i = src_regno;
1560: i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1561: i++)
1562: SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1563: }
1564: }
1565: }
1566:
1567: /* Indicate that hard register number FROM was eliminated and replaced with
1568: an offset from hard register number TO. The status of hard registers live
1569: at the start of a basic block is updated by replacing a use of FROM with
1570: a use of TO. */
1571:
1572: void
1573: mark_elimination (from, to)
1574: int from, to;
1575: {
1576: int i;
1577:
1578: for (i = 0; i < n_basic_blocks; i++)
1579: if ((basic_block_live_at_start[i][from / REGSET_ELT_BITS]
1580: & ((REGSET_ELT_TYPE) 1 << (from % REGSET_ELT_BITS))) != 0)
1581: {
1582: basic_block_live_at_start[i][from / REGSET_ELT_BITS]
1583: &= ~ ((REGSET_ELT_TYPE) 1 << (from % REGSET_ELT_BITS));
1584: basic_block_live_at_start[i][to / REGSET_ELT_BITS]
1585: |= ((REGSET_ELT_TYPE) 1 << (to % REGSET_ELT_BITS));
1586: }
1587: }
1588:
1589: /* Print debugging trace information if -greg switch is given,
1590: showing the information on which the allocation decisions are based. */
1591:
1592: static void
1593: dump_conflicts (file)
1594: FILE *file;
1595: {
1596: register int i;
1597: register int has_preferences;
1598: fprintf (file, ";; %d regs to allocate:", max_allocno);
1599: for (i = 0; i < max_allocno; i++)
1600: {
1601: int j;
1602: fprintf (file, " %d", allocno_reg[allocno_order[i]]);
1603: for (j = 0; j < max_regno; j++)
1604: if (reg_allocno[j] == allocno_order[i]
1605: && j != allocno_reg[allocno_order[i]])
1606: fprintf (file, "+%d", j);
1607: if (allocno_size[allocno_order[i]] != 1)
1608: fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
1609: }
1610: fprintf (file, "\n");
1611:
1612: for (i = 0; i < max_allocno; i++)
1613: {
1614: register int j;
1615: fprintf (file, ";; %d conflicts:", allocno_reg[i]);
1616: for (j = 0; j < max_allocno; j++)
1617: if (CONFLICTP (i, j) || CONFLICTP (j, i))
1618: fprintf (file, " %d", allocno_reg[j]);
1619: for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1620: if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j))
1621: fprintf (file, " %d", j);
1622: fprintf (file, "\n");
1623:
1624: has_preferences = 0;
1625: for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1626: if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1627: has_preferences = 1;
1628:
1629: if (! has_preferences)
1630: continue;
1631: fprintf (file, ";; %d preferences:", allocno_reg[i]);
1632: for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1633: if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1634: fprintf (file, " %d", j);
1635: fprintf (file, "\n");
1636: }
1637: fprintf (file, "\n");
1638: }
1639:
1640: void
1641: dump_global_regs (file)
1642: FILE *file;
1643: {
1644: register int i, j;
1645:
1646: fprintf (file, ";; Register dispositions:\n");
1647: for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1648: if (reg_renumber[i] >= 0)
1649: {
1650: fprintf (file, "%d in %d ", i, reg_renumber[i]);
1651: if (++j % 6 == 0)
1652: fprintf (file, "\n");
1653: }
1654:
1655: fprintf (file, "\n\n;; Hard regs used: ");
1656: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1657: if (regs_ever_live[i])
1658: fprintf (file, " %d", i);
1659: fprintf (file, "\n\n");
1660: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.