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