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