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