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