1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987-1991 Free Software Foundation, Inc.
4 This file is part of GNU CC.
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)
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.
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. */
25 #include "basic-block.h"
26 #include "hard-reg-set.h"
28 #include "insn-config.h"
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.
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.
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.
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).
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.
63 4. Sort a table of the allocnos into order of
64 desirability of the variables.
66 5. Allocate the variables in that order; each if possible into
67 a preferred register, else into another register. */
69 /* Number of pseudo-registers still requiring allocation
70 (not allocated by local_allocate). */
72 static int max_allocno
;
74 /* Indexed by (pseudo) reg number, gives the allocno, or -1
75 for pseudo registers already allocated by local_allocate. */
77 static int *reg_allocno
;
79 /* Indexed by allocno, gives the reg number. */
81 static int *allocno_reg
;
83 /* A vector of the integers from 0 to max_allocno-1,
84 sorted in the order of first-to-be-allocated first. */
86 static int *allocno_order
;
88 /* Indexed by an allocno, gives the number of consecutive
89 hard registers needed by that pseudo reg. */
91 static int *allocno_size
;
93 /* Indexed by (pseudo) reg number, gives the number of another
94 lower-numbered pseudo reg which can share a hard reg with this peudo
95 *even if the two pseudos would otherwise appear to conflict*. */
97 static int *reg_may_share
;
99 /* max_allocno by max_allocno array of bits,
100 recording whether two allocno's conflict (can't go in the same
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. */
106 static int *conflicts
;
108 /* Number of ints require to hold max_allocno bits.
109 This is the length of a row in `conflicts'. */
111 static int allocno_row_words
;
113 /* Two macros to test or store 1 in an element of `conflicts'. */
115 #define CONFLICTP(I, J) \
116 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
117 & (1 << ((J) % INT_BITS)))
119 #define SET_CONFLICT(I, J) \
120 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
121 |= (1 << ((J) % INT_BITS)))
123 /* Set of hard regs currently live (during scan of all insns). */
125 static HARD_REG_SET hard_regs_live
;
127 /* Indexed by N, set of hard regs conflicting with allocno N. */
129 static HARD_REG_SET
*hard_reg_conflicts
;
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. */
135 static HARD_REG_SET
*hard_reg_preferences
;
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. */
142 static HARD_REG_SET
*hard_reg_copy_preferences
;
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. */
148 static HARD_REG_SET
*hard_reg_full_preferences
;
150 /* Indexed by N, set of hard registers that some later allocno has a
153 static HARD_REG_SET
*regs_someone_prefers
;
155 /* Set of registers that global-alloc isn't supposed to use. */
157 static HARD_REG_SET no_global_alloc_regs
;
159 /* Set of registers used so far. */
161 static HARD_REG_SET regs_used_so_far
;
163 /* Number of calls crossed by each allocno. */
165 static int *allocno_calls_crossed
;
167 /* Number of refs (weighted) to each allocno. */
169 static int *allocno_n_refs
;
171 /* Guess at live length of each allocno.
172 This is actually the max of the live lengths of the regs. */
174 static int *allocno_live_length
;
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. */
179 static int local_reg_n_refs
[FIRST_PSEUDO_REGISTER
];
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. */
184 static int local_reg_live_length
[FIRST_PSEUDO_REGISTER
];
186 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
187 for vector element I, and hard register number J. */
189 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
191 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
193 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
195 /* Bit mask for allocnos live at current point in the scan. */
197 static int *allocnos_live
;
199 #define INT_BITS HOST_BITS_PER_INT
201 /* Test, set or clear bit number I in allocnos_live,
202 a bit vector indexed by allocno. */
204 #define ALLOCNO_LIVE_P(I) \
205 (allocnos_live[(I) / INT_BITS] & (1 << ((I) % INT_BITS)))
207 #define SET_ALLOCNO_LIVE(I) \
208 (allocnos_live[(I) / INT_BITS] |= (1 << ((I) % INT_BITS)))
210 #define CLEAR_ALLOCNO_LIVE(I) \
211 (allocnos_live[(I) / INT_BITS] &= ~(1 << ((I) % INT_BITS)))
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.
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. */
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
];
238 /* Record all regs that are set in any one insn.
239 Communication from mark_reg_{store,clobber} and global_conflicts. */
241 static rtx
*regs_set
;
242 static int n_regs_set
;
244 /* All register that can be eliminated. */
246 static HARD_REG_SET eliminable_regset
;
248 static int allocno_compare ();
249 static void mark_reg_store ();
250 static void mark_reg_clobber ();
251 static void mark_reg_live_nc ();
252 static void mark_reg_death ();
253 static void dump_conflicts ();
254 void dump_global_regs ();
255 static void find_reg ();
256 static void global_conflicts ();
257 static void expand_preferences ();
258 static void prune_preferences ();
259 static void record_conflicts ();
260 static void set_preference ();
262 /* Perform allocation of pseudo-registers not allocated by local_alloc.
263 FILE is a file to output debugging information on,
264 or zero if such output is not desired. */
270 #ifdef ELIMINABLE_REGS
271 static struct {int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
278 /* A machine may have certain hard registers that
279 are safe to use only within a basic block. */
281 CLEAR_HARD_REG_SET (no_global_alloc_regs
);
282 #ifdef OVERLAPPING_REGNO_P
283 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
284 if (OVERLAPPING_REGNO_P (i
))
285 SET_HARD_REG_BIT (no_global_alloc_regs
, i
);
288 /* Build the regset of all eliminable registers and show we can't use those
289 that we already know won't be eliminated. */
290 #ifdef ELIMINABLE_REGS
291 for (i
= 0; i
< sizeof eliminables
/ sizeof eliminables
[0]; i
++)
293 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
295 if (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
296 || (eliminables
[i
].from
== FRAME_POINTER_REGNUM
297 && (! flag_omit_frame_pointer
|| FRAME_POINTER_REQUIRED
)))
298 SET_HARD_REG_BIT (no_global_alloc_regs
, eliminables
[i
].from
);
301 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
303 /* If we know we will definitely not be eliminating the frame pointer,
304 don't allocate it. */
305 if (! flag_omit_frame_pointer
|| FRAME_POINTER_REQUIRED
)
306 SET_HARD_REG_BIT (no_global_alloc_regs
, FRAME_POINTER_REGNUM
);
309 /* Track which registers have already been used. Start with registers
310 explicitly in the rtl, then registers allocated by local register
313 We consider registers that do not have to be saved over calls as if
314 they were already used since there is no cost in using them. */
316 CLEAR_HARD_REG_SET (regs_used_so_far
);
317 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
318 if (regs_ever_live
[i
] || call_used_regs
[i
])
319 SET_HARD_REG_BIT (regs_used_so_far
, i
);
321 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
322 if (reg_renumber
[i
] >= 0)
323 SET_HARD_REG_BIT (regs_used_so_far
, reg_renumber
[i
]);
325 /* Establish mappings from register number to allocation number
326 and vice versa. In the process, count the allocnos. */
328 reg_allocno
= (int *) alloca (max_regno
* sizeof (int));
330 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
333 /* Initialize the shared-hard-reg mapping
334 from the list of pairs that may share. */
335 reg_may_share
= (int *) alloca (max_regno
* sizeof (int));
336 bzero (reg_may_share
, max_regno
* sizeof (int));
337 for (x
= regs_may_share
; x
; x
= XEXP (XEXP (x
, 1), 1))
339 int r1
= REGNO (XEXP (x
, 0));
340 int r2
= REGNO (XEXP (XEXP (x
, 1), 0));
342 reg_may_share
[r1
] = r2
;
344 reg_may_share
[r2
] = r1
;
347 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
348 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
349 that we are supposed to refrain from putting in a hard reg.
350 -2 means do make an allocno but don't allocate it. */
351 if (reg_n_refs
[i
] != 0 && reg_renumber
[i
] < 0 && reg_live_length
[i
] != -1
352 /* Don't allocate pseudos that cross calls,
353 if this function receives a nonlocal goto. */
354 && (! current_function_has_nonlocal_label
355 || reg_n_calls_crossed
[i
] == 0))
357 if (reg_may_share
[i
] && reg_allocno
[reg_may_share
[i
]] >= 0)
358 reg_allocno
[i
] = reg_allocno
[reg_may_share
[i
]];
360 reg_allocno
[i
] = max_allocno
++;
361 if (reg_live_length
[i
] == 0)
367 allocno_reg
= (int *) alloca (max_allocno
* sizeof (int));
368 allocno_size
= (int *) alloca (max_allocno
* sizeof (int));
369 allocno_calls_crossed
= (int *) alloca (max_allocno
* sizeof (int));
370 allocno_n_refs
= (int *) alloca (max_allocno
* sizeof (int));
371 allocno_live_length
= (int *) alloca (max_allocno
* sizeof (int));
372 bzero (allocno_size
, max_allocno
* sizeof (int));
373 bzero (allocno_calls_crossed
, max_allocno
* sizeof (int));
374 bzero (allocno_n_refs
, max_allocno
* sizeof (int));
375 bzero (allocno_live_length
, max_allocno
* sizeof (int));
377 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
378 if (reg_allocno
[i
] >= 0)
380 int allocno
= reg_allocno
[i
];
381 allocno_reg
[allocno
] = i
;
382 allocno_size
[allocno
] = PSEUDO_REGNO_SIZE (i
);
383 allocno_calls_crossed
[allocno
] += reg_n_calls_crossed
[i
];
384 allocno_n_refs
[allocno
] += reg_n_refs
[i
];
385 if (allocno_live_length
[allocno
] < reg_live_length
[i
])
386 allocno_live_length
[allocno
] = reg_live_length
[i
];
389 /* Calculate amount of usage of each hard reg by pseudos
390 allocated by local-alloc. This is to see if we want to
392 bzero (local_reg_live_length
, sizeof local_reg_live_length
);
393 bzero (local_reg_n_refs
, sizeof local_reg_n_refs
);
394 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
395 if (reg_allocno
[i
] < 0 && reg_renumber
[i
] >= 0)
397 local_reg_n_refs
[reg_renumber
[i
]] += reg_n_refs
[i
];
398 local_reg_live_length
[reg_renumber
[i
]] += reg_live_length
[i
];
400 /* We can't override local-alloc for a reg used not just by local-alloc. */
401 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
402 if (regs_ever_live
[i
])
403 local_reg_n_refs
[i
] = 0;
405 /* Allocate the space for the conflict and preference tables and
409 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
410 bzero (hard_reg_conflicts
, max_allocno
* sizeof (HARD_REG_SET
));
413 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
414 bzero (hard_reg_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
416 hard_reg_copy_preferences
417 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
418 bzero (hard_reg_copy_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
420 hard_reg_full_preferences
421 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
422 bzero (hard_reg_full_preferences
, max_allocno
* sizeof (HARD_REG_SET
));
425 = (HARD_REG_SET
*) alloca (max_allocno
* sizeof (HARD_REG_SET
));
426 bzero (regs_someone_prefers
, max_allocno
* sizeof (HARD_REG_SET
));
428 allocno_row_words
= (max_allocno
+ INT_BITS
- 1) / INT_BITS
;
430 conflicts
= (int *) alloca (max_allocno
* allocno_row_words
* sizeof (int));
431 bzero (conflicts
, max_allocno
* allocno_row_words
* sizeof (int));
433 allocnos_live
= (int *) alloca (allocno_row_words
* sizeof (int));
435 /* If there is work to be done (at least one reg to allocate),
436 perform global conflict analysis and allocate the regs. */
440 /* Scan all the insns and compute the conflicts among allocnos
441 and between allocnos and hard regs. */
445 /* Eliminate conflicts between pseudos and eliminable registers. If
446 the register is not eliminated, the pseudo won't really be able to
447 live in the eliminable register, so the conflict doesn't matter.
448 If we do eliminate the register, the conflict will no longer exist.
449 So in either case, we can ignore the conflict. Likewise for
452 for (i
= 0; i
< max_allocno
; i
++)
454 AND_COMPL_HARD_REG_SET (hard_reg_conflicts
[i
], eliminable_regset
);
455 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[i
],
457 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[i
], eliminable_regset
);
460 /* Try to expand the preferences by merging them between allocnos. */
462 expand_preferences ();
464 /* Determine the order to allocate the remaining pseudo registers. */
466 allocno_order
= (int *) alloca (max_allocno
* sizeof (int));
467 for (i
= 0; i
< max_allocno
; i
++)
468 allocno_order
[i
] = i
;
470 /* Default the size to 1, since allocno_compare uses it to divide by.
471 Also convert allocno_live_length of zero to -1. A length of zero
472 can occur when all the registers for that allocno have reg_live_length
473 equal to -2. In this case, we want to make an allocno, but not
474 allocate it. So avoid the divide-by-zero and set it to a low
477 for (i
= 0; i
< max_allocno
; i
++)
479 if (allocno_size
[i
] == 0)
481 if (allocno_live_length
[i
] == 0)
482 allocno_live_length
[i
] = -1;
485 qsort (allocno_order
, max_allocno
, sizeof (int), allocno_compare
);
487 prune_preferences ();
490 dump_conflicts (file
);
492 /* Try allocating them, one by one, in that order,
493 except for parameters marked with reg_live_length[regno] == -2. */
495 for (i
= 0; i
< max_allocno
; i
++)
496 if (reg_live_length
[allocno_reg
[allocno_order
[i
]]] >= 0)
498 /* If we have more than one register class,
499 first try allocating in the class that is cheapest
500 for this pseudo-reg. If that fails, try any reg. */
501 if (N_REG_CLASSES
> 1)
503 find_reg (allocno_order
[i
], HARD_CONST (0), 0, 0, 0);
504 if (reg_renumber
[allocno_reg
[allocno_order
[i
]]] >= 0)
507 if (!reg_preferred_or_nothing (allocno_reg
[allocno_order
[i
]]))
508 find_reg (allocno_order
[i
], HARD_CONST (0), 1, 0, 0);
512 /* Do the reloads now while the allocno data still exist, so that we can
513 try to assign new hard regs to any pseudo regs that are spilled. */
515 if (n_basic_blocks
> 0)
516 reload (basic_block_head
[0], 1, file
);
519 /* Sort predicate for ordering the allocnos.
520 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
523 allocno_compare (v1
, v2
)
526 /* Note that the quotient will never be bigger than
527 the value of floor_log2 times the maximum number of
528 times a register can occur in one insn (surely less than 100).
529 Multiplying this by 10000 can't overflow. */
531 = (((double) (floor_log2 (allocno_n_refs
[*v1
]) * allocno_n_refs
[*v1
])
532 / (allocno_live_length
[*v1
] * allocno_size
[*v1
]))
535 = (((double) (floor_log2 (allocno_n_refs
[*v2
]) * allocno_n_refs
[*v2
])
536 / (allocno_live_length
[*v2
] * allocno_size
[*v2
]))
541 /* If regs are equally good, sort by allocno,
542 so that the results of qsort leave nothing to chance. */
546 /* Scan the rtl code and record all conflicts and register preferences in the
547 conflict matrices and preference tables. */
554 short *block_start_allocnos
;
556 /* Make a vector that mark_reg_{store,clobber} will store in. */
557 regs_set
= (rtx
*) alloca (max_parallel
* sizeof (rtx
) * 2);
559 block_start_allocnos
= (short *) alloca (max_allocno
* sizeof (short));
561 for (b
= 0; b
< n_basic_blocks
; b
++)
563 bzero (allocnos_live
, allocno_row_words
* sizeof (int));
565 /* Initialize table of registers currently live
566 to the state at the beginning of this basic block.
567 This also marks the conflicts among them.
569 For pseudo-regs, there is only one bit for each one
570 no matter how many hard regs it occupies.
571 This is ok; we know the size from PSEUDO_REGNO_SIZE.
572 For explicit hard regs, we cannot know the size that way
573 since one hard reg can be used with various sizes.
574 Therefore, we must require that all the hard regs
575 implicitly live as part of a multi-word hard reg
576 are explicitly marked in basic_block_live_at_start. */
579 register int offset
, bit
;
580 register regset old
= basic_block_live_at_start
[b
];
584 hard_regs_live
= old
[0];
586 COPY_HARD_REG_SET (hard_regs_live
, old
);
588 for (offset
= 0, i
= 0; offset
< regset_size
; offset
++)
589 if (old
[offset
] == 0)
590 i
+= HOST_BITS_PER_INT
;
592 for (bit
= 1; bit
; bit
<<= 1, i
++)
596 if (old
[offset
] & bit
)
598 register int a
= reg_allocno
[i
];
601 SET_ALLOCNO_LIVE (a
);
602 block_start_allocnos
[ax
++] = a
;
604 else if ((a
= reg_renumber
[i
]) >= 0)
605 mark_reg_live_nc (a
, PSEUDO_REGNO_MODE (i
));
609 /* Record that each allocno now live conflicts with each other
610 allocno now live, and with each hard reg now live. */
612 record_conflicts (block_start_allocnos
, ax
);
615 insn
= basic_block_head
[b
];
617 /* Scan the code of this basic block, noting which allocnos
618 and hard regs are born or die. When one is born,
619 record a conflict with all others currently live. */
623 register RTX_CODE code
= GET_CODE (insn
);
626 /* Make regs_set an empty set. */
630 if (code
== INSN
|| code
== CALL_INSN
|| code
== JUMP_INSN
)
635 for (link
= REG_NOTES (insn
);
636 link
&& i
< NUM_NO_CONFLICT_PAIRS
;
637 link
= XEXP (link
, 1))
638 if (REG_NOTE_KIND (link
) == REG_NO_CONFLICT
)
640 no_conflict_pairs
[i
].allocno1
641 = reg_allocno
[REGNO (SET_DEST (PATTERN (insn
)))];
642 no_conflict_pairs
[i
].allocno2
643 = reg_allocno
[REGNO (XEXP (link
, 0))];
648 /* Mark any registers clobbered by INSN as live,
649 so they conflict with the inputs. */
651 note_stores (PATTERN (insn
), mark_reg_clobber
);
653 /* Mark any registers dead after INSN as dead now. */
655 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
656 if (REG_NOTE_KIND (link
) == REG_DEAD
)
657 mark_reg_death (XEXP (link
, 0));
659 /* Mark any registers set in INSN as live,
660 and mark them as conflicting with all other live regs.
661 Clobbers are processed again, so they conflict with
662 the registers that are set. */
664 note_stores (PATTERN (insn
), mark_reg_store
);
667 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
668 if (REG_NOTE_KIND (link
) == REG_INC
)
669 mark_reg_store (XEXP (link
, 0), 0);
672 /* Mark any registers set in INSN and then never used. */
674 while (n_regs_set
> 0)
675 if (find_regno_note (insn
, REG_UNUSED
,
676 REGNO (regs_set
[--n_regs_set
])))
677 mark_reg_death (regs_set
[n_regs_set
]);
680 if (insn
== basic_block_end
[b
])
682 insn
= NEXT_INSN (insn
);
686 /* Expand the preference information by looking for cases where one allocno
687 dies in an insn that sets an allocno. If those two allocnos don't conflict,
688 merge any preferences between those allocnos. */
691 expand_preferences ()
697 /* We only try to handle the most common cases here. Most of the cases
698 where this wins are reg-reg copies. */
700 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
701 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
702 && (set
= single_set (insn
)) != 0
703 && GET_CODE (SET_DEST (set
)) == REG
704 && reg_allocno
[REGNO (SET_DEST (set
))] >= 0)
705 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
706 if (REG_NOTE_KIND (link
) == REG_DEAD
707 && GET_CODE (XEXP (link
, 0)) == REG
708 && reg_allocno
[REGNO (XEXP (link
, 0))] >= 0
709 && ! CONFLICTP (reg_allocno
[REGNO (SET_DEST (set
))],
710 reg_allocno
[REGNO (XEXP (link
, 0))])
711 && ! CONFLICTP (reg_allocno
[REGNO (XEXP (link
, 0))],
712 reg_allocno
[REGNO (SET_DEST (set
))]))
714 int a1
= reg_allocno
[REGNO (SET_DEST (set
))];
715 int a2
= reg_allocno
[REGNO (XEXP (link
, 0))];
717 if (XEXP (link
, 0) == SET_SRC (set
))
719 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a1
],
720 hard_reg_copy_preferences
[a2
]);
721 IOR_HARD_REG_SET (hard_reg_copy_preferences
[a2
],
722 hard_reg_copy_preferences
[a1
]);
725 IOR_HARD_REG_SET (hard_reg_preferences
[a1
],
726 hard_reg_preferences
[a2
]);
727 IOR_HARD_REG_SET (hard_reg_preferences
[a2
],
728 hard_reg_preferences
[a1
]);
729 IOR_HARD_REG_SET (hard_reg_full_preferences
[a1
],
730 hard_reg_full_preferences
[a2
]);
731 IOR_HARD_REG_SET (hard_reg_full_preferences
[a2
],
732 hard_reg_full_preferences
[a1
]);
736 /* Prune the preferences for global registers to exclude registers that cannot
739 Compute `regs_someone_prefers', which is a bitmask of the hard registers
740 that are preferred by conflicting registers of lower priority. If possible,
741 we will avoid using these registers. */
749 /* Scan least most important to most important.
750 For each allocno, remove from preferences registers that cannot be used,
751 either because of conflicts or register type. Then compute all registers
752 prefered by each lower-priority register that conflicts. */
754 for (i
= max_allocno
- 1; i
>= 0; i
--)
758 allocno
= allocno_order
[i
];
759 COPY_HARD_REG_SET (temp
, hard_reg_conflicts
[allocno
]);
761 if (allocno_calls_crossed
[allocno
] == 0)
762 IOR_HARD_REG_SET (temp
, fixed_reg_set
);
764 IOR_HARD_REG_SET (temp
, call_used_reg_set
);
766 IOR_COMPL_HARD_REG_SET
768 reg_class_contents
[(int) reg_preferred_class (allocno_reg
[allocno
])]);
770 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], temp
);
771 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], temp
);
772 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences
[allocno
], temp
);
774 CLEAR_HARD_REG_SET (regs_someone_prefers
[allocno
]);
776 /* Merge in the preferences of lower-priority registers (they have
777 already been pruned). If we also prefer some of those registers,
778 don't exclude them unless we are of a smaller size (in which case
779 we want to give the lower-priority allocno the first chance for
781 for (j
= i
+ 1; j
< max_allocno
; j
++)
782 if (CONFLICTP (allocno
, allocno_order
[j
]))
784 COPY_HARD_REG_SET (temp
,
785 hard_reg_full_preferences
[allocno_order
[j
]]);
786 if (allocno_size
[allocno_order
[j
]] <= allocno_size
[allocno
])
787 AND_COMPL_HARD_REG_SET (temp
,
788 hard_reg_full_preferences
[allocno
]);
790 IOR_HARD_REG_SET (regs_someone_prefers
[allocno
], temp
);
795 /* Assign a hard register to ALLOCNO; look for one that is the beginning
796 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
797 The registers marked in PREFREGS are tried first.
799 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
800 be used for this allocation.
802 If ALL_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
803 Otherwise ignore that preferred class.
805 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
806 will have to be saved and restored at calls.
808 RETRYING is nonzero if this is called from retry_global_alloc.
810 If we find one, record it in reg_renumber.
811 If not, do nothing. */
814 find_reg (allocno
, losers
, all_regs_p
, accept_call_clobbered
, retrying
)
818 int accept_call_clobbered
;
821 register int i
, best_reg
, pass
;
823 register /* Declare it register if it's a scalar. */
825 HARD_REG_SET used
, used1
, used2
;
828 = all_regs_p
? ALL_REGS
: reg_preferred_class (allocno_reg
[allocno
]);
829 enum machine_mode mode
= PSEUDO_REGNO_MODE (allocno_reg
[allocno
]);
831 if (accept_call_clobbered
)
832 COPY_HARD_REG_SET (used1
, call_fixed_reg_set
);
833 else if (allocno_calls_crossed
[allocno
] == 0)
834 COPY_HARD_REG_SET (used1
, fixed_reg_set
);
836 COPY_HARD_REG_SET (used1
, call_used_reg_set
);
838 /* Some registers should not be allocated in global-alloc. */
839 IOR_HARD_REG_SET (used1
, no_global_alloc_regs
);
841 IOR_HARD_REG_SET (used1
, losers
);
843 IOR_COMPL_HARD_REG_SET (used1
, reg_class_contents
[(int) class]);
844 COPY_HARD_REG_SET (used2
, used1
);
846 IOR_HARD_REG_SET (used1
, hard_reg_conflicts
[allocno
]);
848 /* Try each hard reg to see if it fits. Do this in two passes.
849 In the first pass, skip registers that are prefered by some other pseudo
850 to give it a better chance of getting one of those registers. Only if
851 we can't get a register when excluding those do we take one of them.
852 However, we never allocate a register for the first time in pass 0. */
854 COPY_HARD_REG_SET (used
, used1
);
855 IOR_COMPL_HARD_REG_SET (used
, regs_used_so_far
);
856 IOR_HARD_REG_SET (used
, regs_someone_prefers
[allocno
]);
859 for (i
= FIRST_PSEUDO_REGISTER
, pass
= 0;
860 pass
<= 1 && i
>= FIRST_PSEUDO_REGISTER
;
864 COPY_HARD_REG_SET (used
, used1
);
865 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
867 #ifdef REG_ALLOC_ORDER
868 int regno
= reg_alloc_order
[i
];
872 if (! TEST_HARD_REG_BIT (used
, regno
)
873 && HARD_REGNO_MODE_OK (regno
, mode
))
876 register int lim
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
879 && ! TEST_HARD_REG_BIT (used
, j
));
886 #ifndef REG_ALLOC_ORDER
887 i
= j
; /* Skip starting points we know will lose */
893 /* See if there is a preferred register with the same class as the register
894 we allocated above. Making this restriction prevents register
895 preferencing from creating worse register allocation.
897 Remove from the preferred registers and conflicting registers. Note that
898 additional conflicts may have been added after `prune_preferences' was
901 First do this for those register with copy preferences, then all
902 preferred registers. */
904 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences
[allocno
], used
);
905 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences
[allocno
],
906 reg_class_contents
[(int) NO_REGS
], no_copy_prefs
);
910 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
911 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences
[allocno
], i
)
912 && HARD_REGNO_MODE_OK (i
, mode
)
913 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
914 || reg_class_subset_p (REGNO_REG_CLASS (i
),
915 REGNO_REG_CLASS (best_reg
))
916 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
917 REGNO_REG_CLASS (i
))))
920 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
923 && ! TEST_HARD_REG_BIT (used
, j
)
924 && (REGNO_REG_CLASS (j
)
925 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
926 || reg_class_subset_p (REGNO_REG_CLASS (j
),
927 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
928 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
929 REGNO_REG_CLASS (j
))));
940 AND_COMPL_HARD_REG_SET (hard_reg_preferences
[allocno
], used
);
941 GO_IF_HARD_REG_SUBSET (hard_reg_preferences
[allocno
],
942 reg_class_contents
[(int) NO_REGS
], no_prefs
);
946 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
947 if (TEST_HARD_REG_BIT (hard_reg_preferences
[allocno
], i
)
948 && HARD_REGNO_MODE_OK (i
, mode
)
949 && (REGNO_REG_CLASS (i
) == REGNO_REG_CLASS (best_reg
)
950 || reg_class_subset_p (REGNO_REG_CLASS (i
),
951 REGNO_REG_CLASS (best_reg
))
952 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
),
953 REGNO_REG_CLASS (i
))))
956 register int lim
= i
+ HARD_REGNO_NREGS (i
, mode
);
959 && ! TEST_HARD_REG_BIT (used
, j
)
960 && (REGNO_REG_CLASS (j
)
961 == REGNO_REG_CLASS (best_reg
+ (j
- i
))
962 || reg_class_subset_p (REGNO_REG_CLASS (j
),
963 REGNO_REG_CLASS (best_reg
+ (j
- i
)))
964 || reg_class_subset_p (REGNO_REG_CLASS (best_reg
+ (j
- i
)),
965 REGNO_REG_CLASS (j
))));
976 /* If we haven't succeeded yet, try with caller-saves. */
977 if (flag_caller_saves
&& best_reg
< 0)
979 /* Did not find a register. If it would be profitable to
980 allocate a call-clobbered register and save and restore it
981 around calls, do that. */
982 if (! accept_call_clobbered
983 && allocno_calls_crossed
[allocno
] != 0
984 && CALLER_SAVE_PROFITABLE (allocno_n_refs
[allocno
],
985 allocno_calls_crossed
[allocno
]))
987 find_reg (allocno
, losers
, all_regs_p
, 1, retrying
);
988 if (reg_renumber
[allocno_reg
[allocno
]] >= 0)
990 caller_save_needed
= 1;
996 /* If we haven't succeeded yet,
997 see if some hard reg that conflicts with us
998 was utilized poorly by local-alloc.
999 If so, kick out the regs that were put there by local-alloc
1000 so we can use it instead. */
1001 if (best_reg
< 0 && !retrying
1002 /* Let's not bother with multi-reg allocnos. */
1003 && allocno_size
[allocno
] == 1)
1005 /* Count from the end, to find the least-used ones first. */
1006 for (i
= FIRST_PSEUDO_REGISTER
- 1; i
>= 0; i
--)
1007 if (local_reg_n_refs
[i
] != 0
1008 /* Don't use a reg no good for this pseudo. */
1009 && ! TEST_HARD_REG_BIT (used2
, i
)
1010 && HARD_REGNO_MODE_OK (i
, mode
)
1011 && ((double) local_reg_n_refs
[i
] / local_reg_live_length
[i
]
1012 < ((double) allocno_n_refs
[allocno
]
1013 / allocno_live_length
[allocno
])))
1015 /* Hard reg I was used less in total by local regs
1016 than it would be used by this one allocno! */
1018 for (k
= 0; k
< max_regno
; k
++)
1019 if (reg_renumber
[k
] == i
)
1020 reg_renumber
[k
] = -1;
1026 /* Did we find a register? */
1030 register int lim
, j
;
1031 HARD_REG_SET this_reg
;
1033 /* Yes. Record it as the hard register of this pseudo-reg. */
1034 reg_renumber
[allocno_reg
[allocno
]] = best_reg
;
1035 /* Also of any pseudo-regs that share with it. */
1036 if (reg_may_share
[allocno_reg
[allocno
]])
1037 for (j
= FIRST_PSEUDO_REGISTER
; j
< max_regno
; j
++)
1038 if (reg_allocno
[j
] == allocno
)
1039 reg_renumber
[j
] = best_reg
;
1041 /* Make a set of the hard regs being allocated. */
1042 CLEAR_HARD_REG_SET (this_reg
);
1043 lim
= best_reg
+ HARD_REGNO_NREGS (best_reg
, mode
);
1044 for (j
= best_reg
; j
< lim
; j
++)
1046 SET_HARD_REG_BIT (this_reg
, j
);
1047 SET_HARD_REG_BIT (regs_used_so_far
, j
);
1048 /* This is no longer a reg used just by local regs. */
1049 local_reg_n_refs
[j
] = 0;
1051 /* For each other pseudo-reg conflicting with this one,
1052 mark it as conflicting with the hard regs this one occupies. */
1054 for (j
= 0; j
< max_allocno
; j
++)
1055 if (CONFLICTP (lim
, j
) || CONFLICTP (j
, lim
))
1057 IOR_HARD_REG_SET (hard_reg_conflicts
[j
], this_reg
);
1062 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1063 Perhaps it had previously seemed not worth a hard reg,
1064 or perhaps its old hard reg has been commandeered for reloads.
1065 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1066 they do not appear to be allocated.
1067 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1070 retry_global_alloc (regno
, forbidden_regs
)
1072 HARD_REG_SET forbidden_regs
;
1074 int allocno
= reg_allocno
[regno
];
1077 /* If we have more than one register class,
1078 first try allocating in the class that is cheapest
1079 for this pseudo-reg. If that fails, try any reg. */
1080 if (N_REG_CLASSES
> 1)
1081 find_reg (allocno
, forbidden_regs
, 0, 0, 1);
1082 if (reg_renumber
[regno
] < 0
1083 && !reg_preferred_or_nothing (regno
))
1084 find_reg (allocno
, forbidden_regs
, 1, 0, 1);
1086 /* If we found a register, modify the RTL for the register to
1087 show the hard register, and mark that register live. */
1088 if (reg_renumber
[regno
] >= 0)
1090 REGNO (regno_reg_rtx
[regno
]) = reg_renumber
[regno
];
1091 mark_home_live (regno
);
1096 /* Record a conflict between register REGNO
1097 and everything currently live.
1098 REGNO must not be a pseudo reg that was allocated
1099 by local_alloc; such numbers must be translated through
1100 reg_renumber before calling here. */
1103 record_one_conflict (regno
)
1108 if (regno
< FIRST_PSEUDO_REGISTER
)
1109 /* When a hard register becomes live,
1110 record conflicts with live pseudo regs. */
1111 for (j
= 0; j
< max_allocno
; j
++)
1113 if (ALLOCNO_LIVE_P (j
))
1114 SET_HARD_REG_BIT (hard_reg_conflicts
[j
], regno
);
1117 /* When a pseudo-register becomes live,
1118 record conflicts first with hard regs,
1119 then with other pseudo regs. */
1121 register int ialloc
= reg_allocno
[regno
];
1122 register int ialloc_prod
= ialloc
* allocno_row_words
;
1123 IOR_HARD_REG_SET (hard_reg_conflicts
[ialloc
], hard_regs_live
);
1124 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1128 for (k
= 0; k
< n_no_conflict_pairs
; k
++)
1129 if (! ((j
== no_conflict_pairs
[k
].allocno1
1130 && ialloc
== no_conflict_pairs
[k
].allocno2
)
1132 (j
== no_conflict_pairs
[k
].allocno2
1133 && ialloc
== no_conflict_pairs
[k
].allocno1
)))
1135 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1140 /* Record all allocnos currently live as conflicting
1141 with each other and with all hard regs currently live.
1142 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1143 are currently live. Their bits are also flagged in allocnos_live. */
1146 record_conflicts (allocno_vec
, len
)
1147 register short *allocno_vec
;
1150 register int allocno
;
1152 register int ialloc_prod
;
1156 allocno
= allocno_vec
[len
];
1157 ialloc_prod
= allocno
* allocno_row_words
;
1158 IOR_HARD_REG_SET (hard_reg_conflicts
[allocno
], hard_regs_live
);
1159 for (j
= allocno_row_words
- 1; j
>= 0; j
--)
1160 conflicts
[ialloc_prod
+ j
] |= allocnos_live
[j
];
1164 /* Handle the case where REG is set by the insn being scanned,
1165 during the forward scan to accumulate conflicts.
1166 Store a 1 in regs_live or allocnos_live for this register, record how many
1167 consecutive hardware registers it actually needs,
1168 and record a conflict with all other registers already live.
1170 Note that even if REG does not remain alive after this insn,
1171 we must mark it here as live, to ensure a conflict between
1172 REG and any other regs set in this insn that really do live.
1173 This is because those other regs could be considered after this.
1175 REG might actually be something other than a register;
1176 if so, we do nothing.
1178 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1179 a REG_INC note was found for it).
1181 CLOBBERs are processed here by calling mark_reg_clobber. */
1184 mark_reg_store (orig_reg
, setter
)
1185 rtx orig_reg
, setter
;
1188 register rtx reg
= orig_reg
;
1190 /* WORD is which word of a multi-register group is being stored.
1191 For the case where the store is actually into a SUBREG of REG.
1192 Except we don't use it; I believe the entire REG needs to be
1196 if (GET_CODE (reg
) == SUBREG
)
1198 word
= SUBREG_WORD (reg
);
1199 reg
= SUBREG_REG (reg
);
1202 if (GET_CODE (reg
) != REG
)
1205 if (setter
&& GET_CODE (setter
) == CLOBBER
)
1207 /* A clobber of a register should be processed here too. */
1208 mark_reg_clobber (orig_reg
, setter
);
1212 regs_set
[n_regs_set
++] = reg
;
1215 set_preference (reg
, SET_SRC (setter
));
1217 regno
= REGNO (reg
);
1219 if (reg_renumber
[regno
] >= 0)
1220 regno
= reg_renumber
[regno
] /* + word */;
1222 /* Either this is one of the max_allocno pseudo regs not allocated,
1223 or it is or has a hardware reg. First handle the pseudo-regs. */
1224 if (regno
>= FIRST_PSEUDO_REGISTER
)
1226 if (reg_allocno
[regno
] >= 0)
1228 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1229 record_one_conflict (regno
);
1232 /* Handle hardware regs (and pseudos allocated to hard regs). */
1233 else if (! fixed_regs
[regno
])
1235 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1236 while (regno
< last
)
1238 record_one_conflict (regno
);
1239 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1245 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1248 mark_reg_clobber (reg
, setter
)
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
1259 if (GET_CODE (setter
) != CLOBBER
)
1262 if (GET_CODE (reg
) == SUBREG
)
1264 word
= SUBREG_WORD (reg
);
1265 reg
= SUBREG_REG (reg
);
1268 if (GET_CODE (reg
) != REG
)
1271 regs_set
[n_regs_set
++] = reg
;
1273 regno
= REGNO (reg
);
1275 if (reg_renumber
[regno
] >= 0)
1276 regno
= reg_renumber
[regno
] /* + word */;
1278 /* Either this is one of the max_allocno pseudo regs not allocated,
1279 or it is or has a hardware reg. First handle the pseudo-regs. */
1280 if (regno
>= FIRST_PSEUDO_REGISTER
)
1282 if (reg_allocno
[regno
] >= 0)
1284 SET_ALLOCNO_LIVE (reg_allocno
[regno
]);
1285 record_one_conflict (regno
);
1288 /* Handle hardware regs (and pseudos allocated to hard regs). */
1289 else if (! fixed_regs
[regno
])
1291 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1292 while (regno
< last
)
1294 record_one_conflict (regno
);
1295 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1301 /* Mark REG as being dead (following the insn being scanned now).
1302 Store a 0 in regs_live or allocnos_live for this register. */
1305 mark_reg_death (reg
)
1308 register int regno
= REGNO (reg
);
1310 /* For pseudo reg, see if it has been assigned a hardware reg. */
1311 if (reg_renumber
[regno
] >= 0)
1312 regno
= reg_renumber
[regno
];
1314 /* Either this is one of the max_allocno pseudo regs not allocated,
1315 or it is a hardware reg. First handle the pseudo-regs. */
1316 if (regno
>= FIRST_PSEUDO_REGISTER
)
1318 if (reg_allocno
[regno
] >= 0)
1319 CLEAR_ALLOCNO_LIVE (reg_allocno
[regno
]);
1321 /* Handle hardware regs (and pseudos allocated to hard regs). */
1322 else if (! fixed_regs
[regno
])
1324 /* Pseudo regs already assigned hardware regs are treated
1325 almost the same as explicit hardware regs. */
1326 register int last
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
1327 while (regno
< last
)
1329 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
1335 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1336 for the value stored in it. MODE determines how many consecutive
1337 registers are actually in use. Do not record conflicts;
1338 it is assumed that the caller will do that. */
1341 mark_reg_live_nc (regno
, mode
)
1343 enum machine_mode mode
;
1345 register int last
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
1346 while (regno
< last
)
1348 SET_HARD_REG_BIT (hard_regs_live
, regno
);
1353 /* Try to set a preference for an allocno to a hard register.
1354 We are passed DEST and SRC which are the operands of a SET. It is known
1355 that SRC is a register. If SRC or the first operand of SRC is a register,
1356 try to set a preference. If one of the two is a hard register and the other
1357 is a pseudo-register, mark the preference.
1359 Note that we are not as agressive as local-alloc in trying to tie a
1360 pseudo-register to a hard register. */
1363 set_preference (dest
, src
)
1366 int src_regno
, dest_regno
;
1367 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1368 to compensate for subregs in SRC or DEST. */
1373 if (GET_RTX_FORMAT (GET_CODE (src
))[0] == 'e')
1374 src
= XEXP (src
, 0), copy
= 0;
1376 /* Get the reg number for both SRC and DEST.
1377 If neither is a reg, give up. */
1379 if (GET_CODE (src
) == REG
)
1380 src_regno
= REGNO (src
);
1381 else if (GET_CODE (src
) == SUBREG
&& GET_CODE (SUBREG_REG (src
)) == REG
)
1383 src_regno
= REGNO (SUBREG_REG (src
));
1384 offset
+= SUBREG_WORD (src
);
1389 if (GET_CODE (dest
) == REG
)
1390 dest_regno
= REGNO (dest
);
1391 else if (GET_CODE (dest
) == SUBREG
&& GET_CODE (SUBREG_REG (dest
)) == REG
)
1393 dest_regno
= REGNO (SUBREG_REG (dest
));
1394 offset
-= SUBREG_WORD (dest
);
1399 /* Convert either or both to hard reg numbers. */
1401 if (reg_renumber
[src_regno
] >= 0)
1402 src_regno
= reg_renumber
[src_regno
];
1404 if (reg_renumber
[dest_regno
] >= 0)
1405 dest_regno
= reg_renumber
[dest_regno
];
1407 /* Now if one is a hard reg and the other is a global pseudo
1408 then give the other a preference. */
1410 if (dest_regno
< FIRST_PSEUDO_REGISTER
&& src_regno
>= FIRST_PSEUDO_REGISTER
1411 && reg_allocno
[src_regno
] >= 0)
1413 dest_regno
-= offset
;
1414 if (dest_regno
>= 0 && dest_regno
< FIRST_PSEUDO_REGISTER
)
1417 SET_REGBIT (hard_reg_copy_preferences
,
1418 reg_allocno
[src_regno
], dest_regno
);
1420 SET_REGBIT (hard_reg_preferences
,
1421 reg_allocno
[src_regno
], dest_regno
);
1422 for (i
= dest_regno
;
1423 i
< dest_regno
+ HARD_REGNO_NREGS (dest_regno
, GET_MODE (dest
));
1425 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[src_regno
], i
);
1429 if (src_regno
< FIRST_PSEUDO_REGISTER
&& dest_regno
>= FIRST_PSEUDO_REGISTER
1430 && reg_allocno
[dest_regno
] >= 0)
1432 src_regno
+= offset
;
1433 if (src_regno
>= 0 && src_regno
< FIRST_PSEUDO_REGISTER
)
1436 SET_REGBIT (hard_reg_copy_preferences
,
1437 reg_allocno
[dest_regno
], src_regno
);
1439 SET_REGBIT (hard_reg_preferences
,
1440 reg_allocno
[dest_regno
], src_regno
);
1442 i
< src_regno
+ HARD_REGNO_NREGS (src_regno
, GET_MODE (src
));
1444 SET_REGBIT (hard_reg_full_preferences
, reg_allocno
[dest_regno
], i
);
1449 /* Indicate that hard register number FROM was eliminated and replaced with
1450 an offset from hard register number TO. The status of hard registers live
1451 at the start of a basic block is updated by replacing a use of FROM with
1455 mark_elimination (from
, to
)
1460 for (i
= 0; i
< n_basic_blocks
; i
++)
1461 if ((basic_block_live_at_start
[i
][from
/ HOST_BITS_PER_INT
]
1462 & (1 << (from
% HOST_BITS_PER_INT
))) != 0)
1464 basic_block_live_at_start
[i
][from
/ HOST_BITS_PER_INT
]
1465 &= ~ (1 << (from
% HOST_BITS_PER_INT
));
1466 basic_block_live_at_start
[i
][to
/ HOST_BITS_PER_INT
]
1467 |= (1 << (to
% HOST_BITS_PER_INT
));
1471 /* Print debugging trace information if -greg switch is given,
1472 showing the information on which the allocation decisions are based. */
1475 dump_conflicts (file
)
1479 register int has_preferences
;
1480 fprintf (file
, ";; %d regs to allocate:", max_allocno
);
1481 for (i
= 0; i
< max_allocno
; i
++)
1484 fprintf (file
, " %d", allocno_reg
[allocno_order
[i
]]);
1485 for (j
= 0; j
< max_regno
; j
++)
1486 if (reg_allocno
[j
] == allocno_order
[i
]
1487 && j
!= allocno_reg
[allocno_order
[i
]])
1488 fprintf (file
, "+%d", j
);
1489 if (allocno_size
[allocno_order
[i
]] != 1)
1490 fprintf (file
, " (%d)", allocno_size
[allocno_order
[i
]]);
1492 fprintf (file
, "\n");
1494 for (i
= 0; i
< max_allocno
; i
++)
1497 fprintf (file
, ";; %d conflicts:", allocno_reg
[i
]);
1498 for (j
= 0; j
< max_allocno
; j
++)
1499 if (CONFLICTP (i
, j
) || CONFLICTP (j
, i
))
1500 fprintf (file
, " %d", allocno_reg
[j
]);
1501 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1502 if (TEST_HARD_REG_BIT (hard_reg_conflicts
[i
], j
))
1503 fprintf (file
, " %d", j
);
1504 fprintf (file
, "\n");
1506 has_preferences
= 0;
1507 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1508 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1509 has_preferences
= 1;
1511 if (! has_preferences
)
1513 fprintf (file
, ";; %d preferences:", allocno_reg
[i
]);
1514 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1515 if (TEST_HARD_REG_BIT (hard_reg_preferences
[i
], j
))
1516 fprintf (file
, " %d", j
);
1517 fprintf (file
, "\n");
1519 fprintf (file
, "\n");
1523 dump_global_regs (file
)
1528 fprintf (file
, ";; Register dispositions:\n");
1529 for (i
= FIRST_PSEUDO_REGISTER
, j
= 0; i
< max_regno
; i
++)
1530 if (reg_renumber
[i
] >= 0)
1532 fprintf (file
, "%d in %d ", i
, reg_renumber
[i
]);
1534 fprintf (file
, "\n");
1537 fprintf (file
, "\n\n;; Hard regs used: ");
1538 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1539 if (regs_ever_live
[i
])
1540 fprintf (file
, " %d", i
);
1541 fprintf (file
, "\n\n");