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