![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to local-alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 2.x] / gcc|
Return to local-alloc.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Allocate registers within a basic block, for GNU compiler.
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: /* Allocation of hard register numbers to pseudo registers is done in
22: two passes. In this pass we consider only regs that are born and
23: die once within one basic block. We do this one basic block at a
24: time. Then the next pass allocates the registers that remain.
25: Two passes are used because this pass uses methods that work only
26: on linear code, but that do a better job than the general methods
27: used in global_alloc, and more quickly too.
28:
29: The assignments made are recorded in the vector reg_renumber
30: whose space is allocated here. The rtl code itself is not altered.
31:
32: We assign each instruction in the basic block a number
33: which is its order from the beginning of the block.
34: Then we can represent the lifetime of a pseudo register with
35: a pair of numbers, and check for conflicts easily.
36: We can record the availability of hard registers with a
37: HARD_REG_SET for each instruction. The HARD_REG_SET
38: contains 0 or 1 for each hard reg.
39:
40: To avoid register shuffling, we tie registers together when one
41: dies by being copied into another, or dies in an instruction that
42: does arithmetic to produce another. The tied registers are
43: allocated as one. Registers with different reg class preferences
44: can never be tied unless the class preferred by one is a subclass
45: of the one preferred by the other.
46:
47: Tying is represented with "quantity numbers".
48: A non-tied register is given a new quantity number.
49: Tied registers have the same quantity number.
50:
51: We have provision to exempt registers, even when they are contained
52: within the block, that can be tied to others that are not contained in it.
53: This is so that global_alloc could process them both and tie them then.
54: But this is currently disabled since tying in global_alloc is not
55: yet implemented. */
56:
57: #include <stdio.h>
58: #include "config.h"
59: #include "rtl.h"
60: #include "flags.h"
61: #include "basic-block.h"
62: #include "regs.h"
63: #include "hard-reg-set.h"
64: #include "insn-config.h"
65: #include "recog.h"
66: #include "output.h"
67:
68: /* Next quantity number available for allocation. */
69:
70: static int next_qty;
71:
72: /* In all the following vectors indexed by quantity number. */
73:
74: /* Element Q is the hard reg number chosen for quantity Q,
75: or -1 if none was found. */
76:
77: static short *qty_phys_reg;
78:
79: /* We maintain two hard register sets that indicate suggested hard registers
80: for each quantity. The first, qty_phys_copy_sugg, contains hard registers
81: that are tied to the quantity by a simple copy. The second contains all
82: hard registers that are tied to the quantity via an arithmetic operation.
83:
84: The former register set is given priority for allocation. This tends to
85: eliminate copy insns. */
86:
87: /* Element Q is a set of hard registers that are suggested for quantity Q by
88: copy insns. */
89:
90: static HARD_REG_SET *qty_phys_copy_sugg;
91:
92: /* Element Q is a set of hard registers that are suggested for quantity Q by
93: arithmetic insns. */
94:
95: static HARD_REG_SET *qty_phys_sugg;
96:
97: /* Element Q is non-zero if there is a suggested register in
98: qty_phys_copy_sugg. */
99:
100: static char *qty_phys_has_copy_sugg;
101:
102: /* Element Q is non-zero if there is a suggested register in qty_phys_sugg. */
103:
104: static char *qty_phys_has_sugg;
105:
106: /* Element Q is the number of refs to quantity Q. */
107:
108: static short *qty_n_refs;
109:
110: /* Element Q is a reg class contained in (smaller than) the
111: preferred classes of all the pseudo regs that are tied in quantity Q.
112: This is the preferred class for allocating that quantity. */
113:
114: static enum reg_class *qty_min_class;
115:
116: /* Insn number (counting from head of basic block)
117: where quantity Q was born. -1 if birth has not been recorded. */
118:
119: static int *qty_birth;
120:
121: /* Insn number (counting from head of basic block)
122: where quantity Q died. Due to the way tying is done,
123: and the fact that we consider in this pass only regs that die but once,
124: a quantity can die only once. Each quantity's life span
125: is a set of consecutive insns. -1 if death has not been recorded. */
126:
127: static int *qty_death;
128:
129: /* Number of words needed to hold the data in quantity Q.
130: This depends on its machine mode. It is used for these purposes:
131: 1. It is used in computing the relative importances of qtys,
132: which determines the order in which we look for regs for them.
133: 2. It is used in rules that prevent tying several registers of
134: different sizes in a way that is geometrically impossible
135: (see combine_regs). */
136:
137: static int *qty_size;
138:
139: /* This holds the mode of the registers that are tied to qty Q,
140: or VOIDmode if registers with differing modes are tied together. */
141:
142: static enum machine_mode *qty_mode;
143:
144: /* Number of times a reg tied to qty Q lives across a CALL_INSN. */
145:
146: static int *qty_n_calls_crossed;
147:
1.1.1.4 ! root 148: /* Register class within which we allocate qty Q if we can't get
! 149: its preferred class. */
1.1 root 150:
1.1.1.4 ! root 151: static enum reg_class *qty_alternate_class;
1.1 root 152:
153: /* Element Q is the SCRATCH expression for which this quantity is being
154: allocated or 0 if this quantity is allocating registers. */
155:
156: static rtx *qty_scratch_rtx;
157:
158: /* Element Q is the register number of one pseudo register whose
159: reg_qty value is Q, or -1 is this quantity is for a SCRATCH. This
160: register should be the head of the chain maintained in reg_next_in_qty. */
161:
162: static short *qty_first_reg;
163:
164: /* If (REG N) has been assigned a quantity number, is a register number
165: of another register assigned the same quantity number, or -1 for the
166: end of the chain. qty_first_reg point to the head of this chain. */
167:
168: static short *reg_next_in_qty;
169:
170: /* reg_qty[N] (where N is a pseudo reg number) is the qty number of that reg
171: if it is >= 0,
172: of -1 if this register cannot be allocated by local-alloc,
173: or -2 if not known yet.
174:
175: Note that if we see a use or death of pseudo register N with
176: reg_qty[N] == -2, register N must be local to the current block. If
177: it were used in more than one block, we would have reg_qty[N] == -1.
178: This relies on the fact that if reg_basic_block[N] is >= 0, register N
179: will not appear in any other block. We save a considerable number of
180: tests by exploiting this.
181:
182: If N is < FIRST_PSEUDO_REGISTER, reg_qty[N] is undefined and should not
183: be referenced. */
184:
185: static int *reg_qty;
186:
187: /* The offset (in words) of register N within its quantity.
188: This can be nonzero if register N is SImode, and has been tied
189: to a subreg of a DImode register. */
190:
191: static char *reg_offset;
192:
193: /* Vector of substitutions of register numbers,
194: used to map pseudo regs into hardware regs.
195: This is set up as a result of register allocation.
196: Element N is the hard reg assigned to pseudo reg N,
197: or is -1 if no hard reg was assigned.
198: If N is a hard reg number, element N is N. */
199:
200: short *reg_renumber;
201:
202: /* Set of hard registers live at the current point in the scan
203: of the instructions in a basic block. */
204:
205: static HARD_REG_SET regs_live;
206:
207: /* Each set of hard registers indicates registers live at a particular
208: point in the basic block. For N even, regs_live_at[N] says which
209: hard registers are needed *after* insn N/2 (i.e., they may not
210: conflict with the outputs of insn N/2 or the inputs of insn N/2 + 1.
211:
212: If an object is to conflict with the inputs of insn J but not the
213: outputs of insn J + 1, we say it is born at index J*2 - 1. Similarly,
214: if it is to conflict with the outputs of insn J but not the inputs of
215: insn J + 1, it is said to die at index J*2 + 1. */
216:
217: static HARD_REG_SET *regs_live_at;
218:
219: /* Communicate local vars `insn_number' and `insn'
220: from `block_alloc' to `reg_is_set', `wipe_dead_reg', and `alloc_qty'. */
221: static int this_insn_number;
222: static rtx this_insn;
223:
224: static void block_alloc ();
225: static void update_equiv_regs ();
226: static int no_conflict_p ();
227: static int combine_regs ();
228: static void wipe_dead_reg ();
229: static int find_free_reg ();
230: static void reg_is_born ();
231: static void reg_is_set ();
232: static void mark_life ();
233: static void post_mark_life ();
234: static int qty_compare ();
235: static int qty_compare_1 ();
236: static int reg_meets_class_p ();
237: static void update_qty_class ();
238: static int requires_inout_p ();
239:
240: /* Allocate a new quantity (new within current basic block)
241: for register number REGNO which is born at index BIRTH
242: within the block. MODE and SIZE are info on reg REGNO. */
243:
244: static void
245: alloc_qty (regno, mode, size, birth)
246: int regno;
247: enum machine_mode mode;
248: int size, birth;
249: {
250: register int qty = next_qty++;
251:
252: reg_qty[regno] = qty;
253: reg_offset[regno] = 0;
254: reg_next_in_qty[regno] = -1;
255:
256: qty_first_reg[qty] = regno;
257: qty_size[qty] = size;
258: qty_mode[qty] = mode;
259: qty_birth[qty] = birth;
260: qty_n_calls_crossed[qty] = reg_n_calls_crossed[regno];
261: qty_min_class[qty] = reg_preferred_class (regno);
1.1.1.4 ! root 262: qty_alternate_class[qty] = reg_alternate_class (regno);
1.1 root 263: qty_n_refs[qty] = reg_n_refs[regno];
264: }
265:
266: /* Similar to `alloc_qty', but allocates a quantity for a SCRATCH rtx
267: used as operand N in INSN. We assume here that the SCRATCH is used in
268: a CLOBBER. */
269:
270: static void
271: alloc_qty_for_scratch (scratch, n, insn, insn_code_num, insn_number)
272: rtx scratch;
273: int n;
274: rtx insn;
275: int insn_code_num, insn_number;
276: {
277: register int qty;
278: enum reg_class class;
279: char *p, c;
280: int i;
281:
1.1.1.4 ! root 282: #ifdef REGISTER_CONSTRAINTS
1.1 root 283: /* If we haven't yet computed which alternative will be used, do so now.
284: Then set P to the constraints for that alternative. */
285: if (which_alternative == -1)
286: if (! constrain_operands (insn_code_num, 0))
287: return;
288:
289: for (p = insn_operand_constraint[insn_code_num][n], i = 0;
290: *p && i < which_alternative; p++)
291: if (*p == ',')
292: i++;
293:
294: /* Compute the class required for this SCRATCH. If we don't need a
295: register, the class will remain NO_REGS. If we guessed the alternative
296: number incorrectly, reload will fix things up for us. */
297:
298: class = NO_REGS;
299: while ((c = *p++) != '\0' && c != ',')
300: switch (c)
301: {
302: case '=': case '+': case '?':
303: case '#': case '&': case '!':
304: case '*': case '%':
305: case '0': case '1': case '2': case '3': case '4':
306: case 'm': case '<': case '>': case 'V': case 'o':
307: case 'E': case 'F': case 'G': case 'H':
308: case 's': case 'i': case 'n':
309: case 'I': case 'J': case 'K': case 'L':
310: case 'M': case 'N': case 'O': case 'P':
311: #ifdef EXTRA_CONSTRAINT
312: case 'Q': case 'R': case 'S': case 'T': case 'U':
313: #endif
314: case 'p':
315: /* These don't say anything we care about. */
316: break;
317:
318: case 'X':
319: /* We don't need to allocate this SCRATCH. */
320: return;
321:
322: case 'g': case 'r':
323: class = reg_class_subunion[(int) class][(int) GENERAL_REGS];
324: break;
325:
326: default:
327: class
328: = reg_class_subunion[(int) class][(int) REG_CLASS_FROM_LETTER (c)];
329: break;
330: }
331:
332: /* If CLASS has only one register, don't allocate the SCRATCH here since
333: it will prevent that register from being used as a spill register.
334: reload will do the allocation. */
335:
336: if (class == NO_REGS || reg_class_size[(int) class] == 1)
337: return;
338:
1.1.1.4 ! root 339: #else /* REGISTER_CONSTRAINTS */
! 340:
! 341: class = GENERAL_REGS;
! 342: #endif
! 343:
! 344:
1.1 root 345: qty = next_qty++;
346:
347: qty_first_reg[qty] = -1;
348: qty_scratch_rtx[qty] = scratch;
349: qty_size[qty] = GET_MODE_SIZE (GET_MODE (scratch));
350: qty_mode[qty] = GET_MODE (scratch);
351: qty_birth[qty] = 2 * insn_number - 1;
352: qty_death[qty] = 2 * insn_number + 1;
353: qty_n_calls_crossed[qty] = 0;
354: qty_min_class[qty] = class;
1.1.1.4 ! root 355: qty_alternate_class[qty] = NO_REGS;
1.1 root 356: qty_n_refs[qty] = 1;
357: }
358:
359: /* Main entry point of this file. */
360:
361: void
362: local_alloc ()
363: {
364: register int b, i;
365: int max_qty;
366:
367: /* Leaf functions and non-leaf functions have different needs.
368: If defined, let the machine say what kind of ordering we
369: should use. */
370: #ifdef ORDER_REGS_FOR_LOCAL_ALLOC
371: ORDER_REGS_FOR_LOCAL_ALLOC;
372: #endif
373:
374: /* Promote REG_EQUAL notes to REG_EQUIV notes and adjust status of affected
375: registers. */
376: update_equiv_regs ();
377:
378: /* This sets the maximum number of quantities we can have. Quantity
1.1.1.2 root 379: numbers start at zero and we can have one for each pseudo plus the
1.1.1.3 root 380: number of SCRATCHes in the largest block, in the worst case. */
1.1 root 381: max_qty = (max_regno - FIRST_PSEUDO_REGISTER) + max_scratch;
382:
383: /* Allocate vectors of temporary data.
384: See the declarations of these variables, above,
385: for what they mean. */
386:
387: qty_phys_reg = (short *) alloca (max_qty * sizeof (short));
388: qty_phys_copy_sugg = (HARD_REG_SET *) alloca (max_qty * sizeof (HARD_REG_SET));
389: qty_phys_has_copy_sugg = (char *) alloca (max_qty * sizeof (char));
390: qty_phys_sugg = (HARD_REG_SET *) alloca (max_qty * sizeof (HARD_REG_SET));
391: qty_phys_has_sugg = (char *) alloca (max_qty * sizeof (char));
392: qty_birth = (int *) alloca (max_qty * sizeof (int));
393: qty_death = (int *) alloca (max_qty * sizeof (int));
394: qty_scratch_rtx = (rtx *) alloca (max_qty * sizeof (rtx));
395: qty_first_reg = (short *) alloca (max_qty * sizeof (short));
396: qty_size = (int *) alloca (max_qty * sizeof (int));
397: qty_mode = (enum machine_mode *) alloca (max_qty * sizeof (enum machine_mode));
398: qty_n_calls_crossed = (int *) alloca (max_qty * sizeof (int));
399: qty_min_class = (enum reg_class *) alloca (max_qty * sizeof (enum reg_class));
1.1.1.4 ! root 400: qty_alternate_class = (enum reg_class *) alloca (max_qty * sizeof (enum reg_class));
1.1 root 401: qty_n_refs = (short *) alloca (max_qty * sizeof (short));
402:
403: reg_qty = (int *) alloca (max_regno * sizeof (int));
404: reg_offset = (char *) alloca (max_regno * sizeof (char));
405: reg_next_in_qty = (short *) alloca (max_regno * sizeof (short));
406:
407: reg_renumber = (short *) oballoc (max_regno * sizeof (short));
408: for (i = 0; i < max_regno; i++)
409: reg_renumber[i] = -1;
410:
411: /* Determine which pseudo-registers can be allocated by local-alloc.
412: In general, these are the registers used only in a single block and
413: which only die once. However, if a register's preferred class has only
414: one entry, don't allocate this register here unless it is preferred
415: or nothing since retry_global_alloc won't be able to move it to
416: GENERAL_REGS if a reload register of this class is needed.
417:
418: We need not be concerned with which block actually uses the register
419: since we will never see it outside that block. */
420:
421: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
422: {
423: if (reg_basic_block[i] >= 0 && reg_n_deaths[i] == 1
1.1.1.4 ! root 424: && (reg_alternate_class (i) == NO_REGS
1.1 root 425: || reg_class_size[(int) reg_preferred_class (i)] > 1))
426: reg_qty[i] = -2;
427: else
428: reg_qty[i] = -1;
429: }
430:
431: /* Force loop below to initialize entire quantity array. */
432: next_qty = max_qty;
433:
434: /* Allocate each block's local registers, block by block. */
435:
436: for (b = 0; b < n_basic_blocks; b++)
437: {
438: /* NEXT_QTY indicates which elements of the `qty_...'
439: vectors might need to be initialized because they were used
440: for the previous block; it is set to the entire array before
441: block 0. Initialize those, with explicit loop if there are few,
442: else with bzero and bcopy. Do not initialize vectors that are
443: explicit set by `alloc_qty'. */
444:
445: if (next_qty < 6)
446: {
447: for (i = 0; i < next_qty; i++)
448: {
449: qty_scratch_rtx[i] = 0;
450: CLEAR_HARD_REG_SET (qty_phys_copy_sugg[i]);
451: qty_phys_has_copy_sugg[i] = 0;
452: CLEAR_HARD_REG_SET (qty_phys_sugg[i]);
453: qty_phys_has_sugg[i] = 0;
454: }
455: }
456: else
457: {
458: #define CLEAR(vector) \
459: bzero ((vector), (sizeof (*(vector))) * next_qty);
460:
461: CLEAR (qty_scratch_rtx);
462: CLEAR (qty_phys_copy_sugg);
463: CLEAR (qty_phys_has_copy_sugg);
464: CLEAR (qty_phys_sugg);
465: CLEAR (qty_phys_has_sugg);
466: }
467:
468: next_qty = 0;
469:
470: block_alloc (b);
471: #ifdef USE_C_ALLOCA
472: alloca (0);
473: #endif
474: }
475: }
476:
477: /* Depth of loops we are in while in update_equiv_regs. */
478: static int loop_depth;
479:
480: /* Used for communication between the following two functions: contains
481: a MEM that we wish to ensure remains unchanged. */
482: static rtx equiv_mem;
483:
484: /* Set nonzero if EQUIV_MEM is modified. */
485: static int equiv_mem_modified;
486:
487: /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
488: Called via note_stores. */
489:
490: static void
491: validate_equiv_mem_from_store (dest, set)
492: rtx dest;
493: rtx set;
494: {
495: if ((GET_CODE (dest) == REG
496: && reg_overlap_mentioned_p (dest, equiv_mem))
497: || (GET_CODE (dest) == MEM
498: && true_dependence (dest, equiv_mem)))
499: equiv_mem_modified = 1;
500: }
501:
502: /* Verify that no store between START and the death of REG invalidates
503: MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
504: by storing into an overlapping memory location, or with a non-const
505: CALL_INSN.
506:
507: Return 1 if MEMREF remains valid. */
508:
509: static int
510: validate_equiv_mem (start, reg, memref)
511: rtx start;
512: rtx reg;
513: rtx memref;
514: {
515: rtx insn;
516: rtx note;
517:
518: equiv_mem = memref;
519: equiv_mem_modified = 0;
520:
521: /* If the memory reference has side effects or is volatile, it isn't a
522: valid equivalence. */
523: if (side_effects_p (memref))
524: return 0;
525:
526: for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
527: {
528: if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
529: continue;
530:
531: if (find_reg_note (insn, REG_DEAD, reg))
532: return 1;
533:
534: if (GET_CODE (insn) == CALL_INSN && ! RTX_UNCHANGING_P (memref)
535: && ! CONST_CALL_P (insn))
536: return 0;
537:
538: note_stores (PATTERN (insn), validate_equiv_mem_from_store);
539:
540: /* If a register mentioned in MEMREF is modified via an
541: auto-increment, we lose the equivalence. Do the same if one
542: dies; although we could extend the life, it doesn't seem worth
543: the trouble. */
544:
545: for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
546: if ((REG_NOTE_KIND (note) == REG_INC
547: || REG_NOTE_KIND (note) == REG_DEAD)
548: && GET_CODE (XEXP (note, 0)) == REG
549: && reg_overlap_mentioned_p (XEXP (note, 0), memref))
550: return 0;
551: }
552:
553: return 0;
554: }
555:
556: /* TRUE if X references a memory location that would be affected by a store
557: to MEMREF. */
558:
559: static int
560: memref_referenced_p (memref, x)
561: rtx x;
562: rtx memref;
563: {
564: int i, j;
565: char *fmt;
566: enum rtx_code code = GET_CODE (x);
567:
568: switch (code)
569: {
570: case REG:
571: case CONST_INT:
572: case CONST:
573: case LABEL_REF:
574: case SYMBOL_REF:
575: case CONST_DOUBLE:
576: case PC:
577: case CC0:
578: case HIGH:
579: case LO_SUM:
580: return 0;
581:
582: case MEM:
583: if (true_dependence (memref, x))
584: return 1;
585: break;
586:
587: case SET:
588: /* If we are setting a MEM, it doesn't count (its address does), but any
589: other SET_DEST that has a MEM in it is referencing the MEM. */
590: if (GET_CODE (SET_DEST (x)) == MEM)
591: {
592: if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
593: return 1;
594: }
595: else if (memref_referenced_p (memref, SET_DEST (x)))
596: return 1;
597:
598: return memref_referenced_p (memref, SET_SRC (x));
599: }
600:
601: fmt = GET_RTX_FORMAT (code);
602: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
603: switch (fmt[i])
604: {
605: case 'e':
606: if (memref_referenced_p (memref, XEXP (x, i)))
607: return 1;
608: break;
609: case 'E':
610: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
611: if (memref_referenced_p (memref, XVECEXP (x, i, j)))
612: return 1;
613: break;
614: }
615:
616: return 0;
617: }
618:
619: /* TRUE if some insn in the range (START, END] references a memory location
620: that would be affected by a store to MEMREF. */
621:
622: static int
623: memref_used_between_p (memref, start, end)
624: rtx memref;
625: rtx start;
626: rtx end;
627: {
628: rtx insn;
629:
630: for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
631: insn = NEXT_INSN (insn))
632: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
633: && memref_referenced_p (memref, PATTERN (insn)))
634: return 1;
635:
636: return 0;
637: }
638:
639: /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
640: in INSN.
641:
642: Search forward to see if SRC dies before either it or DEST is modified,
643: but don't scan past the end of a basic block. If so, we can replace SRC
644: with DEST and let SRC die in INSN.
645:
646: This will reduce the number of registers live in that range and may enable
647: DEST to be tied to SRC, thus often saving one register in addition to a
648: register-register copy. */
649:
650: static void
1.1.1.2 root 651: optimize_reg_copy_1 (insn, dest, src)
1.1 root 652: rtx insn;
653: rtx dest;
654: rtx src;
655: {
656: rtx p, q;
657: rtx note;
658: rtx dest_death = 0;
659: int sregno = REGNO (src);
660: int dregno = REGNO (dest);
661:
662: if (sregno == dregno
663: #ifdef SMALL_REGISTER_CLASSES
664: /* We don't want to mess with hard regs if register classes are small. */
665: || sregno < FIRST_PSEUDO_REGISTER || dregno < FIRST_PSEUDO_REGISTER
666: #endif
667: /* We don't see all updates to SP if they are in an auto-inc memory
668: reference, so we must disallow this optimization on them. */
669: || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
670: return;
671:
672: for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
673: {
674: if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
675: || (GET_CODE (p) == NOTE
676: && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG
677: || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)))
678: break;
679:
680: if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
681: continue;
682:
683: if (reg_set_p (src, p) || reg_set_p (dest, p)
684: /* Don't change a USE of a register. */
685: || (GET_CODE (PATTERN (p)) == USE
686: && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
687: break;
688:
1.1.1.4 ! root 689: /* See if all of SRC dies in P. This test is slightly more
! 690: conservative than it needs to be. */
! 691: if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
! 692: && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
1.1 root 693: {
694: int failed = 0;
695: int length = 0;
1.1.1.4 ! root 696: int d_length = 0;
1.1 root 697: int n_calls = 0;
1.1.1.4 ! root 698: int d_n_calls = 0;
! 699:
! 700: /* If P is a CALL_INSN, SRC crosses one more call, since it
! 701: used to die there. */
! 702:
! 703: if (GET_CODE (p) == CALL_INSN)
! 704: n_calls++;
1.1 root 705:
706: /* We can do the optimization. Scan forward from INSN again,
707: replacing regs as we go. Set FAILED if a replacement can't
708: be done. In that case, we can't move the death note for SRC.
709: This should be rare. */
710:
711: /* Set to stop at next insn. */
712: for (q = next_real_insn (insn);
713: q != next_real_insn (p);
714: q = next_real_insn (q))
715: {
1.1.1.4 ! root 716: if (reg_overlap_mentioned_p (src, PATTERN (q)))
1.1 root 717: {
1.1.1.4 ! root 718: /* If SRC is a hard register, we might miss some
! 719: overlapping registers with validate_replace_rtx,
! 720: so we would have to undo it. We can't if DEST is
! 721: present in the insn, so fail in that combination
! 722: of cases. */
! 723: if (sregno < FIRST_PSEUDO_REGISTER
! 724: && reg_mentioned_p (dest, PATTERN (q)))
! 725: failed = 1;
! 726:
! 727: /* Replace all uses and make sure that the register
! 728: isn't still present. */
! 729: else if (validate_replace_rtx (src, dest, q)
! 730: && (sregno >= FIRST_PSEUDO_REGISTER
! 731: || ! reg_overlap_mentioned_p (src,
! 732: PATTERN (q))))
1.1 root 733: {
734: /* We assume that a register is used exactly once per
735: insn in the updates below. If this is not correct,
736: no great harm is done. */
737: if (sregno >= FIRST_PSEUDO_REGISTER)
738: reg_n_refs[sregno] -= loop_depth;
739: if (dregno >= FIRST_PSEUDO_REGISTER)
740: reg_n_refs[dregno] += loop_depth;
741: }
742: else
1.1.1.4 ! root 743: {
! 744: validate_replace_rtx (dest, src, q);
! 745: failed = 1;
! 746: }
1.1 root 747: }
748:
749: /* Count the insns and CALL_INSNs passed. If we passed the
750: death note of DEST, show increased live length. */
751: length++;
752: if (dest_death)
1.1.1.4 ! root 753: d_length++;
1.1 root 754:
755: if (GET_CODE (q) == CALL_INSN)
756: {
757: n_calls++;
758: if (dest_death)
1.1.1.4 ! root 759: d_n_calls++;
1.1 root 760: }
761:
762: /* If DEST dies here, remove the death note and save it for
1.1.1.4 ! root 763: later. Make sure ALL of DEST dies here; again, this is
! 764: overly conservative. */
1.1 root 765: if (dest_death == 0
1.1.1.4 ! root 766: && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0
! 767: && GET_MODE (XEXP (dest_death, 0)) == GET_MODE (dest))
1.1 root 768: remove_note (q, dest_death);
769: }
770:
771: if (! failed)
772: {
773: if (sregno >= FIRST_PSEUDO_REGISTER)
774: {
775: reg_live_length[sregno] -= length;
776: reg_n_calls_crossed[sregno] -= n_calls;
777: }
778:
1.1.1.4 ! root 779: if (dregno >= FIRST_PSEUDO_REGISTER)
! 780: {
! 781: reg_live_length[dregno] += d_length;
! 782: reg_n_calls_crossed[dregno] += d_n_calls;
! 783: }
! 784:
1.1 root 785: /* Move death note of SRC from P to INSN. */
786: remove_note (p, note);
787: XEXP (note, 1) = REG_NOTES (insn);
788: REG_NOTES (insn) = note;
789: }
790:
791: /* Put death note of DEST on P if we saw it die. */
792: if (dest_death)
793: {
794: XEXP (dest_death, 1) = REG_NOTES (p);
795: REG_NOTES (p) = dest_death;
796: }
797:
798: return;
799: }
1.1.1.4 ! root 800:
! 801: /* If SRC is a hard register which is set or killed in some other
! 802: way, we can't do this optimization. */
! 803: else if (sregno < FIRST_PSEUDO_REGISTER
! 804: && dead_or_set_p (p, src))
! 805: break;
1.1 root 806: }
807: }
1.1.1.2 root 808:
809: /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
810: a sequence of insns that modify DEST followed by an insn that sets
811: SRC to DEST in which DEST dies, with no prior modification of DEST.
812: (There is no need to check if the insns in between actually modify
813: DEST. We should not have cases where DEST is not modified, but
814: the optimization is safe if no such modification is detected.)
815: In that case, we can replace all uses of DEST, starting with INSN and
816: ending with the set of SRC to DEST, with SRC. We do not do this
817: optimization if a CALL_INSN is crossed unless SRC already crosses a
818: call.
819:
820: It is assumed that DEST and SRC are pseudos; it is too complicated to do
821: this for hard registers since the substitutions we may make might fail. */
822:
823: static void
824: optimize_reg_copy_2 (insn, dest, src)
825: rtx insn;
826: rtx dest;
827: rtx src;
828: {
829: rtx p, q;
830: rtx set;
831: int sregno = REGNO (src);
832: int dregno = REGNO (dest);
833:
834: for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
835: {
836: if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
837: || (GET_CODE (p) == NOTE
838: && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG
839: || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)))
840: break;
841:
842: if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
843: continue;
844:
845: set = single_set (p);
846: if (set && SET_SRC (set) == dest && SET_DEST (set) == src
847: && find_reg_note (p, REG_DEAD, dest))
848: {
849: /* We can do the optimization. Scan forward from INSN again,
850: replacing regs as we go. */
851:
852: /* Set to stop at next insn. */
853: for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
854: if (GET_RTX_CLASS (GET_CODE (q)) == 'i')
855: {
856: if (reg_mentioned_p (dest, PATTERN (q)))
857: {
858: PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
859:
860: /* We assume that a register is used exactly once per
861: insn in the updates below. If this is not correct,
862: no great harm is done. */
1.1.1.4 ! root 863: reg_n_refs[dregno] -= loop_depth;
! 864: reg_n_refs[sregno] += loop_depth;
1.1.1.2 root 865: }
866:
867:
868: if (GET_CODE (q) == CALL_INSN)
869: {
870: reg_n_calls_crossed[dregno]--;
871: reg_n_calls_crossed[sregno]++;
872: }
873: }
874:
875: remove_note (p, find_reg_note (p, REG_DEAD, dest));
876: reg_n_deaths[dregno]--;
877: remove_note (insn, find_reg_note (insn, REG_DEAD, src));
878: reg_n_deaths[sregno]--;
879: return;
880: }
881:
882: if (reg_set_p (src, p)
883: || (GET_CODE (p) == CALL_INSN && reg_n_calls_crossed[sregno] == 0))
884: break;
885: }
886: }
1.1 root 887:
888: /* Find registers that are equivalent to a single value throughout the
889: compilation (either because they can be referenced in memory or are set once
890: from a single constant). Lower their priority for a register.
891:
892: If such a register is only referenced once, try substituting its value
893: into the using insn. If it succeeds, we can eliminate the register
894: completely. */
895:
896: static void
897: update_equiv_regs ()
898: {
899: rtx *reg_equiv_init_insn = (rtx *) alloca (max_regno * sizeof (rtx *));
900: rtx *reg_equiv_replacement = (rtx *) alloca (max_regno * sizeof (rtx *));
901: rtx insn;
902:
903: bzero (reg_equiv_init_insn, max_regno * sizeof (rtx *));
904: bzero (reg_equiv_replacement, max_regno * sizeof (rtx *));
905:
906: init_alias_analysis ();
907:
908: loop_depth = 1;
909:
910: /* Scan the insns and find which registers have equivalences. Do this
911: in a separate scan of the insns because (due to -fcse-follow-jumps)
912: a register can be set below its use. */
913: for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
914: {
915: rtx note;
916: rtx set = single_set (insn);
917: rtx dest;
918: int regno;
919:
920: if (GET_CODE (insn) == NOTE)
921: {
922: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
923: loop_depth++;
924: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
925: loop_depth--;
926: }
927:
928: /* If this insn contains more (or less) than a single SET, ignore it. */
929: if (set == 0)
930: continue;
931:
932: dest = SET_DEST (set);
933:
934: /* If this sets a MEM to the contents of a REG that is only used
935: in a single basic block, see if the register is always equivalent
936: to that memory location and if moving the store from INSN to the
937: insn that set REG is safe. If so, put a REG_EQUIV note on the
938: initializing insn. */
939:
940: if (GET_CODE (dest) == MEM && GET_CODE (SET_SRC (set)) == REG
941: && (regno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
942: && reg_basic_block[regno] >= 0
943: && reg_equiv_init_insn[regno] != 0
944: && validate_equiv_mem (reg_equiv_init_insn[regno], SET_SRC (set),
945: dest)
946: && ! memref_used_between_p (SET_DEST (set),
947: reg_equiv_init_insn[regno], insn))
948: REG_NOTES (reg_equiv_init_insn[regno])
949: = gen_rtx (EXPR_LIST, REG_EQUIV, dest,
950: REG_NOTES (reg_equiv_init_insn[regno]));
951:
952: /* If this is a register-register copy where SRC is not dead, see if we
953: can optimize it. */
954: if (flag_expensive_optimizations && GET_CODE (dest) == REG
955: && GET_CODE (SET_SRC (set)) == REG
956: && ! find_reg_note (insn, REG_DEAD, SET_SRC (set)))
1.1.1.2 root 957: optimize_reg_copy_1 (insn, dest, SET_SRC (set));
958:
959: /* Similarly for a pseudo-pseudo copy when SRC is dead. */
960: else if (flag_expensive_optimizations && GET_CODE (dest) == REG
961: && REGNO (dest) >= FIRST_PSEUDO_REGISTER
962: && GET_CODE (SET_SRC (set)) == REG
963: && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
964: && find_reg_note (insn, REG_DEAD, SET_SRC (set)))
965: optimize_reg_copy_2 (insn, dest, SET_SRC (set));
1.1 root 966:
967: /* Otherwise, we only handle the case of a pseudo register being set
968: once. */
969: if (GET_CODE (dest) != REG
970: || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
971: || reg_n_sets[regno] != 1)
972: continue;
973:
1.1.1.4 ! root 974: note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1.1 root 975:
976: /* Record this insn as initializing this register. */
977: reg_equiv_init_insn[regno] = insn;
978:
979: /* If this register is known to be equal to a constant, record that
980: it is always equivalent to the constant. */
981: if (note && CONSTANT_P (XEXP (note, 0)))
982: PUT_MODE (note, (enum machine_mode) REG_EQUIV);
983:
984: /* If this insn introduces a "constant" register, decrease the priority
985: of that register. Record this insn if the register is only used once
986: more and the equivalence value is the same as our source.
987:
988: The latter condition is checked for two reasons: First, it is an
989: indication that it may be more efficient to actually emit the insn
990: as written (if no registers are available, reload will substitute
991: the equivalence). Secondly, it avoids problems with any registers
992: dying in this insn whose death notes would be missed.
993:
994: If we don't have a REG_EQUIV note, see if this insn is loading
995: a register used only in one basic block from a MEM. If so, and the
996: MEM remains unchanged for the life of the register, add a REG_EQUIV
997: note. */
998:
1.1.1.4 ! root 999: note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
1.1 root 1000:
1001: if (note == 0 && reg_basic_block[regno] >= 0
1002: && GET_CODE (SET_SRC (set)) == MEM
1003: && validate_equiv_mem (insn, dest, SET_SRC (set)))
1004: REG_NOTES (insn) = note = gen_rtx (EXPR_LIST, REG_EQUIV, SET_SRC (set),
1005: REG_NOTES (insn));
1006:
1007: /* Don't mess with things live during setjmp. */
1008: if (note && reg_live_length[regno] >= 0)
1009: {
1010: int regno = REGNO (dest);
1011:
1012: /* Note that the statement below does not affect the priority
1013: in local-alloc! */
1014: reg_live_length[regno] *= 2;
1015:
1016: /* If the register is referenced exactly twice, meaning it is set
1017: once and used once, indicate that the reference may be replaced
1018: by the equivalence we computed above. If the register is only
1019: used in one basic block, this can't succeed or combine would
1020: have done it.
1021:
1022: It would be nice to use "loop_depth * 2" in the compare
1023: below. Unfortunately, LOOP_DEPTH need not be constant within
1024: a basic block so this would be too complicated.
1025:
1026: This case normally occurs when a parameter is read from memory
1027: and then used exactly once, not in a loop. */
1028:
1029: if (reg_n_refs[regno] == 2
1030: && reg_basic_block[regno] < 0
1031: && rtx_equal_p (XEXP (note, 0), SET_SRC (set)))
1032: reg_equiv_replacement[regno] = SET_SRC (set);
1033: }
1034: }
1035:
1036: /* Now scan all regs killed in an insn to see if any of them are registers
1037: only used that once. If so, see if we can replace the reference with
1038: the equivalent from. If we can, delete the initializing reference
1039: and this register will go away. */
1040: for (insn = next_active_insn (get_insns ());
1041: insn;
1042: insn = next_active_insn (insn))
1043: {
1044: rtx link;
1045:
1046: for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1047: if (REG_NOTE_KIND (link) == REG_DEAD
1048: /* Make sure this insn still refers to the register. */
1049: && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
1050: {
1051: int regno = REGNO (XEXP (link, 0));
1052:
1053: if (reg_equiv_replacement[regno]
1054: && validate_replace_rtx (regno_reg_rtx[regno],
1055: reg_equiv_replacement[regno], insn))
1056: {
1057: rtx equiv_insn = reg_equiv_init_insn[regno];
1058:
1059: remove_death (regno, insn);
1060: reg_n_refs[regno] = 0;
1061: PUT_CODE (equiv_insn, NOTE);
1062: NOTE_LINE_NUMBER (equiv_insn) = NOTE_INSN_DELETED;
1063: NOTE_SOURCE_FILE (equiv_insn) = 0;
1064: }
1065: }
1066: }
1067: }
1068:
1069: /* Allocate hard regs to the pseudo regs used only within block number B.
1070: Only the pseudos that die but once can be handled. */
1071:
1072: static void
1073: block_alloc (b)
1074: int b;
1075: {
1076: register int i, q;
1077: register rtx insn;
1078: rtx note;
1079: int insn_number = 0;
1080: int insn_count = 0;
1081: int max_uid = get_max_uid ();
1082: short *qty_order;
1083: int no_conflict_combined_regno = -1;
1084:
1085: /* Count the instructions in the basic block. */
1086:
1087: insn = basic_block_end[b];
1088: while (1)
1089: {
1090: if (GET_CODE (insn) != NOTE)
1091: if (++insn_count > max_uid)
1092: abort ();
1093: if (insn == basic_block_head[b])
1094: break;
1095: insn = PREV_INSN (insn);
1096: }
1097:
1098: /* +2 to leave room for a post_mark_life at the last insn and for
1099: the birth of a CLOBBER in the first insn. */
1100: regs_live_at = (HARD_REG_SET *) alloca ((2 * insn_count + 2)
1101: * sizeof (HARD_REG_SET));
1102: bzero (regs_live_at, (2 * insn_count + 2) * sizeof (HARD_REG_SET));
1103:
1104: /* Initialize table of hardware registers currently live. */
1105:
1106: #ifdef HARD_REG_SET
1107: regs_live = *basic_block_live_at_start[b];
1108: #else
1109: COPY_HARD_REG_SET (regs_live, basic_block_live_at_start[b]);
1110: #endif
1111:
1112: /* This loop scans the instructions of the basic block
1113: and assigns quantities to registers.
1114: It computes which registers to tie. */
1115:
1116: insn = basic_block_head[b];
1117: while (1)
1118: {
1119: register rtx body = PATTERN (insn);
1120:
1121: if (GET_CODE (insn) != NOTE)
1122: insn_number++;
1123:
1124: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1125: {
1126: register rtx link, set;
1127: register int win = 0;
1128: register rtx r0, r1;
1129: int combined_regno = -1;
1130: int i;
1131: int insn_code_number = recog_memoized (insn);
1132:
1133: this_insn_number = insn_number;
1134: this_insn = insn;
1135:
1136: if (insn_code_number >= 0)
1137: insn_extract (insn);
1138: which_alternative = -1;
1139:
1140: /* Is this insn suitable for tying two registers?
1141: If so, try doing that.
1142: Suitable insns are those with at least two operands and where
1143: operand 0 is an output that is a register that is not
1144: earlyclobber.
1145: For a commutative operation, try (set reg0 (arithop ... reg1)).
1146: Subregs in place of regs are also ok.
1147:
1148: If tying is done, WIN is set nonzero. */
1149:
1150: if (insn_code_number >= 0
1.1.1.4 ! root 1151: #ifdef REGISTER_CONSTRAINTS
1.1 root 1152: && insn_n_operands[insn_code_number] > 1
1153: && insn_operand_constraint[insn_code_number][0][0] == '='
1.1.1.4 ! root 1154: && insn_operand_constraint[insn_code_number][0][1] != '&'
! 1155: #else
! 1156: && GET_CODE (PATTERN (insn)) == SET
! 1157: && rtx_equal_p (SET_DEST (PATTERN (insn)), recog_operand[0])
! 1158: #endif
! 1159: )
1.1 root 1160: {
1161: r0 = recog_operand[0];
1162: r1 = recog_operand[1];
1163:
1164: /* If the first operand is an address, find a register in it.
1165: There may be more than one register, but we only try one of
1166: them. */
1.1.1.4 ! root 1167: if (
! 1168: #ifdef REGISTER_CONSTRAINTS
! 1169: insn_operand_constraint[insn_code_number][1][0] == 'p'
! 1170: #else
! 1171: insn_operand_address_p[insn_code_number][1]
! 1172: #endif
! 1173: )
1.1 root 1174: while (GET_CODE (r1) == PLUS || GET_CODE (r1) == MULT)
1175: r1 = XEXP (r1, 0);
1176:
1177: if (GET_CODE (r0) == REG || GET_CODE (r0) == SUBREG)
1178: {
1.1.1.3 root 1179: /* We have two priorities for hard register preferences.
1.1 root 1180: If we have a move insn or an insn whose first input can
1181: only be in the same register as the output, give
1182: priority to an equivalence found from that insn. */
1.1.1.4 ! root 1183: #ifdef REGISTER_CONSTRAINTS
1.1 root 1184: int may_save_copy
1185: = ((SET_DEST (body) == r0 && SET_SRC (body) == r1)
1186: || (r1 == recog_operand[1]
1187: && (requires_inout_p (insn_operand_constraint[insn_code_number][1]))));
1.1.1.4 ! root 1188: #else
! 1189: int may_save_copy = 0;
! 1190: #endif
1.1 root 1191:
1192: if (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG)
1193: win = combine_regs (r1, r0, may_save_copy,
1194: insn_number, insn, 0);
1195:
1196: if (win == 0
1197: && insn_n_operands[insn_code_number] > 2
1.1.1.4 ! root 1198: #ifdef REGISTER_CONSTRAINTS
1.1 root 1199: && insn_operand_constraint[insn_code_number][1][0] == '%'
1.1.1.4 ! root 1200: #else
! 1201: && GET_CODE (PATTERN (insn)) == SET
! 1202: && (GET_RTX_CLASS (GET_CODE (SET_SRC (PATTERN (insn))))
! 1203: == 'c')
! 1204: && rtx_equal_p (recog_operand[2],
! 1205: XEXP (SET_SRC (PATTERN (insn)), 0))
! 1206: #endif
1.1 root 1207: && (r1 = recog_operand[2],
1208: GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG))
1209: win = combine_regs (r1, r0, may_save_copy,
1210: insn_number, insn, 0);
1211: }
1212: }
1213:
1214: /* Recognize an insn sequence with an ultimate result
1215: which can safely overlap one of the inputs.
1216: The sequence begins with a CLOBBER of its result,
1217: and ends with an insn that copies the result to itself
1218: and has a REG_EQUAL note for an equivalent formula.
1219: That note indicates what the inputs are.
1220: The result and the input can overlap if each insn in
1221: the sequence either doesn't mention the input
1222: or has a REG_NO_CONFLICT note to inhibit the conflict.
1223:
1224: We do the combining test at the CLOBBER so that the
1225: destination register won't have had a quantity number
1226: assigned, since that would prevent combining. */
1227:
1228: if (GET_CODE (PATTERN (insn)) == CLOBBER
1229: && (r0 = XEXP (PATTERN (insn), 0),
1230: GET_CODE (r0) == REG)
1.1.1.4 ! root 1231: && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1.1 root 1232: && GET_CODE (XEXP (link, 0)) == INSN
1233: && (set = single_set (XEXP (link, 0))) != 0
1234: && SET_DEST (set) == r0 && SET_SRC (set) == r0
1.1.1.4 ! root 1235: && (note = find_reg_note (XEXP (link, 0), REG_EQUAL,
! 1236: NULL_RTX)) != 0)
1.1 root 1237: {
1238: if (r1 = XEXP (note, 0), GET_CODE (r1) == REG
1239: /* Check that we have such a sequence. */
1240: && no_conflict_p (insn, r0, r1))
1241: win = combine_regs (r1, r0, 1, insn_number, insn, 1);
1242: else if (GET_RTX_FORMAT (GET_CODE (XEXP (note, 0)))[0] == 'e'
1243: && (r1 = XEXP (XEXP (note, 0), 0),
1244: GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG)
1245: && no_conflict_p (insn, r0, r1))
1246: win = combine_regs (r1, r0, 0, insn_number, insn, 1);
1247:
1248: /* Here we care if the operation to be computed is
1249: commutative. */
1250: else if ((GET_CODE (XEXP (note, 0)) == EQ
1251: || GET_CODE (XEXP (note, 0)) == NE
1252: || GET_RTX_CLASS (GET_CODE (XEXP (note, 0))) == 'c')
1253: && (r1 = XEXP (XEXP (note, 0), 1),
1254: (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG))
1255: && no_conflict_p (insn, r0, r1))
1256: win = combine_regs (r1, r0, 0, insn_number, insn, 1);
1257:
1258: /* If we did combine something, show the register number
1259: in question so that we know to ignore its death. */
1260: if (win)
1261: no_conflict_combined_regno = REGNO (r1);
1262: }
1263:
1264: /* If registers were just tied, set COMBINED_REGNO
1265: to the number of the register used in this insn
1266: that was tied to the register set in this insn.
1267: This register's qty should not be "killed". */
1268:
1269: if (win)
1270: {
1271: while (GET_CODE (r1) == SUBREG)
1272: r1 = SUBREG_REG (r1);
1273: combined_regno = REGNO (r1);
1274: }
1275:
1276: /* Mark the death of everything that dies in this instruction,
1277: except for anything that was just combined. */
1278:
1279: for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1280: if (REG_NOTE_KIND (link) == REG_DEAD
1281: && GET_CODE (XEXP (link, 0)) == REG
1282: && combined_regno != REGNO (XEXP (link, 0))
1283: && (no_conflict_combined_regno != REGNO (XEXP (link, 0))
1284: || ! find_reg_note (insn, REG_NO_CONFLICT, XEXP (link, 0))))
1285: wipe_dead_reg (XEXP (link, 0), 0);
1286:
1287: /* Allocate qty numbers for all registers local to this block
1288: that are born (set) in this instruction.
1289: A pseudo that already has a qty is not changed. */
1290:
1291: note_stores (PATTERN (insn), reg_is_set);
1292:
1293: /* If anything is set in this insn and then unused, mark it as dying
1294: after this insn, so it will conflict with our outputs. This
1295: can't match with something that combined, and it doesn't matter
1296: if it did. Do this after the calls to reg_is_set since these
1297: die after, not during, the current insn. */
1298:
1299: for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1300: if (REG_NOTE_KIND (link) == REG_UNUSED
1301: && GET_CODE (XEXP (link, 0)) == REG)
1302: wipe_dead_reg (XEXP (link, 0), 1);
1303:
1304: #ifndef SMALL_REGISTER_CLASSES
1305: /* Allocate quantities for any SCRATCH operands of this insn. We
1306: don't do this for machines with small register classes because
1307: those machines can use registers explicitly mentioned in the
1308: RTL as spill registers and our usage of hard registers
1309: explicitly for SCRATCH operands will conflict. On those machines,
1310: reload will allocate the SCRATCH. */
1311:
1312: if (insn_code_number >= 0)
1313: for (i = 0; i < insn_n_operands[insn_code_number]; i++)
1314: if (GET_CODE (recog_operand[i]) == SCRATCH)
1315: alloc_qty_for_scratch (recog_operand[i], i, insn,
1316: insn_code_number, insn_number);
1317: #endif
1318:
1319: /* If this is an insn that has a REG_RETVAL note pointing at a
1320: CLOBBER insn, we have reached the end of a REG_NO_CONFLICT
1321: block, so clear any register number that combined within it. */
1.1.1.4 ! root 1322: if ((note = find_reg_note (insn, REG_RETVAL, NULL_RTX)) != 0
1.1 root 1323: && GET_CODE (XEXP (note, 0)) == INSN
1324: && GET_CODE (PATTERN (XEXP (note, 0))) == CLOBBER)
1325: no_conflict_combined_regno = -1;
1326: }
1327:
1328: /* Set the registers live after INSN_NUMBER. Note that we never
1329: record the registers live before the block's first insn, since no
1330: pseudos we care about are live before that insn. */
1331:
1332: IOR_HARD_REG_SET (regs_live_at[2 * insn_number], regs_live);
1333: IOR_HARD_REG_SET (regs_live_at[2 * insn_number + 1], regs_live);
1334:
1335: if (insn == basic_block_end[b])
1336: break;
1337:
1338: insn = NEXT_INSN (insn);
1339: }
1340:
1341: /* Now every register that is local to this basic block
1342: should have been given a quantity, or else -1 meaning ignore it.
1343: Every quantity should have a known birth and death.
1344:
1345: Order the qtys so we assign them registers in order of
1346: decreasing length of life. Normally call qsort, but if we
1347: have only a very small number of quantities, sort them ourselves. */
1348:
1349: qty_order = (short *) alloca (next_qty * sizeof (short));
1350: for (i = 0; i < next_qty; i++)
1351: qty_order[i] = i;
1352:
1353: #define EXCHANGE(I1, I2) \
1354: { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; }
1355:
1356: switch (next_qty)
1357: {
1358: case 3:
1359: /* Make qty_order[2] be the one to allocate last. */
1360: if (qty_compare (0, 1) > 0)
1361: EXCHANGE (0, 1);
1362: if (qty_compare (1, 2) > 0)
1363: EXCHANGE (2, 1);
1364:
1365: /* ... Fall through ... */
1366: case 2:
1367: /* Put the best one to allocate in qty_order[0]. */
1368: if (qty_compare (0, 1) > 0)
1369: EXCHANGE (0, 1);
1370:
1371: /* ... Fall through ... */
1372:
1373: case 1:
1374: case 0:
1375: /* Nothing to do here. */
1376: break;
1377:
1378: default:
1379: qsort (qty_order, next_qty, sizeof (short), qty_compare_1);
1380: }
1381:
1382: /* Try to put each quantity in a suggested physical register, if it has one.
1383: This may cause registers to be allocated that otherwise wouldn't be, but
1384: this seems acceptable in local allocation (unlike global allocation). */
1385: for (i = 0; i < next_qty; i++)
1386: {
1387: q = qty_order[i];
1388: if (qty_phys_has_sugg[q] || qty_phys_has_copy_sugg[q])
1389: qty_phys_reg[q] = find_free_reg (qty_min_class[q], qty_mode[q], q,
1390: 0, 1, qty_birth[q], qty_death[q]);
1391: else
1392: qty_phys_reg[q] = -1;
1393: }
1394:
1395: /* Now for each qty that is not a hardware register,
1396: look for a hardware register to put it in.
1397: First try the register class that is cheapest for this qty,
1398: if there is more than one class. */
1399:
1400: for (i = 0; i < next_qty; i++)
1401: {
1402: q = qty_order[i];
1403: if (qty_phys_reg[q] < 0)
1404: {
1405: if (N_REG_CLASSES > 1)
1406: {
1407: qty_phys_reg[q] = find_free_reg (qty_min_class[q],
1408: qty_mode[q], q, 0, 0,
1409: qty_birth[q], qty_death[q]);
1410: if (qty_phys_reg[q] >= 0)
1411: continue;
1412: }
1413:
1.1.1.4 ! root 1414: if (qty_alternate_class[q] != NO_REGS)
! 1415: qty_phys_reg[q] = find_free_reg (qty_alternate_class[q],
1.1 root 1416: qty_mode[q], q, 0, 0,
1417: qty_birth[q], qty_death[q]);
1418: }
1419: }
1420:
1421: /* Now propagate the register assignments
1422: to the pseudo regs belonging to the qtys. */
1423:
1424: for (q = 0; q < next_qty; q++)
1425: if (qty_phys_reg[q] >= 0)
1426: {
1427: for (i = qty_first_reg[q]; i >= 0; i = reg_next_in_qty[i])
1428: reg_renumber[i] = qty_phys_reg[q] + reg_offset[i];
1429: if (qty_scratch_rtx[q])
1430: {
1431: PUT_CODE (qty_scratch_rtx[q], REG);
1432: REGNO (qty_scratch_rtx[q]) = qty_phys_reg[q];
1433:
1434: for (i = HARD_REGNO_NREGS (qty_phys_reg[q],
1435: GET_MODE (qty_scratch_rtx[q])) - 1;
1436: i >= 0; i--)
1437: regs_ever_live[qty_phys_reg[q] + i] = 1;
1438:
1439: /* Must clear the USED field, because it will have been set by
1440: copy_rtx_if_shared, but the leaf_register code expects that
1441: it is zero in all REG rtx. copy_rtx_if_shared does not set the
1442: used bit for REGs, but does for SCRATCHes. */
1443: qty_scratch_rtx[q]->used = 0;
1444: }
1445: }
1446: }
1447:
1448: /* Compare two quantities' priority for getting real registers.
1449: We give shorter-lived quantities higher priority.
1.1.1.3 root 1450: Quantities with more references are also preferred, as are quantities that
1451: require multiple registers. This is the identical prioritization as
1.1 root 1452: done by global-alloc.
1453:
1454: We used to give preference to registers with *longer* lives, but using
1455: the same algorithm in both local- and global-alloc can speed up execution
1456: of some programs by as much as a factor of three! */
1457:
1458: static int
1459: qty_compare (q1, q2)
1460: int q1, q2;
1461: {
1462: /* Note that the quotient will never be bigger than
1463: the value of floor_log2 times the maximum number of
1464: times a register can occur in one insn (surely less than 100).
1465: Multiplying this by 10000 can't overflow. */
1466: register int pri1
1467: = (((double) (floor_log2 (qty_n_refs[q1]) * qty_n_refs[q1])
1468: / ((qty_death[q1] - qty_birth[q1]) * qty_size[q1]))
1469: * 10000);
1470: register int pri2
1471: = (((double) (floor_log2 (qty_n_refs[q2]) * qty_n_refs[q2])
1472: / ((qty_death[q2] - qty_birth[q2]) * qty_size[q2]))
1473: * 10000);
1474: return pri2 - pri1;
1475: }
1476:
1477: static int
1478: qty_compare_1 (q1, q2)
1479: short *q1, *q2;
1480: {
1481: register int tem;
1482:
1483: /* Note that the quotient will never be bigger than
1484: the value of floor_log2 times the maximum number of
1485: times a register can occur in one insn (surely less than 100).
1486: Multiplying this by 10000 can't overflow. */
1487: register int pri1
1488: = (((double) (floor_log2 (qty_n_refs[*q1]) * qty_n_refs[*q1])
1489: / ((qty_death[*q1] - qty_birth[*q1]) * qty_size[*q1]))
1490: * 10000);
1491: register int pri2
1492: = (((double) (floor_log2 (qty_n_refs[*q2]) * qty_n_refs[*q2])
1493: / ((qty_death[*q2] - qty_birth[*q2]) * qty_size[*q2]))
1494: * 10000);
1495:
1496: tem = pri2 - pri1;
1497: if (tem != 0) return tem;
1498: /* If qtys are equally good, sort by qty number,
1499: so that the results of qsort leave nothing to chance. */
1500: return *q1 - *q2;
1501: }
1502:
1503: /* Attempt to combine the two registers (rtx's) USEDREG and SETREG.
1504: Returns 1 if have done so, or 0 if cannot.
1505:
1506: Combining registers means marking them as having the same quantity
1507: and adjusting the offsets within the quantity if either of
1508: them is a SUBREG).
1509:
1510: We don't actually combine a hard reg with a pseudo; instead
1511: we just record the hard reg as the suggestion for the pseudo's quantity.
1512: If we really combined them, we could lose if the pseudo lives
1513: across an insn that clobbers the hard reg (eg, movstr).
1514:
1515: ALREADY_DEAD is non-zero if USEDREG is known to be dead even though
1516: there is no REG_DEAD note on INSN. This occurs during the processing
1517: of REG_NO_CONFLICT blocks.
1518:
1519: MAY_SAVE_COPYCOPY is non-zero if this insn is simply copying USEDREG to
1520: SETREG or if the input and output must share a register.
1521: In that case, we record a hard reg suggestion in QTY_PHYS_COPY_SUGG.
1522:
1523: There are elaborate checks for the validity of combining. */
1524:
1525:
1526: static int
1527: combine_regs (usedreg, setreg, may_save_copy, insn_number, insn, already_dead)
1528: rtx usedreg, setreg;
1529: int may_save_copy;
1530: int insn_number;
1531: rtx insn;
1532: int already_dead;
1533: {
1534: register int ureg, sreg;
1535: register int offset = 0;
1536: int usize, ssize;
1537: register int sqty;
1538:
1539: /* Determine the numbers and sizes of registers being used. If a subreg
1.1.1.3 root 1540: is present that does not change the entire register, don't consider
1.1 root 1541: this a copy insn. */
1542:
1543: while (GET_CODE (usedreg) == SUBREG)
1544: {
1545: if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (usedreg))) > UNITS_PER_WORD)
1546: may_save_copy = 0;
1547: offset += SUBREG_WORD (usedreg);
1548: usedreg = SUBREG_REG (usedreg);
1549: }
1550: if (GET_CODE (usedreg) != REG)
1551: return 0;
1552: ureg = REGNO (usedreg);
1553: usize = REG_SIZE (usedreg);
1554:
1555: while (GET_CODE (setreg) == SUBREG)
1556: {
1557: if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (setreg))) > UNITS_PER_WORD)
1558: may_save_copy = 0;
1559: offset -= SUBREG_WORD (setreg);
1560: setreg = SUBREG_REG (setreg);
1561: }
1562: if (GET_CODE (setreg) != REG)
1563: return 0;
1564: sreg = REGNO (setreg);
1565: ssize = REG_SIZE (setreg);
1566:
1567: /* If UREG is a pseudo-register that hasn't already been assigned a
1568: quantity number, it means that it is not local to this block or dies
1569: more than once. In either event, we can't do anything with it. */
1570: if ((ureg >= FIRST_PSEUDO_REGISTER && reg_qty[ureg] < 0)
1571: /* Do not combine registers unless one fits within the other. */
1572: || (offset > 0 && usize + offset > ssize)
1573: || (offset < 0 && usize + offset < ssize)
1574: /* Do not combine with a smaller already-assigned object
1575: if that smaller object is already combined with something bigger. */
1576: || (ssize > usize && ureg >= FIRST_PSEUDO_REGISTER
1577: && usize < qty_size[reg_qty[ureg]])
1578: /* Can't combine if SREG is not a register we can allocate. */
1579: || (sreg >= FIRST_PSEUDO_REGISTER && reg_qty[sreg] == -1)
1580: /* Don't combine with a pseudo mentioned in a REG_NO_CONFLICT note.
1581: These have already been taken care of. This probably wouldn't
1582: combine anyway, but don't take any chances. */
1583: || (ureg >= FIRST_PSEUDO_REGISTER
1584: && find_reg_note (insn, REG_NO_CONFLICT, usedreg))
1585: /* Don't tie something to itself. In most cases it would make no
1586: difference, but it would screw up if the reg being tied to itself
1587: also dies in this insn. */
1588: || ureg == sreg
1589: /* Don't try to connect two different hardware registers. */
1590: || (ureg < FIRST_PSEUDO_REGISTER && sreg < FIRST_PSEUDO_REGISTER)
1591: /* Don't connect two different machine modes if they have different
1592: implications as to which registers may be used. */
1593: || !MODES_TIEABLE_P (GET_MODE (usedreg), GET_MODE (setreg)))
1594: return 0;
1595:
1596: /* Now, if UREG is a hard reg and SREG is a pseudo, record the hard reg in
1597: qty_phys_sugg for the pseudo instead of tying them.
1598:
1599: Return "failure" so that the lifespan of UREG is terminated here;
1600: that way the two lifespans will be disjoint and nothing will prevent
1601: the pseudo reg from being given this hard reg. */
1602:
1603: if (ureg < FIRST_PSEUDO_REGISTER)
1604: {
1605: /* Allocate a quantity number so we have a place to put our
1606: suggestions. */
1607: if (reg_qty[sreg] == -2)
1608: reg_is_born (setreg, 2 * insn_number);
1609:
1610: if (reg_qty[sreg] >= 0)
1611: {
1612: if (may_save_copy)
1613: {
1614: SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg);
1615: qty_phys_has_copy_sugg[reg_qty[sreg]] = 1;
1616: }
1617: else
1618: {
1619: SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg);
1620: qty_phys_has_sugg[reg_qty[sreg]] = 1;
1621: }
1622: }
1623: return 0;
1624: }
1625:
1626: /* Similarly for SREG a hard register and UREG a pseudo register. */
1627:
1628: if (sreg < FIRST_PSEUDO_REGISTER)
1629: {
1630: if (may_save_copy)
1631: {
1632: SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg);
1633: qty_phys_has_copy_sugg[reg_qty[ureg]] = 1;
1634: }
1635: else
1636: {
1637: SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg);
1638: qty_phys_has_sugg[reg_qty[ureg]] = 1;
1639: }
1640: return 0;
1641: }
1642:
1643: /* At this point we know that SREG and UREG are both pseudos.
1644: Do nothing if SREG already has a quantity or is a register that we
1645: don't allocate. */
1646: if (reg_qty[sreg] >= -1
1647: /* If we are not going to let any regs live across calls,
1648: don't tie a call-crossing reg to a non-call-crossing reg. */
1649: || (current_function_has_nonlocal_label
1650: && ((reg_n_calls_crossed[ureg] > 0)
1651: != (reg_n_calls_crossed[sreg] > 0))))
1652: return 0;
1653:
1654: /* We don't already know about SREG, so tie it to UREG
1655: if this is the last use of UREG, provided the classes they want
1656: are compatible. */
1657:
1658: if ((already_dead || find_regno_note (insn, REG_DEAD, ureg))
1659: && reg_meets_class_p (sreg, qty_min_class[reg_qty[ureg]]))
1660: {
1661: /* Add SREG to UREG's quantity. */
1662: sqty = reg_qty[ureg];
1663: reg_qty[sreg] = sqty;
1664: reg_offset[sreg] = reg_offset[ureg] + offset;
1665: reg_next_in_qty[sreg] = qty_first_reg[sqty];
1666: qty_first_reg[sqty] = sreg;
1667:
1668: /* If SREG's reg class is smaller, set qty_min_class[SQTY]. */
1669: update_qty_class (sqty, sreg);
1670:
1671: /* Update info about quantity SQTY. */
1672: qty_n_calls_crossed[sqty] += reg_n_calls_crossed[sreg];
1673: qty_n_refs[sqty] += reg_n_refs[sreg];
1674: if (usize < ssize)
1675: {
1676: register int i;
1677:
1678: for (i = qty_first_reg[sqty]; i >= 0; i = reg_next_in_qty[i])
1679: reg_offset[i] -= offset;
1680:
1681: qty_size[sqty] = ssize;
1682: qty_mode[sqty] = GET_MODE (setreg);
1683: }
1684: }
1685: else
1686: return 0;
1687:
1688: return 1;
1689: }
1690:
1691: /* Return 1 if the preferred class of REG allows it to be tied
1692: to a quantity or register whose class is CLASS.
1693: True if REG's reg class either contains or is contained in CLASS. */
1694:
1695: static int
1696: reg_meets_class_p (reg, class)
1697: int reg;
1698: enum reg_class class;
1699: {
1700: register enum reg_class rclass = reg_preferred_class (reg);
1701: return (reg_class_subset_p (rclass, class)
1702: || reg_class_subset_p (class, rclass));
1703: }
1704:
1705: /* Return 1 if the two specified classes have registers in common.
1706: If CALL_SAVED, then consider only call-saved registers. */
1707:
1708: static int
1709: reg_classes_overlap_p (c1, c2, call_saved)
1710: register enum reg_class c1;
1711: register enum reg_class c2;
1712: int call_saved;
1713: {
1714: HARD_REG_SET c;
1715: int i;
1716:
1717: COPY_HARD_REG_SET (c, reg_class_contents[(int) c1]);
1718: AND_HARD_REG_SET (c, reg_class_contents[(int) c2]);
1719:
1720: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1721: if (TEST_HARD_REG_BIT (c, i)
1722: && (! call_saved || ! call_used_regs[i]))
1723: return 1;
1724:
1725: return 0;
1726: }
1727:
1728: /* Update the class of QTY assuming that REG is being tied to it. */
1729:
1730: static void
1731: update_qty_class (qty, reg)
1732: int qty;
1733: int reg;
1734: {
1735: enum reg_class rclass = reg_preferred_class (reg);
1736: if (reg_class_subset_p (rclass, qty_min_class[qty]))
1737: qty_min_class[qty] = rclass;
1.1.1.4 ! root 1738:
! 1739: rclass = reg_alternate_class (reg);
! 1740: if (reg_class_subset_p (rclass, qty_alternate_class[qty]))
! 1741: qty_alternate_class[qty] = rclass;
1.1 root 1742: }
1743:
1744: /* Handle something which alters the value of an rtx REG.
1745:
1746: REG is whatever is set or clobbered. SETTER is the rtx that
1747: is modifying the register.
1748:
1749: If it is not really a register, we do nothing.
1750: The file-global variables `this_insn' and `this_insn_number'
1751: carry info from `block_alloc'. */
1752:
1753: static void
1754: reg_is_set (reg, setter)
1755: rtx reg;
1756: rtx setter;
1757: {
1758: /* Note that note_stores will only pass us a SUBREG if it is a SUBREG of
1759: a hard register. These may actually not exist any more. */
1760:
1761: if (GET_CODE (reg) != SUBREG
1762: && GET_CODE (reg) != REG)
1763: return;
1764:
1765: /* Mark this register as being born. If it is used in a CLOBBER, mark
1766: it as being born halfway between the previous insn and this insn so that
1767: it conflicts with our inputs but not the outputs of the previous insn. */
1768:
1769: reg_is_born (reg, 2 * this_insn_number - (GET_CODE (setter) == CLOBBER));
1770: }
1771:
1772: /* Handle beginning of the life of register REG.
1773: BIRTH is the index at which this is happening. */
1774:
1775: static void
1776: reg_is_born (reg, birth)
1777: rtx reg;
1778: int birth;
1779: {
1780: register int regno;
1781:
1782: if (GET_CODE (reg) == SUBREG)
1783: regno = REGNO (SUBREG_REG (reg)) + SUBREG_WORD (reg);
1784: else
1785: regno = REGNO (reg);
1786:
1787: if (regno < FIRST_PSEUDO_REGISTER)
1788: {
1789: mark_life (regno, GET_MODE (reg), 1);
1790:
1791: /* If the register was to have been born earlier that the present
1792: insn, mark it as live where it is actually born. */
1793: if (birth < 2 * this_insn_number)
1794: post_mark_life (regno, GET_MODE (reg), 1, birth, 2 * this_insn_number);
1795: }
1796: else
1797: {
1798: if (reg_qty[regno] == -2)
1799: alloc_qty (regno, GET_MODE (reg), PSEUDO_REGNO_SIZE (regno), birth);
1800:
1801: /* If this register has a quantity number, show that it isn't dead. */
1802: if (reg_qty[regno] >= 0)
1803: qty_death[reg_qty[regno]] = -1;
1804: }
1805: }
1806:
1807: /* Record the death of REG in the current insn. If OUTPUT_P is non-zero,
1808: REG is an output that is dying (i.e., it is never used), otherwise it
1.1.1.2 root 1809: is an input (the normal case).
1810: If OUTPUT_P is 1, then we extend the life past the end of this insn. */
1.1 root 1811:
1812: static void
1813: wipe_dead_reg (reg, output_p)
1814: register rtx reg;
1815: int output_p;
1816: {
1817: register int regno = REGNO (reg);
1818:
1.1.1.2 root 1819: /* If this insn has multiple results,
1820: and the dead reg is used in one of the results,
1821: extend its life to after this insn,
1822: so it won't get allocated together with any other result of this insn. */
1823: if (GET_CODE (PATTERN (this_insn)) == PARALLEL
1824: && !single_set (this_insn))
1825: {
1826: int i;
1827: for (i = XVECLEN (PATTERN (this_insn), 0) - 1; i >= 0; i--)
1828: {
1829: rtx set = XVECEXP (PATTERN (this_insn), 0, i);
1830: if (GET_CODE (set) == SET
1831: && GET_CODE (SET_DEST (set)) != REG
1832: && !rtx_equal_p (reg, SET_DEST (set))
1833: && reg_overlap_mentioned_p (reg, SET_DEST (set)))
1834: output_p = 1;
1835: }
1836: }
1837:
1.1 root 1838: if (regno < FIRST_PSEUDO_REGISTER)
1839: {
1840: mark_life (regno, GET_MODE (reg), 0);
1841:
1842: /* If a hard register is dying as an output, mark it as in use at
1843: the beginning of this insn (the above statement would cause this
1844: not to happen). */
1845: if (output_p)
1846: post_mark_life (regno, GET_MODE (reg), 1,
1847: 2 * this_insn_number, 2 * this_insn_number+ 1);
1848: }
1849:
1850: else if (reg_qty[regno] >= 0)
1851: qty_death[reg_qty[regno]] = 2 * this_insn_number + output_p;
1852: }
1853:
1854: /* Find a block of SIZE words of hard regs in reg_class CLASS
1855: that can hold something of machine-mode MODE
1856: (but actually we test only the first of the block for holding MODE)
1857: and still free between insn BORN_INDEX and insn DEAD_INDEX,
1858: and return the number of the first of them.
1859: Return -1 if such a block cannot be found.
1860: If QTY crosses calls, insist on a register preserved by calls,
1861: unless ACCEPT_CALL_CLOBBERED is nonzero.
1862:
1863: If JUST_TRY_SUGGESTED is non-zero, only try to see if the suggested
1864: register is available. If not, return -1. */
1865:
1866: static int
1867: find_free_reg (class, mode, qty, accept_call_clobbered, just_try_suggested,
1868: born_index, dead_index)
1869: enum reg_class class;
1870: enum machine_mode mode;
1871: int accept_call_clobbered;
1872: int just_try_suggested;
1873: int qty;
1874: int born_index, dead_index;
1875: {
1876: register int i, ins;
1877: #ifdef HARD_REG_SET
1878: register /* Declare it register if it's a scalar. */
1879: #endif
1880: HARD_REG_SET used, first_used;
1881: #ifdef ELIMINABLE_REGS
1882: static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
1883: #endif
1884:
1885: /* Validate our parameters. */
1886: if (born_index < 0 || born_index > dead_index)
1887: abort ();
1888:
1889: /* Don't let a pseudo live in a reg across a function call
1890: if we might get a nonlocal goto. */
1891: if (current_function_has_nonlocal_label
1892: && qty_n_calls_crossed[qty] > 0)
1893: return -1;
1894:
1895: if (accept_call_clobbered)
1896: COPY_HARD_REG_SET (used, call_fixed_reg_set);
1897: else if (qty_n_calls_crossed[qty] == 0)
1898: COPY_HARD_REG_SET (used, fixed_reg_set);
1899: else
1900: COPY_HARD_REG_SET (used, call_used_reg_set);
1901:
1902: for (ins = born_index; ins < dead_index; ins++)
1903: IOR_HARD_REG_SET (used, regs_live_at[ins]);
1904:
1905: IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]);
1906:
1907: /* Don't use the frame pointer reg in local-alloc even if
1908: we may omit the frame pointer, because if we do that and then we
1909: need a frame pointer, reload won't know how to move the pseudo
1910: to another hard reg. It can move only regs made by global-alloc.
1911:
1912: This is true of any register that can be eliminated. */
1913: #ifdef ELIMINABLE_REGS
1914: for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
1915: SET_HARD_REG_BIT (used, eliminables[i].from);
1916: #else
1917: SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM);
1918: #endif
1919:
1920: /* Normally, the registers that can be used for the first register in
1921: a multi-register quantity are the same as those that can be used for
1922: subsequent registers. However, if just trying suggested registers,
1923: restrict our consideration to them. If there are copy-suggested
1924: register, try them. Otherwise, try the arithmetic-suggested
1925: registers. */
1926: COPY_HARD_REG_SET (first_used, used);
1927:
1928: if (just_try_suggested)
1929: {
1930: if (qty_phys_has_copy_sugg[qty])
1931: IOR_COMPL_HARD_REG_SET (first_used, qty_phys_copy_sugg[qty]);
1932: else
1933: IOR_COMPL_HARD_REG_SET (first_used, qty_phys_sugg[qty]);
1934: }
1935:
1936: /* If all registers are excluded, we can't do anything. */
1937: GO_IF_HARD_REG_SUBSET (reg_class_contents[(int) ALL_REGS], first_used, fail);
1938:
1939: /* If at least one would be suitable, test each hard reg. */
1940:
1941: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1942: {
1943: #ifdef REG_ALLOC_ORDER
1944: int regno = reg_alloc_order[i];
1945: #else
1946: int regno = i;
1947: #endif
1948: if (! TEST_HARD_REG_BIT (first_used, regno)
1949: && HARD_REGNO_MODE_OK (regno, mode))
1950: {
1951: register int j;
1952: register int size1 = HARD_REGNO_NREGS (regno, mode);
1953: for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++);
1954: if (j == size1)
1955: {
1956: /* Mark that this register is in use between its birth and death
1957: insns. */
1958: post_mark_life (regno, mode, 1, born_index, dead_index);
1959: return regno;
1960: }
1961: #ifndef REG_ALLOC_ORDER
1962: i += j; /* Skip starting points we know will lose */
1963: #endif
1964: }
1965: }
1966:
1967: fail:
1968:
1969: /* If we are just trying suggested register, we have just tried copy-
1970: suggested registers, and there are arithmetic-suggested registers,
1971: try them. */
1972:
1973: /* If it would be profitable to allocate a call-clobbered register
1974: and save and restore it around calls, do that. */
1975: if (just_try_suggested && qty_phys_has_copy_sugg[qty]
1976: && qty_phys_has_sugg[qty])
1977: {
1978: /* Don't try the copy-suggested regs again. */
1979: qty_phys_has_copy_sugg[qty] = 0;
1980: return find_free_reg (class, mode, qty, accept_call_clobbered, 1,
1981: born_index, dead_index);
1982: }
1983:
1984: if (! accept_call_clobbered
1985: && flag_caller_saves
1986: && ! just_try_suggested
1987: && qty_n_calls_crossed[qty] != 0
1988: && CALLER_SAVE_PROFITABLE (qty_n_refs[qty], qty_n_calls_crossed[qty]))
1989: {
1990: i = find_free_reg (class, mode, qty, 1, 0, born_index, dead_index);
1991: if (i >= 0)
1992: caller_save_needed = 1;
1993: return i;
1994: }
1995: return -1;
1996: }
1997:
1998: /* Mark that REGNO with machine-mode MODE is live starting from the current
1999: insn (if LIFE is non-zero) or dead starting at the current insn (if LIFE
2000: is zero). */
2001:
2002: static void
2003: mark_life (regno, mode, life)
2004: register int regno;
2005: enum machine_mode mode;
2006: int life;
2007: {
2008: register int j = HARD_REGNO_NREGS (regno, mode);
2009: if (life)
2010: while (--j >= 0)
2011: SET_HARD_REG_BIT (regs_live, regno + j);
2012: else
2013: while (--j >= 0)
2014: CLEAR_HARD_REG_BIT (regs_live, regno + j);
2015: }
2016:
2017: /* Mark register number REGNO (with machine-mode MODE) as live (if LIFE
2018: is non-zero) or dead (if LIFE is zero) from insn number BIRTH (inclusive)
2019: to insn number DEATH (exclusive). */
2020:
2021: static void
2022: post_mark_life (regno, mode, life, birth, death)
2023: register int regno, life, birth;
2024: enum machine_mode mode;
2025: int death;
2026: {
2027: register int j = HARD_REGNO_NREGS (regno, mode);
2028: #ifdef HARD_REG_SET
2029: register /* Declare it register if it's a scalar. */
2030: #endif
2031: HARD_REG_SET this_reg;
2032:
2033: CLEAR_HARD_REG_SET (this_reg);
2034: while (--j >= 0)
2035: SET_HARD_REG_BIT (this_reg, regno + j);
2036:
2037: if (life)
2038: while (birth < death)
2039: {
2040: IOR_HARD_REG_SET (regs_live_at[birth], this_reg);
2041: birth++;
2042: }
2043: else
2044: while (birth < death)
2045: {
2046: AND_COMPL_HARD_REG_SET (regs_live_at[birth], this_reg);
2047: birth++;
2048: }
2049: }
2050:
2051: /* INSN is the CLOBBER insn that starts a REG_NO_NOCONFLICT block, R0
2052: is the register being clobbered, and R1 is a register being used in
2053: the equivalent expression.
2054:
2055: If R1 dies in the block and has a REG_NO_CONFLICT note on every insn
2056: in which it is used, return 1.
2057:
2058: Otherwise, return 0. */
2059:
2060: static int
2061: no_conflict_p (insn, r0, r1)
2062: rtx insn, r0, r1;
2063: {
2064: int ok = 0;
1.1.1.4 ! root 2065: rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
1.1 root 2066: rtx p, last;
2067:
2068: /* If R1 is a hard register, return 0 since we handle this case
2069: when we scan the insns that actually use it. */
2070:
2071: if (note == 0
2072: || (GET_CODE (r1) == REG && REGNO (r1) < FIRST_PSEUDO_REGISTER)
2073: || (GET_CODE (r1) == SUBREG && GET_CODE (SUBREG_REG (r1)) == REG
2074: && REGNO (SUBREG_REG (r1)) < FIRST_PSEUDO_REGISTER))
2075: return 0;
2076:
2077: last = XEXP (note, 0);
2078:
2079: for (p = NEXT_INSN (insn); p && p != last; p = NEXT_INSN (p))
2080: if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
2081: {
2082: if (find_reg_note (p, REG_DEAD, r1))
2083: ok = 1;
2084:
2085: if (reg_mentioned_p (r1, PATTERN (p))
2086: && ! find_reg_note (p, REG_NO_CONFLICT, r1))
2087: return 0;
2088: }
2089:
2090: return ok;
2091: }
2092:
1.1.1.4 ! root 2093: #ifdef REGISTER_CONSTRAINTS
! 2094:
1.1 root 2095: /* Return 1 if the constraint string P indicates that the a the operand
2096: must be equal to operand 0 and that no register is acceptable. */
2097:
2098: static int
2099: requires_inout_p (p)
2100: char *p;
2101: {
2102: char c;
2103: int found_zero = 0;
2104:
2105: while (c = *p++)
2106: switch (c)
2107: {
2108: case '0':
2109: found_zero = 1;
2110: break;
2111:
2112: case '=': case '+': case '?':
2113: case '#': case '&': case '!':
2114: case '*': case '%': case ',':
2115: case '1': case '2': case '3': case '4':
2116: case 'm': case '<': case '>': case 'V': case 'o':
2117: case 'E': case 'F': case 'G': case 'H':
2118: case 's': case 'i': case 'n':
2119: case 'I': case 'J': case 'K': case 'L':
2120: case 'M': case 'N': case 'O': case 'P':
2121: #ifdef EXTRA_CONSTRAINT
2122: case 'Q': case 'R': case 'S': case 'T': case 'U':
2123: #endif
2124: case 'X':
2125: /* These don't say anything we care about. */
2126: break;
2127:
2128: case 'p':
2129: case 'g': case 'r':
2130: default:
2131: /* These mean a register is allowed. Fail if so. */
2132: return 0;
2133: }
2134:
2135: return found_zero;
2136: }
1.1.1.4 ! root 2137: #endif /* REGISTER_CONSTRAINTS */
1.1 root 2138:
2139: void
2140: dump_local_alloc (file)
2141: FILE *file;
2142: {
2143: register int i;
2144: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2145: if (reg_renumber[i] != -1)
2146: fprintf (file, ";; Register %d in %d.\n", i, reg_renumber[i]);
2147: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.