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