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