![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to reload1.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / cmd / gcc|
Return to reload1.c CVS log | Up to [Research Unix] / researchv10dc / cmd / gcc |
1.1 root 1: /* Reload pseudo regs into hard regs for insns that require hard regs.
2: Copyright (C) 1987, 1988 Free Software Foundation, Inc.
3:
4: This file is part of GNU CC.
5:
6: GNU CC is distributed in the hope that it will be useful,
7: but WITHOUT ANY WARRANTY. No author or distributor
8: accepts responsibility to anyone for the consequences of using it
9: or for whether it serves any particular purpose or works at all,
10: unless he says so in writing. Refer to the GNU CC General Public
11: License for full details.
12:
13: Everyone is granted permission to copy, modify and redistribute
14: GNU CC, but only under the conditions described in the
15: GNU CC General Public License. A copy of this license is
16: supposed to have been given to you along with GNU CC so you
17: can know your rights and responsibilities. It should be in a
18: file named COPYING. Among other things, the copyright notice
19: and this notice must be preserved on all copies. */
20:
21:
22: #include "config.h"
23: #include "rtl.h"
24: #include "flags.h"
25: #include "regs.h"
26: #include "hard-reg-set.h"
27: #include "reload.h"
28: #include "insn-config.h"
29: #include "basic-block.h"
30: #include <stdio.h>
31:
32: #define min(A,B) ((A) < (B) ? (A) : (B))
33:
34: /* This file contains the reload pass of the compiler, which is
35: run after register allocation has been done. It checks that
36: each insn is valid (operands required to be in registers really
37: are in registers of the proper class) and fixes up invalid ones
38: by copying values temporarily into registers for the insns
39: that need them.
40:
41: The results of register allocation are described by the vector
42: reg_renumber; the insns still contain pseudo regs, but reg_renumber
43: can be used to find which hard reg, if any, a pseudo reg is in.
44:
45: The technique we always use is to free up a few hard regs that are
46: called ``reload regs'', and for each place where a pseudo reg
47: must be in a hard reg, copy it temporarily into one of the reload regs.
48:
49: All the pseudos that were formerly allocated to the hard regs that
50: are now in use as reload regs must be ``spilled''. This means
51: that they go to other hard regs, or to stack slots if no other
52: available hard regs can be found. Spilling can invalidate more
53: insns, requiring additional need for reloads, so we must keep checking
54: until the process stabilizes.
55:
56: For machines with different classes of registers, we must keep track
57: of the register class needed for each reload, and make sure that
58: we allocate enough reload registers of each class.
59:
60: The file reload.c contains the code that checks one insn for
61: validity and reports the reloads that it needs. This file
62: is in charge of scanning the entire rtl code, accumulating the
63: reload needs, spilling, assigning reload registers to use for
64: fixing up each insn, and generating the new insns to copy values
65: into the reload registers. */
66:
67: /* During reload_as_needed, element N contains a REG rtx for the hard reg
68: into which pseudo reg N has been reloaded (perhaps for a previous insn). */
69: static rtx *reg_last_reload_reg;
70:
71: /* Element N is the constant value to which pseudo reg N is equivalent,
72: or zero if pseudo reg N is not equivalent to a constant.
73: find_reloads looks at this in order to replace pseudo reg N
74: with the constant it stands for. */
75: rtx *reg_equiv_constant;
76:
77: /* Element N is the address of stack slot to which pseudo reg N is equivalent.
78: This is used when the address is not valid as a memory address
79: (because its displacement is too big for the machine.) */
80: rtx *reg_equiv_address;
81:
82: /* Element N is the memory slot to which pseudo reg N is equivalent,
83: or zero if pseudo reg N is not equivalent to a memory slot. */
84: static rtx *reg_equiv_mem;
85:
86: /* Element N is the insn that initialized reg N from its equivalent
87: constant or memory slot. */
88: static rtx *reg_equiv_init;
89:
90: /* During reload_as_needed, element N contains the last pseudo regno
91: reloaded into the Nth reload register. This vector is in parallel
92: with spill_regs. */
93: static int reg_reloaded_contents[FIRST_PSEUDO_REGISTER];
94:
95: /* In parallel with spill_regs, contains REG rtx's for those regs.
96: Holds the last rtx used for any given reg, or 0 if it has never
97: been used for spilling yet. This rtx is reused, provided it has
98: the proper mode. */
99: static rtx spill_reg_rtx[FIRST_PSEUDO_REGISTER];
100:
101: /* In parallel with spill_regs, contains nonzero for a spill reg
102: that was stored after the last time it was used.
103: The precise value is the insn generated to do the store. */
104: static rtx spill_reg_store[FIRST_PSEUDO_REGISTER];
105:
106: /* This table is the inverse mapping of spill_regs:
107: indexed by hard reg number,
108: it contains the position of that reg in spill_regs,
109: or -1 for something that is not in spill_regs. */
110: static short spill_reg_order[FIRST_PSEUDO_REGISTER];
111:
112: /* This table contains 1 for a register that may not be used
113: for retrying global allocation, or -1 for a register that may be used.
114: The registers that may not be used include all spill registers
115: and the frame pointer (if we are using one). */
116: static short forbidden_regs[FIRST_PSEUDO_REGISTER];
117:
118: /* Describes order of use of registers for reloading
119: of spilled pseudo-registers. `spills' is the number of
120: elements that are actually valid; new ones are added at the end. */
121: static char spill_regs[FIRST_PSEUDO_REGISTER];
122:
123: /* Describes order of preference for putting regs into spill_regs.
124: Contains the numbers of all the hard regs, in order most preferred first.
125: This order is different for each function.
126: It is set up by order_regs_for_reload.
127: Empty elements at the end contain -1. */
128: static short potential_reload_regs[FIRST_PSEUDO_REGISTER];
129:
130: /* 1 for a hard register that appears explicitly in the rtl
131: (for example, function value registers, special registers
132: used by insns, structure value pointer registers). */
133: static char regs_explicitly_used[FIRST_PSEUDO_REGISTER];
134:
135: /* Nonzero if spilling (REG n) does not require reloading it into
136: a register in order to do (MEM (REG n)). */
137:
138: static char spill_indirect_ok;
139:
140: /* Indexed by basic block number, nonzero if there is any need
141: for a spill register in that basic block.
142: The pointer is 0 if we did stupid allocation and don't know
143: the structure of basic blocks. */
144:
145: char *basic_block_needs;
146:
147: /* First uid used by insns created by reload in this function.
148: Used in find_equiv_reg. */
149: int reload_first_uid;
150:
151: static void reload_as_needed ();
152: static rtx alter_frame_pointer_addresses ();
153: static void alter_reg ();
154: void mark_home_live ();
155: static int spill_hard_reg ();
156: static void choose_reload_targets ();
157: static void forget_old_reloads ();
158: static void order_regs_for_reload ();
159: static void eliminate_frame_pointer ();
160:
161: extern rtx adj_offsetable_operand ();
162:
163: /* Main entry point for the reload pass, and only entry point
164: in this file.
165:
166: FIRST is the first insn of the function being compiled.
167:
168: GLOBAL nonzero means we were called from global_alloc
169: and should attempt to reallocate any pseudoregs that we
170: displace from hard regs we will use for reloads.
171: If GLOBAL is zero, we do not have enough information to do that,
172: so any pseudo reg that is spilled must go to the stack.
173:
174: DUMPFILE is the global-reg debugging dump file stream, or 0.
175: If it is nonzero, messages are written to it to describe
176: which registers are seized as reload regs, which pseudo regs
177: are spilled from them, and where the pseudo regs are reallocated to. */
178:
179: void
180: reload (first, global, dumpfile)
181: rtx first;
182: int global;
183: FILE *dumpfile;
184: {
185: register int n_spills;
186: register int class;
187: register int i;
188: register rtx insn;
189:
190: int something_changed;
191: int something_needs_reloads;
192: int new_basic_block_needs;
193:
194: /* The basic block number currently being processed for INSN. */
195: int this_block;
196:
197: /* Enable find_equiv_reg to distinguish insns made by reload. */
198: reload_first_uid = get_max_uid ();
199:
200: basic_block_needs = 0;
201:
202: /* Remember which hard regs appear explicitly
203: before we merge into `regs_ever_live' the ones in which
204: pseudo regs have been allocated. */
205: bcopy (regs_ever_live, regs_explicitly_used, sizeof regs_ever_live);
206:
207: /* Compute which hard registers are now in use
208: as homes for pseudo registers.
209: This is done here rather than (eg) in global_alloc
210: because this point is reached even if not optimizing. */
211:
212: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
213: mark_home_live (i);
214:
215: /* Find all the pseudo registers that didn't get hard regs
216: but do have known equivalent constants or memory slots.
217: These include parameters (known equivalent to parameter slots)
218: and cse'd or loop-moved constant memory addresses.
219:
220: Record constant equivalents in reg_equiv_constant
221: so they will be substituted by find_reloads.
222: Record memory equivalents in reg_mem_equiv so they can
223: be substituted eventually by altering the REG-rtx's. */
224:
225: reg_equiv_constant = (rtx *) alloca (max_regno * sizeof (rtx));
226: bzero (reg_equiv_constant, max_regno * sizeof (rtx));
227: reg_equiv_mem = (rtx *) alloca (max_regno * sizeof (rtx));
228: bzero (reg_equiv_mem, max_regno * sizeof (rtx));
229: reg_equiv_init = (rtx *) alloca (max_regno * sizeof (rtx));
230: bzero (reg_equiv_init, max_regno * sizeof (rtx));
231: reg_equiv_address = (rtx *) alloca (max_regno * sizeof (rtx));
232: bzero (reg_equiv_address, max_regno * sizeof (rtx));
233:
234: for (insn = first; insn; insn = NEXT_INSN (insn))
235: if (GET_CODE (insn) == INSN
236: && GET_CODE (PATTERN (insn)) == SET
237: && GET_CODE (SET_DEST (PATTERN (insn))) == REG)
238: {
239: rtx note = find_reg_note (insn, REG_EQUIV, 0);
240: if (note)
241: {
242: rtx x = XEXP (note, 0);
243: i = REGNO (SET_DEST (PATTERN (insn)));
244: if (GET_CODE (x) == MEM)
245: reg_equiv_mem[i] = x;
246: else if (immediate_operand (x))
247: reg_equiv_constant[i] = x;
248: else
249: continue;
250:
251: reg_equiv_init[i] = insn;
252: }
253: }
254:
255: /* Does this function require a frame pointer? */
256:
257: frame_pointer_needed
258: |= (! global || FRAME_POINTER_REQUIRED);
259:
260: if (! frame_pointer_needed)
261: frame_pointer_needed
262: = check_frame_pointer_required (reg_equiv_constant, reg_equiv_mem);
263:
264: /* Alter each pseudo-reg rtx to contain its hard reg number.
265: Delete initializations of pseudos that don't have hard regs
266: and do have equivalents.
267: Assign stack slots to the pseudos that lack hard regs or equivalents. */
268:
269: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
270: alter_reg (i);
271:
272: #ifndef REGISTER_CONSTRAINTS
273: /* If all the pseudo regs have hard regs,
274: except for those that are never referenced,
275: we know that no reloads are needed. */
276: /* But that is not true if there are register constraints, since
277: in that case some pseudos might be in the wrong kind of hard reg. */
278:
279: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
280: if (reg_renumber[i] == -1 && reg_n_refs[i] != 0)
281: break;
282:
283: if (i == max_regno && frame_pointer_needed)
284: return;
285: #endif
286:
287: /* Compute the order of preference for hard registers to spill.
288: Store them by decreasing preference in potential_reload_regs. */
289:
290: order_regs_for_reload ();
291:
292: /* So far, no hard regs have been spilled. */
293: n_spills = 0;
294: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
295: {
296: spill_reg_order[i] = -1;
297: forbidden_regs[i] = -1;
298: }
299:
300: if (frame_pointer_needed)
301: {
302: forbidden_regs[FRAME_POINTER_REGNUM] = 1;
303: spill_hard_reg (FRAME_POINTER_REGNUM, global, dumpfile);
304: }
305:
306: if (global)
307: {
308: basic_block_needs = (char *)alloca (n_basic_blocks);
309: bzero (basic_block_needs, n_basic_blocks);
310: }
311:
312: /* This loop scans the entire function each go-round
313: and repeats until one repetition spills no additional hard regs. */
314:
315: /* This flag is set when a psuedo reg is spilled,
316: to require another pass. Note that getting an additional reload
317: reg does not necessarily imply any pseudo reg was spilled;
318: sometimes we find a reload reg that no pseudo reg was allocated in. */
319: something_changed = 1;
320: /* This flag is set if there are any insns that require reloading. */
321: something_needs_reloads = 0;
322: while (something_changed)
323: {
324: /* For each class, number of reload regs needed in that class.
325: This is the maximum over all insns of the needs in that class
326: of the individual insn. */
327: int max_needs[N_REG_CLASSES];
328: /* For each class, size of group of consecutive regs
329: that is needed for the reloads of this class. */
330: int group_size[N_REG_CLASSES];
331: /* For each class, max number of consecutive groups needed.
332: (Each group contains max_needs_size[CLASS] consecutive registers.) */
333: int max_groups[N_REG_CLASSES];
334: /* For each class, max number needed of regs that don't belong
335: to any of the groups. */
336: int max_nongroups[N_REG_CLASSES];
337: /* For each class, the machine mode which requires consecutive
338: groups of regs of that class.
339: If two different modes ever require groups of one class,
340: we crash, not having the hair to deal with that case. */
341: enum machine_mode group_mode[N_REG_CLASSES];
342: /* For each register, 1 if it was counted against the need for
343: groups. 0 means it can count against max_nongroup instead. */
344: char counted_for_groups[FIRST_PSEUDO_REGISTER];
345:
346: something_changed = 0;
347: bzero (max_needs, sizeof max_needs);
348: bzero (max_groups, sizeof max_groups);
349: bzero (max_nongroups, sizeof max_nongroups);
350: bzero (group_size, sizeof group_size);
351: for (i = 0; i < N_REG_CLASSES; i++)
352: group_mode[i] = VOIDmode;
353:
354: /* Keep track of which basic blocks are needing the reloads. */
355: this_block = 0;
356:
357: /* Remember whether any element of basic_block_needs
358: changes from 0 to 1 in this pass. */
359: new_basic_block_needs = 0;
360:
361: /* Compute the most additional registers needed by any instruction.
362: Collect information separately for each class of regs. */
363:
364: for (insn = first; insn; insn = NEXT_INSN (insn))
365: {
366: if (global && insn == basic_block_head[this_block+1])
367: ++this_block;
368:
369: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN
370: || GET_CODE (insn) == CALL_INSN)
371: {
372: int insn_needs[N_REG_CLASSES];
373: int insn_groups[N_REG_CLASSES];
374: int insn_total_groups = 0;
375:
376: for (i = 0; i < N_REG_CLASSES; i++)
377: insn_needs[i] = 0, insn_groups[i] = 0;
378:
379: #if 0
380: /* Optimization: a bit-field instruction whose field
381: happens to be a byte or halfword in memory
382: can be changed to a move instruction. */
383:
384: if (GET_CODE (PATTERN (insn)) == SET)
385: {
386: rtx dest = SET_DEST (PATTERN (insn));
387: rtx src = SET_SRC (PATTERN (insn));
388:
389: if (GET_CODE (dest) == ZERO_EXTRACT
390: || GET_CODE (dest) == SIGN_EXTRACT)
391: optimize_bit_field (PATTERN (insn), insn, reg_equiv_mem);
392: if (GET_CODE (src) == ZERO_EXTRACT
393: || GET_CODE (src) == SIGN_EXTRACT)
394: optimize_bit_field (PATTERN (insn), insn, reg_equiv_mem);
395: }
396: #endif
397:
398: /* Analyze the instruction. */
399:
400: find_reloads (insn, 0, spill_indirect_ok, global, spill_reg_order);
401:
402: if (n_reloads == 0)
403: continue;
404:
405: something_needs_reloads = 1;
406:
407: /* Count each reload once in every class
408: containing the reload's own class. */
409:
410: for (i = 0; i < n_reloads; i++)
411: {
412: register enum reg_class *p;
413: int size;
414: enum machine_mode mode;
415:
416: /* Don't count the dummy reloads, for which one of the
417: regs mentioned in the insn can be used for reloading.
418: Don't count optional reloads.
419: Don't count reloads that got combined with others. */
420: if (reload_reg_rtx[i] != 0
421: || reload_optional[i] != 0
422: || (reload_out[i] == 0 && reload_in[i] == 0))
423: continue;
424:
425: mode = reload_inmode[i];
426: if (GET_MODE_SIZE (reload_outmode[i]) > GET_MODE_SIZE (mode))
427: mode = reload_outmode[i];
428: size = CLASS_MAX_NREGS (reload_reg_class[i], mode);
429: if (size > 1)
430: {
431: /* Count number of groups needed separately from
432: number of individual regs needed. */
433: insn_groups[(int) reload_reg_class[i]]++;
434: p = reg_class_superclasses[(int) reload_reg_class[i]];
435: while (*p != LIM_REG_CLASSES)
436: insn_groups[(int) *p++]++;
437: insn_total_groups++;
438:
439: /* Record size of a group. */
440: group_size[(int) reload_reg_class[i]] = size;
441: /* If a group of consecutive regs are needed,
442: record which machine mode needs them.
443: Crash if two different machine modes both need
444: groups of consecutive regs of the same class. */
445: if ((group_mode[(int) reload_reg_class[i]] != VOIDmode)
446: &&
447: (group_mode[(int) reload_reg_class[i]] != mode))
448: abort ();
449: group_mode[(int) reload_reg_class[i]] = mode;
450: }
451: else if (size == 1)
452: {
453: insn_needs[(int) reload_reg_class[i]] += 1;
454: p = reg_class_superclasses[(int) reload_reg_class[i]];
455: while (*p != LIM_REG_CLASSES)
456: insn_needs[(int) *p++] += 1;
457: }
458: else
459: abort ();
460:
461: if (global)
462: {
463: if (! basic_block_needs[this_block])
464: new_basic_block_needs = 1;
465: basic_block_needs[this_block] = 1;
466: }
467: }
468:
469: /* Remember for later shortcuts which insns had any reloads. */
470:
471: PUT_MODE (insn, n_reloads ? QImode : VOIDmode);
472:
473: /* For each class, collect maximum need of any insn */
474:
475: for (i = 0; i < N_REG_CLASSES; i++)
476: {
477: if (max_needs[i] < insn_needs[i])
478: max_needs[i] = insn_needs[i];
479: if (max_groups[i] < insn_groups[i])
480: max_groups[i] = insn_groups[i];
481: if (insn_total_groups > 0)
482: if (max_nongroups[i] < insn_needs[i])
483: max_nongroups[i] = insn_needs[i];
484: }
485: }
486: /* Note that there is a continue statement above. */
487: }
488:
489: /* Now deduct from the needs for the registers already
490: available (already spilled). */
491:
492: bzero (counted_for_groups, sizeof counted_for_groups);
493:
494: /* Find all consecutive groups of spilled registers
495: and mark each group off against the need for such groups. */
496:
497: for (i = 0; i < N_REG_CLASSES; i++)
498: if (group_size[i] > 1)
499: {
500: char regmask[FIRST_PSEUDO_REGISTER];
501: int j;
502:
503: bzero (regmask, sizeof regmask);
504: /* Make a mask of all the regs that are spill regs in class I. */
505: for (j = 0; j < n_spills; j++)
506: if (TEST_HARD_REG_BIT (reg_class_contents[i], spill_regs[j])
507: && !counted_for_groups[spill_regs[i]])
508: regmask[spill_regs[j]] = 1;
509: /* Find each consecutive group of them. */
510: for (j = 0; j < FIRST_PSEUDO_REGISTER && max_groups[i] > 0; j++)
511: if (regmask[j] && j + group_size[i] <= FIRST_PSEUDO_REGISTER)
512: {
513: int k;
514: for (k = 1; k < group_size[i]; k++)
515: if (! regmask[j + k])
516: break;
517: if (k == group_size[i])
518: {
519: /* We found a group. Mark it off against this class's
520: need for groups, and against each superclass too. */
521: register enum reg_class *p;
522: max_groups[i]--;
523: p = reg_class_superclasses[i];
524: while (*p != LIM_REG_CLASSES)
525: max_groups[(int) *p++]--;
526: /* Don't count these registers again. */
527: counted_for_groups[j] = 1;
528: for (k = 1; k < group_size[i]; k++)
529: counted_for_groups[j + k] = 1;
530: }
531: j += k;
532: }
533: }
534:
535: /* Now count all remaining spill regs against the individual need.
536: Those that weren't counted_for_groups in groups can also count against
537: the not-in-group need. */
538:
539: for (i = 0; i < n_spills; i++)
540: {
541: register enum reg_class *p;
542: class = (int) REGNO_REG_CLASS (spill_regs[i]);
543:
544: max_needs[class]--;
545: p = reg_class_superclasses[class];
546: while (*p != LIM_REG_CLASSES)
547: max_needs[(int) *p++]--;
548:
549: if (! counted_for_groups[spill_regs[i]])
550: {
551: max_nongroups[class]--;
552: p = reg_class_superclasses[class];
553: while (*p != LIM_REG_CLASSES)
554: max_nongroups[(int) *p++]--;
555: }
556: }
557:
558: /* If all needs are met, we win. */
559:
560: for (i = 0; i < N_REG_CLASSES; i++)
561: if (max_needs[i] > 0 || max_groups[i] > 0 || max_nongroups[i] > 0)
562: break;
563: if (i == N_REG_CLASSES && !new_basic_block_needs)
564: break;
565:
566: /* Not all needs are met; must spill more hard regs. */
567:
568: /* If any element of basic_block_needs changed from 0 to 1,
569: re-spill all the regs already spilled. This may spill
570: additional pseudos that didn't spill before. */
571:
572: if (new_basic_block_needs)
573: for (i = 0; i < n_spills; i++)
574: something_changed
575: |= spill_hard_reg (spill_regs[i], global, dumpfile);
576:
577: /* Now find more reload regs to satisfy the remaining need.
578: Count them in `spills', and add entries to
579: `spill_regs' and `spill_reg_order'. */
580:
581: for (class = 0; class < N_REG_CLASSES; class++)
582: while (max_needs[class] > 0 || max_groups[class] > 0
583: || max_nongroups[class] > 0)
584: {
585: register enum reg_class *p;
586: int in_a_group = 0;
587:
588: /* First, if we need more groups of consecutive regs, get them.
589: Either get a spill register that completes a group
590: or, if that cannot be done, get one that starts a group.
591: Here we do not yet handle groups of size > 2. */
592: if (max_groups[class] > 0)
593: {
594: if (group_size[class] > 2)
595: abort ();
596:
597: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
598: {
599: int j = potential_reload_regs[i];
600: if (j >= 0
601: &&
602: ((j > 0 && spill_reg_order[j - 1] >= 0
603: && TEST_HARD_REG_BIT (reg_class_contents[class], j)
604: && TEST_HARD_REG_BIT (reg_class_contents[class], j - 1)
605: && HARD_REGNO_MODE_OK (j - 1, group_mode[class]))
606: ||
607: (j < FIRST_PSEUDO_REGISTER - 1
608: && spill_reg_order[j + 1] >= 0
609: && TEST_HARD_REG_BIT (reg_class_contents[class], j)
610: && TEST_HARD_REG_BIT (reg_class_contents[class], j + 1)
611: && HARD_REGNO_MODE_OK (j, group_mode[class]))))
612: {
613: /* We have found one that will complete a group,
614: so count off one group as provided. */
615: max_groups[class]--;
616: p = reg_class_superclasses[class];
617: while (*p != LIM_REG_CLASSES)
618: max_groups[(int) *p++]--;
619: in_a_group = 1;
620: break;
621: }
622: }
623: /* We can't complete any group, so start one. */
624: if (i == FIRST_PSEUDO_REGISTER)
625: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
626: {
627: int j = potential_reload_regs[i];
628: if (j >= 0 && j + 1 < FIRST_PSEUDO_REGISTER
629: && spill_reg_order[j] < 0 && spill_reg_order[j + 1] < 0
630: && TEST_HARD_REG_BIT (reg_class_contents[class], j)
631: && TEST_HARD_REG_BIT (reg_class_contents[class], j + 1)
632: && HARD_REGNO_MODE_OK (j, group_mode[class]))
633: {
634: in_a_group = 1;
635: break;
636: }
637: }
638: }
639: else
640: {
641: /* We want a solitary register. */
642:
643: /* Consider the potential reload regs that aren't
644: yet in use as reload regs, in order of preference.
645: Find the most preferred one that's in this class. */
646:
647: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
648: if (potential_reload_regs[i] >= 0
649: && TEST_HARD_REG_BIT (reg_class_contents[class],
650: potential_reload_regs[i]))
651: break;
652: }
653:
654: /* I should be the index in potential_reload_regs
655: of the new reload reg we have found. */
656:
657: if (i == FIRST_PSEUDO_REGISTER)
658: abort (); /* No reload reg possible? */
659:
660: /* Make potential_reload_regs[i] an additional reload reg. */
661:
662: spill_regs[n_spills] = potential_reload_regs[i];
663: spill_reg_order[potential_reload_regs[i]] = n_spills;
664: forbidden_regs[potential_reload_regs[i]] = 1;
665: potential_reload_regs[i] = -1;
666: if (dumpfile)
667: fprintf (dumpfile, "Spilling reg %d.\n", spill_regs[n_spills]);
668:
669: /* Clear off the needs we just satisfied. */
670:
671: max_needs[class]--;
672: p = reg_class_superclasses[class];
673: while (*p != LIM_REG_CLASSES)
674: max_needs[(int) *p++]--;
675:
676: if (! in_a_group)
677: {
678: max_nongroups[class]--;
679: p = reg_class_superclasses[class];
680: while (*p != LIM_REG_CLASSES)
681: max_nongroups[(int) *p++]--;
682: }
683:
684: /* Spill every pseudo reg that was allocated to this reg
685: or to something that overlaps this reg. */
686:
687: something_changed |= spill_hard_reg (spill_regs[n_spills],
688: global, dumpfile);
689:
690: regs_ever_live[spill_regs[n_spills]] = 1;
691: n_spills++;
692: }
693: }
694:
695: /* Use the reload registers where necessary
696: by generating move instructions to move the must-be-register
697: values into or out of the reload registers. */
698:
699: if (something_needs_reloads)
700: reload_as_needed (first, n_spills, global);
701:
702: /* Now eliminate all pseudo regs by modifying them into
703: their equivalent memory references.
704: The REG-rtx's for the pseudos are modified in place,
705: so all insns that used to refer to them now refer to memory.
706:
707: For a reg that has a reg_equiv_address, all those insns
708: were changed by reloading so that no insns refer to it any longer;
709: but the DECL_RTL of a variable decl may refer to it,
710: and if so this causes the debugging info to mention the variable. */
711:
712: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
713: {
714: rtx addr = 0;
715: if (reg_equiv_mem[i])
716: addr = XEXP (reg_equiv_mem[i], 0);
717: if (reg_equiv_address[i])
718: addr = reg_equiv_address[i];
719: if (addr)
720: {
721: if (reg_renumber[i] < 0)
722: {
723: rtx reg = regno_reg_rtx[i];
724: XEXP (reg, 0) = addr;
725: PUT_CODE (reg, MEM);
726: }
727: else if (reg_equiv_mem[i])
728: {
729: if (! frame_pointer_needed)
730: FIX_FRAME_POINTER_ADDRESS (addr, 0);
731: XEXP (reg_equiv_mem[i], 0) = addr;
732: }
733: }
734: }
735:
736: /* Sometimes the sole reference to a parameter has been combined into
737: another instruction, eliminating the parameter's register.
738: Find these memory references and fix their addresses. */
739:
740: if (! frame_pointer_needed)
741: eliminate_frame_pointer (first);
742: }
743:
744: /* Scan all insns, computing the stack depth, and convert all
745: frame-pointer-relative references to stack-pointer-relative references. */
746:
747: static void
748: eliminate_frame_pointer (first)
749: rtx first;
750: {
751: int depth = 0;
752: int max_uid = get_max_uid ();
753: int *label_depth = (int *) alloca ((max_uid + 1) * sizeof (int));
754: int i;
755: rtx insn;
756:
757: for (i = 0; i <= max_uid; i++)
758: label_depth[i] = -1;
759:
760: /* In this loop, for each forward branch we record the stack
761: depth of the label it jumps to. We take advantage of the fact
762: that the stack depth at a label reached by a backward branch
763: is always, in GCC output, equal to the stack depth of the preceding
764: unconditional jump, because it was either a loop statement or
765: statement label. */
766:
767: for (insn = first; insn; insn = NEXT_INSN (insn))
768: {
769: rtx pattern = PATTERN (insn);
770: switch (GET_CODE (insn))
771: {
772: case INSN:
773: alter_frame_pointer_addresses (pattern, depth);
774: #ifdef PUSH_ROUNDING
775: /* Notice pushes and pops; update DEPTH. */
776: if (GET_CODE (pattern) == SET)
777: {
778: if (push_operand (SET_DEST (pattern),
779: GET_MODE (SET_DEST (pattern))))
780: depth += PUSH_ROUNDING (GET_MODE_SIZE (GET_MODE (SET_DEST (pattern))));
781: if (GET_CODE (SET_DEST (pattern)) == REG
782: && REGNO (SET_DEST (pattern)) == STACK_POINTER_REGNUM)
783: {
784: int delta;
785: if (GET_CODE (SET_SRC (pattern)) == PLUS
786: && GET_CODE (XEXP (SET_SRC (pattern), 0)) == REG
787: && REGNO (XEXP (SET_SRC (pattern), 0)) == STACK_POINTER_REGNUM)
788: delta = INTVAL (XEXP (SET_SRC (pattern), 1));
789: else if (GET_CODE (SET_SRC (pattern)) == MINUS
790: && GET_CODE (XEXP (SET_SRC (pattern), 0)) == REG
791: && REGNO (XEXP (SET_SRC (pattern), 0)) == STACK_POINTER_REGNUM)
792: delta = -INTVAL (XEXP (SET_SRC (pattern), 1));
793: else abort ();
794: #ifdef STACK_GROWS_DOWNWARD
795: depth -= delta;
796: #else
797: depth += delta;
798: #endif
799: }
800: }
801: #endif
802: break;
803:
804: case JUMP_INSN:
805: alter_frame_pointer_addresses (pattern, depth);
806: if (GET_CODE (pattern) == ADDR_VEC)
807: for (i = 0; i < XVECLEN (pattern, 0); i++)
808: label_depth[INSN_UID (XEXP (XVECEXP (pattern, 0, i), 0))] = depth;
809: else if (GET_CODE (pattern) == ADDR_DIFF_VEC)
810: {
811: label_depth[INSN_UID (XEXP (XEXP (pattern, 0), 0))] = depth;
812: for (i = 0; i < XVECLEN (pattern, 1); i++)
813: label_depth[INSN_UID (XEXP (XVECEXP (pattern, 1, i), 0))] = depth;
814: }
815: else if (JUMP_LABEL (insn))
816: label_depth[INSN_UID (JUMP_LABEL (insn))] = depth;
817: else
818: break;
819:
820: case CODE_LABEL:
821: if (label_depth [INSN_UID (insn)] >= 0)
822: depth = label_depth [INSN_UID (insn)];
823: break;
824:
825: case CALL_INSN:
826: alter_frame_pointer_addresses (pattern, depth);
827: break;
828: }
829: }
830: }
831:
832: /* Walk the rtx X, converting all frame-pointer refs to stack-pointer refs
833: on the assumption that the current temporary stack depth is DEPTH.
834: (The size of saved registers must be added to DEPTH
835: to get the actual offset between the logical frame-pointer and the
836: stack pointer. FIX_FRAME_POINTER_ADDRESS takes care of that.) */
837:
838: static rtx
839: alter_frame_pointer_addresses (x, depth)
840: register rtx x;
841: int depth;
842: {
843: register int i;
844: register char *fmt;
845: register enum rtx_code code = GET_CODE (x);
846:
847: switch (code)
848: {
849: case REG:
850: case CONST_INT:
851: case CONST:
852: case SYMBOL_REF:
853: case LABEL_REF:
854: case CONST_DOUBLE:
855: case CC0:
856: case PC:
857: return x;
858:
859: case MEM:
860: {
861: rtx addr = XEXP (x, 0);
862: FIX_FRAME_POINTER_ADDRESS (addr, depth);
863: XEXP (x, 0) = addr;
864: }
865: break;
866:
867: case PLUS:
868: /* Handle addresses being loaded or pushed, etc.,
869: rather than referenced. */
870: FIX_FRAME_POINTER_ADDRESS (x, depth);
871: break;
872: }
873:
874: fmt = GET_RTX_FORMAT (code);
875: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
876: {
877: if (fmt[i] == 'e')
878: XEXP (x, i) = alter_frame_pointer_addresses (XEXP (x, i), depth);
879: else if (fmt[i] == 'E')
880: {
881: register int j;
882: for (j = XVECLEN (x, i) - 1; j >=0; j--)
883: XVECEXP (x, i, j)
884: = alter_frame_pointer_addresses (XVECEXP (x, i, j), depth);
885: }
886: }
887: return x;
888: }
889:
890: static void
891: alter_reg (i)
892: register int i;
893: {
894: /* If the reg got changed to a MEM at rtl-generation time,
895: ignore it. */
896: if (GET_CODE (regno_reg_rtx[i]) != REG)
897: return;
898:
899: /* Modify the reg-rtx to contain the new hard reg
900: number or else to contain its pseudo reg number. */
901: REGNO (regno_reg_rtx[i])
902: = reg_renumber[i] >= 0 ? reg_renumber[i] : i;
903:
904: if (reg_renumber[i] < 0 && reg_equiv_init[i])
905: {
906: /* Delete the insn that loads the pseudo register. */
907: PUT_CODE (reg_equiv_init[i], NOTE);
908: NOTE_LINE_NUMBER (reg_equiv_init[i])
909: = NOTE_INSN_DELETED;
910: NOTE_SOURCE_FILE (reg_equiv_init[i]) = 0;
911: }
912:
913: /* If we have a pseudo that is needed but has no hard reg or equivalent,
914: allocate a stack slot for it. */
915:
916: if (reg_renumber[i] < 0
917: && reg_n_refs[i] > 0
918: && reg_equiv_constant[i] == 0
919: && reg_equiv_mem[i] == 0)
920: {
921: register rtx x = assign_stack_local (GET_MODE (regno_reg_rtx[i]),
922: PSEUDO_REGNO_BYTES (i));
923: register rtx addr = XEXP (x, 0);
924: /* If the stack slot is directly addressable, substitute
925: the MEM we just got directly for the old REG.
926: Otherwise, record the address; we will generate hairy code
927: to compute the address in a register each time it is needed. */
928: if (memory_address_p (GET_MODE (regno_reg_rtx[i]), addr))
929: reg_equiv_mem[i] = x;
930: else
931: reg_equiv_address[i] = XEXP (x, 0);
932: }
933: }
934:
935: /* Mark the slots in regs_ever_live for the hard regs
936: used by pseudo-reg number REGNO. */
937:
938: void
939: mark_home_live (regno)
940: int regno;
941: {
942: register int i, lim;
943: i = reg_renumber[regno];
944: if (i < 0)
945: return;
946: lim = i + HARD_REGNO_NREGS (i, PSEUDO_REGNO_MODE (regno));
947: while (i < lim)
948: regs_ever_live[i++] = 1;
949: }
950:
951: /* Kick all pseudos out of hard register REGNO.
952: If GLOBAL is nonzero, try to find someplace else to put them.
953: If DUMPFILE is nonzero, log actions taken on that file.
954:
955: Return nonzero if any pseudos needed to be kicked out. */
956:
957: static int
958: spill_hard_reg (regno, global, dumpfile)
959: register int regno;
960: int global;
961: FILE *dumpfile;
962: {
963: int something_changed = 0;
964: register int i;
965:
966: /* Spill every pseudo reg that was allocated to this reg
967: or to something that overlaps this reg. */
968:
969: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
970: if (reg_renumber[i] >= 0
971: && reg_renumber[i] <= regno
972: && (reg_renumber[i]
973: + HARD_REGNO_NREGS (reg_renumber[i],
974: PSEUDO_REGNO_MODE (i))
975: > regno))
976: {
977: #if 1
978: /* If this register belongs solely to a basic block
979: which needed no spilling, leave it be. */
980: if (basic_block_needs
981: && reg_basic_block[i] >= 0
982: && basic_block_needs[reg_basic_block[i]] == 0)
983: continue;
984: #endif
985:
986: /* Mark it as no longer having a hard register home. */
987: reg_renumber[i] = -1;
988: /* We will need to scan everything again. */
989: something_changed = 1;
990: if (global)
991: {
992: retry_global_alloc (i, forbidden_regs);
993: /* Update regs_ever_live for new home (if any). */
994: mark_home_live (i);
995: /* If something gets spilled to the stack,
996: we must have a frame pointer, so spill the frame pointer. */
997: if (reg_renumber[i] == -1 && ! frame_pointer_needed)
998: {
999: frame_pointer_needed = 1;
1000: forbidden_regs[FRAME_POINTER_REGNUM] = 1;
1001: spill_hard_reg (FRAME_POINTER_REGNUM, global, dumpfile);
1002: }
1003: }
1004: alter_reg (i);
1005: if (dumpfile)
1006: {
1007: if (reg_renumber[i] == -1)
1008: fprintf (dumpfile, " Register %d now on stack.\n\n", i);
1009: else
1010: fprintf (dumpfile, " Register %d now in %d.\n\n",
1011: i, reg_renumber[i]);
1012: }
1013: }
1014:
1015: return something_changed;
1016: }
1017:
1018: struct hard_reg_n_uses { int regno; int uses; };
1019:
1020: static int
1021: hard_reg_use_compare (p1, p2)
1022: struct hard_reg_n_uses *p1, *p2;
1023: {
1024: return p1->uses - p2->uses;
1025: }
1026:
1027: /* Choose the order to consider regs for use as reload registers
1028: based on how much trouble would be caused by spilling one.
1029: Store them in order of decreasing preference in potential_reload_regs. */
1030:
1031: static void
1032: order_regs_for_reload ()
1033: {
1034: register int i;
1035: register int o = 0;
1036: int large = 0;
1037:
1038: struct hard_reg_n_uses hard_reg_n_uses[FIRST_PSEUDO_REGISTER];
1039:
1040: /* Count number of uses of each hard reg by pseudo regs allocated to it
1041: and then order them by decreasing use. */
1042:
1043: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1044: {
1045: hard_reg_n_uses[i].uses = 0;
1046: hard_reg_n_uses[i].regno = i;
1047: }
1048:
1049: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1050: {
1051: if (reg_renumber[i] >= 0)
1052: hard_reg_n_uses[reg_renumber[i]].uses += reg_n_refs[i];
1053: large += reg_n_refs[i];
1054: }
1055:
1056: /* Now fixed registers (which cannot safely be used for reloading)
1057: get a very high use count so they will be considered least desirable.
1058: Likewise registers used explicitly in the rtl code. */
1059:
1060: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1061: if (fixed_regs[i] || regs_explicitly_used[i])
1062: hard_reg_n_uses[i].uses = large;
1063: hard_reg_n_uses[FRAME_POINTER_REGNUM].uses = large;
1064:
1065: qsort (hard_reg_n_uses, FIRST_PSEUDO_REGISTER,
1066: sizeof hard_reg_n_uses[0], hard_reg_use_compare);
1067:
1068: /* Prefer registers not so far used, for use in temporary loading.
1069: Among them, prefer registers not preserved by calls. */
1070:
1071: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1072: if (regs_ever_live[i] == 0 && call_used_regs[i]
1073: && ! fixed_regs[i])
1074: potential_reload_regs[o++] = i;
1075:
1076: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1077: if (regs_ever_live[i] == 0 && ! call_used_regs[i]
1078: && i != FRAME_POINTER_REGNUM)
1079: potential_reload_regs[o++] = i;
1080:
1081: /* Now add the regs that are already used,
1082: preferring those used less often. */
1083:
1084: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1085: if (regs_ever_live[hard_reg_n_uses[i].regno] != 0)
1086: potential_reload_regs[o++] = hard_reg_n_uses[i].regno;
1087:
1088: #if 0
1089: /* For regs that are used, don't prefer those not preserved by calls
1090: because those are likely to contain high priority things
1091: that are live for short periods of time. */
1092:
1093: for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1094: if (regs_ever_live[i] != 0 && ! call_used_regs[i])
1095: potential_reload_regs[o++] = i;
1096: #endif
1097: }
1098:
1099: /* Reload pseudo-registers into hard regs around each insn as needed.
1100: Additional register load insns are output before the insn that needs it
1101: and perhaps store insns after insns that modify the reloaded pseudo reg.
1102:
1103: reg_last_reload_reg and reg_reloaded_contents keep track of
1104: which pseudo-registers are already available in reload registers.
1105: We update these for the reloads that we perform,
1106: as the insns are scanned. */
1107:
1108: static void
1109: reload_as_needed (first, n_spills, live_known)
1110: rtx first;
1111: int n_spills;
1112: int live_known;
1113: {
1114: register rtx insn;
1115: register int i;
1116:
1117: /* Often (MEM (REG n)) is still valid even if (REG n) is put on the stack.
1118: Set spill_indirect_ok if so. */
1119: register rtx tem
1120: = gen_rtx (MEM, SImode,
1121: gen_rtx (PLUS, Pmode,
1122: gen_rtx (REG, Pmode, FRAME_POINTER_REGNUM),
1123: gen_rtx (CONST_INT, VOIDmode, 4)));
1124:
1125: spill_indirect_ok = memory_address_p (QImode, tem);
1126:
1127: bzero (spill_reg_rtx, sizeof spill_reg_rtx);
1128: reg_last_reload_reg = (rtx *) alloca (max_regno * sizeof (rtx));
1129: bzero (reg_last_reload_reg, max_regno * sizeof (rtx));
1130: for (i = 0; i < n_spills; i++)
1131: reg_reloaded_contents[i] = -1;
1132:
1133: for (insn = first; insn;)
1134: {
1135: register rtx next = NEXT_INSN (insn);
1136: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN
1137: || GET_CODE (insn) == CALL_INSN)
1138: {
1139: if (GET_MODE (insn) == VOIDmode)
1140: n_reloads = 0;
1141: /* First find the pseudo regs that must be reloaded for this insn.
1142: This info is returned in the tables reload_... (see reload.h).
1143: Also modify the body of INSN by substituting RELOAD
1144: rtx's for those pseudo regs. */
1145: else
1146: find_reloads (insn, 1, spill_indirect_ok, live_known, spill_reg_order);
1147:
1148: if (n_reloads > 0)
1149: {
1150: /* Now compute which reload regs to reload them into. Perhaps
1151: reusing reload regs from previous insns, or else output
1152: load insns to reload them. Maybe output store insns too.
1153: Record the choices of reload reg in reload_reg_rtx. */
1154: choose_reload_targets (insn, n_spills);
1155: /* Substitute the chosen reload regs from reload_reg_rtx
1156: into the insn's body (or perhaps into the bodies of other
1157: load and store insn that we just made for reloading
1158: and that we moved the structure into). */
1159: subst_reloads ();
1160: }
1161: /* Any previously reloaded spilled pseudo reg, stored in this insn,
1162: is no longer validly lying around to save a future reload.
1163: Note that this does not detect pseudos that were reloaded
1164: for this insn in order to be stored in
1165: (obeying register constraints). That is correct; such reload
1166: registers ARE still valid. */
1167: forget_old_reloads (PATTERN (insn));
1168: }
1169: /* A reload reg's contents are unknown after a label. */
1170: if (GET_CODE (insn) == CODE_LABEL)
1171: for (i = 0; i < n_spills; i++)
1172: reg_reloaded_contents[i] = -1;
1173:
1174: /* Don't assume a reload reg is still good after a call insn
1175: if it is a call-used reg. */
1176: if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == CALL_INSN)
1177: for (i = 0; i < n_spills; i++)
1178: if (call_used_regs[spill_regs[i]])
1179: reg_reloaded_contents[i] = -1;
1180:
1181: insn = next;
1182: }
1183: }
1184:
1185: /* If we see a pseudo-reg being stored into,
1186: don't try to reuse an old reload reg
1187: which previously contained a copy of it. */
1188:
1189: static void
1190: forget_old_reloads (x)
1191: rtx x;
1192: {
1193: if (GET_CODE (x) == SET && GET_CODE (SET_DEST (x)) == REG)
1194: {
1195: register int regno = REGNO (SET_DEST (x));
1196: int nr;
1197:
1198: if (regno >= FIRST_PSEUDO_REGISTER)
1199: nr = 1;
1200: else
1201: {
1202: int i;
1203: nr = HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (x)));
1204: /* Storing into a spilled-reg invalidates its contents.
1205: This can happen if a block-local pseudo is allocated to that reg
1206: and it wasn't spilled because this block's total need is 0.
1207: Then some insn might have an optional reload and use this reg. */
1208: for (i = 0; i < nr; i++)
1209: if (spill_reg_order[regno + i] >= 0)
1210: reg_reloaded_contents[spill_reg_order[regno + i]] = -1;
1211: }
1212:
1213: while (nr-- > 0) reg_last_reload_reg[regno + nr] = 0;
1214: }
1215: else if (GET_CODE (x) == PARALLEL)
1216: {
1217: register int i;
1218: for (i = 0; i < XVECLEN (x, 0); i++)
1219: {
1220: register rtx y = XVECEXP (x, 0, i);
1221: if (GET_CODE (y) == SET && GET_CODE (SET_DEST (y)) == REG)
1222: forget_old_reloads (y);
1223: }
1224: }
1225: }
1226:
1227: /* Comparison function for qsort to decide which of two reloads
1228: should be handled first. *P1 and *P2 are the reload numbers. */
1229:
1230: static int
1231: reload_reg_class_lower (p1, p2)
1232: short *p1, *p2;
1233: {
1234: register int r1 = *p1, r2 = *p2;
1235: register int t;
1236: register enum machine_mode mode1, mode2;
1237:
1238: /* Consider required reloads before optional ones. */
1239: t = reload_optional[r1] - reload_optional[r2];
1240: if (t != 0)
1241: return t;
1242: /* Consider reloads in order of increasing reg-class number. */
1243: t = (int) reload_reg_class[r1] - (int) reload_reg_class[r2];
1244: if (t != 0)
1245: return t;
1246: /* For a given reg-class number, consider multi-reg groups first. */
1247: mode1 = (reload_inmode[r1] == VOIDmode ? reload_outmode[r1] : reload_inmode[r1]);
1248: mode2 = (reload_inmode[r2] == VOIDmode ? reload_outmode[r2] : reload_inmode[r2]);
1249: t = (CLASS_MAX_NREGS (reload_reg_class[r2], mode2)
1250: - CLASS_MAX_NREGS (reload_reg_class[r1], mode1));
1251: return t;
1252: }
1253:
1254: /* Assign hard reg targets for the pseudo-registers we must reload
1255: into hard regs for this insn.
1256: Also output the instructions to copy them in and out of the hard regs.
1257:
1258: For machines with register classes, we are responsible for
1259: finding a reload reg in the proper class. */
1260:
1261: static void
1262: choose_reload_targets (insn, n_spills)
1263: rtx insn;
1264: int n_spills;
1265: {
1266: register int j;
1267: char reload_reg_in_use[FIRST_PSEUDO_REGISTER];
1268: short reload_order[FIRST_PSEUDO_REGISTER];
1269: char reload_inherited[FIRST_PSEUDO_REGISTER];
1270: /* Elt N nonzero if reg_last_reload_reg[N] has been set in this insn
1271: for an output reload that stores into reg N. */
1272: char *reg_has_output_reload;
1273: int have_groups = 0;
1274:
1275: /* For each reload, the index in spill_regs of the spill register used,
1276: or -1 if we did not need one of the spill registers for this reload. */
1277: int reload_spill_index[FIRST_PSEUDO_REGISTER];
1278:
1279: bzero (reload_inherited, FIRST_PSEUDO_REGISTER);
1280: bzero (reload_reg_in_use, FIRST_PSEUDO_REGISTER);
1281:
1282: reg_has_output_reload = (char *) alloca (max_regno);
1283: bzero (reg_has_output_reload, max_regno);
1284:
1285: /* In order to be certain of getting the registers we need,
1286: we must sort the reloads into order of increasing register class.
1287: Then our grabbing of reload registers will parallel the process
1288: that provided the reload registers. */
1289:
1290: /* Also note whether any of the reloads wants a consecutive group of regs.
1291: When that happens, we must when processing the non-group reloads
1292: avoid (when possible) using a reload reg that would break up a group. */
1293:
1294: /* This used to look for an existing reloaded home for all
1295: of the reloads, and only then perform any new reloads.
1296: But that could lose if the reloads were done out of reg-class order
1297: because a later reload with a looser constraint might have an old
1298: home in a register needed by an earlier reload with a tighter constraint.
1299: It would be possible with even hairier code to detect such cases
1300: and handle them, but it doesn't seem worth while yet. */
1301:
1302: for (j = 0; j < n_reloads; j++)
1303: {
1304: enum machine_mode mode;
1305: reload_order[j] = j;
1306: reload_spill_index[j] = -1;
1307: mode = (reload_inmode[j] == VOIDmode ? reload_outmode[j] : reload_inmode[j]);
1308: if (CLASS_MAX_NREGS (reload_reg_class[j], mode) > 1)
1309: have_groups = 1;
1310: }
1311:
1312: if (n_reloads > 1)
1313: qsort (reload_order, n_reloads, sizeof (short), reload_reg_class_lower);
1314:
1315: for (j = 0; j < n_reloads; j++)
1316: {
1317: register int r = reload_order[j];
1318: register int i;
1319: register rtx new;
1320: enum machine_mode reload_mode = reload_inmode[r];
1321:
1322: if (GET_MODE_SIZE (reload_outmode[r]) > GET_MODE_SIZE (reload_mode))
1323: reload_mode = reload_outmode[r];
1324: if (reload_strict_low[r])
1325: reload_mode = GET_MODE (SUBREG_REG (reload_out[r]));
1326:
1327: /* Ignore reloads that got marked inoperative. */
1328: if (reload_out[r] == 0 && reload_in[r] == 0)
1329: continue;
1330:
1331: /* No need to find a reload-register if find_reloads chose one. */
1332:
1333: if (reload_reg_rtx[r] != 0)
1334: {
1335: #if 0
1336: /* But do see if the chosen reload-reg already contains
1337: a copy of the desired value. */
1338: if (reload_in[r] != 0)
1339: {
1340: register rtx equiv
1341: = find_equiv_reg (reload_in[r], insn, 0,
1342: REGNO (reload_reg_rtx[r]), 0, 0);
1343: if (equiv != 0)
1344: reload_inherited[r] = 1;
1345: }
1346: #endif
1347: continue;
1348: }
1349:
1350: /* First see if this pseudo is already available as reloaded
1351: for a previous insn.
1352: This feature is disabled for multi-register groups
1353: because we haven't yet any way to tell whether the entire
1354: value is properly preserved.
1355: It is also disabled when there are other reloads for mult-register
1356: groups, lest the inherited reload reg break up a needed group. */
1357:
1358: {
1359: register int regno = -1;
1360:
1361: if (reload_in[r] == 0)
1362: ;
1363: else if (GET_CODE (reload_in[r]) == REG)
1364: regno = REGNO (reload_in[r]);
1365: #if 0
1366: /* This won't work, since REGNO can be a pseudo reg number.
1367: Also, it takes much more hair to keep track of all the things
1368: that can invalidate an inherited reload of part of a pseudoreg. */
1369: else if (GET_CODE (reload_in[r]) == SUBREG
1370: && GET_CODE (SUBREG_REG (reload_in[r])) == REG)
1371: regno = REGNO (SUBREG_REG (reload_in[r])) + SUBREG_WORD (reload_in[r]);
1372: #endif
1373:
1374: if (regno >= 0
1375: && GET_MODE_SIZE (reload_mode) <= UNITS_PER_WORD
1376: && reg_last_reload_reg[regno] != 0
1377: && ! have_groups)
1378: {
1379: i = spill_reg_order[REGNO (reg_last_reload_reg[regno])];
1380:
1381: if (reg_reloaded_contents[i] == regno
1382: && TEST_HARD_REG_BIT (reg_class_contents[(int) reload_reg_class[r]],
1383: spill_regs[i])
1384: && ! reload_reg_in_use[spill_regs[i]])
1385: {
1386: /* Mark the reload register as in use for this insn. */
1387: reload_reg_rtx[r] = reg_last_reload_reg[regno];
1388: reload_reg_in_use[spill_regs[i]] = 1;
1389: reload_inherited[r] = 1;
1390: reload_spill_index[r] = i;
1391: }
1392: }
1393: }
1394:
1395: /* If this is not a pseudo, here's a different way to see
1396: if it is already lying around. */
1397: if (reload_in[r] != 0
1398: && reload_out[r] == 0
1399: && (CONSTANT_P (reload_in[r])
1400: || GET_CODE (reload_in[r]) == PLUS
1401: || GET_CODE (reload_in[r]) == MEM)
1402: && ! have_groups)
1403: {
1404: register rtx equiv
1405: = find_equiv_reg (reload_in[r], insn, reload_reg_class[r],
1406: -1, (short *)1, 0);
1407: /* If we found an equivalent reg, say no code need be generated
1408: to load it, and use it as our reload reg. */
1409: if (equiv != 0
1410: && REGNO (equiv) != FRAME_POINTER_REGNUM)
1411: {
1412: reload_reg_rtx[r] = equiv;
1413: reload_inherited[r] = 1;
1414: /* If it is a spill reg,
1415: mark the spill reg as in use for this insn. */
1416: i = spill_reg_order[REGNO (equiv)];
1417: if (i >= 0)
1418: {
1419: int nr = HARD_REGNO_NREGS (spill_regs[i], reload_mode);
1420: while (nr > 0)
1421: reload_reg_in_use[REGNO (equiv) + --nr] = 1;
1422: }
1423: }
1424: }
1425:
1426: /* If it isn't lying around, and isn't optional,
1427: find a place to reload it into. */
1428: if (reload_reg_rtx[r] != 0 || reload_optional[r] != 0)
1429: continue;
1430:
1431: /* Value not lying around; find a register to reload it into.
1432: Here I is not a regno, it is an index into spill_regs. */
1433: i = n_spills;
1434:
1435: /* If we want just one reg, and other reloads want groups,
1436: first try to find a reg that can't be part of a group. */
1437: if (have_groups && HARD_REGNO_NREGS (spill_regs[i], reload_mode) == 1)
1438: for (i = 0; i < n_spills; i++)
1439: {
1440: int regno = spill_regs[i];
1441: int class = (int) reload_reg_class[r];
1442: if (reload_reg_in_use[regno] == 0
1443: && TEST_HARD_REG_BIT (reg_class_contents[class],
1444: regno)
1445: && !(regno + 1 < FIRST_PSEUDO_REGISTER
1446: && spill_reg_order[regno + 1] >= 0
1447: && reload_reg_in_use[regno + 1] == 0
1448: && TEST_HARD_REG_BIT (reg_class_contents[class],
1449: regno - 1))
1450: && !(regno > 0
1451: && spill_reg_order[regno - 1] >= 0
1452: && reload_reg_in_use[regno - 1] == 0
1453: && TEST_HARD_REG_BIT (reg_class_contents[class],
1454: regno - 1)))
1455: break;
1456: }
1457:
1458: /* If that didn't work, try to find a register that has only one
1459: neighbor that could make a group with it. That way, if the
1460: available registers are three consecutive ones, we avoid taking
1461: the middle one (which would leave us with no possible groups). */
1462:
1463: if (have_groups && HARD_REGNO_NREGS (spill_regs[i], reload_mode) == 1
1464: && i == n_spills)
1465: for (i = 0; i < n_spills; i++)
1466: {
1467: int regno = spill_regs[i];
1468: int class = (int) reload_reg_class[r];
1469: if (reload_reg_in_use[regno] == 0
1470: && TEST_HARD_REG_BIT (reg_class_contents[class],
1471: regno)
1472: && (!(regno + 1 < FIRST_PSEUDO_REGISTER
1473: && spill_reg_order[regno + 1] >= 0
1474: && reload_reg_in_use[regno + 1] == 0
1475: && TEST_HARD_REG_BIT (reg_class_contents[class],
1476: regno - 1))
1477: || !(regno > 0
1478: && spill_reg_order[regno - 1] >= 0
1479: && reload_reg_in_use[regno - 1] == 0
1480: && TEST_HARD_REG_BIT (reg_class_contents[class],
1481: regno - 1))))
1482: break;
1483: }
1484:
1485: /* Now, if we want a single register and haven't yet found one,
1486: take any reg in the right class and not in use.
1487: If we want a consecutive group, here is where we look for it. */
1488: if (i == n_spills)
1489: for (i = 0; i < n_spills; i++)
1490: {
1491: int class = (int) reload_reg_class[r];
1492: if (reload_reg_in_use[spill_regs[i]] == 0
1493: && TEST_HARD_REG_BIT (reg_class_contents[class],
1494: spill_regs[i]))
1495: {
1496: int nr = HARD_REGNO_NREGS (spill_regs[i], reload_mode);
1497: /* If we need only one reg, we have already won. */
1498: if (nr == 1)
1499: break;
1500: /* Otherwise check that as many consecutive regs as we need
1501: are available here. */
1502: if (HARD_REGNO_MODE_OK (spill_regs[i], reload_mode))
1503: while (nr > 1)
1504: {
1505: if (!(TEST_HARD_REG_BIT (reg_class_contents[class],
1506: spill_regs[i] + nr - 1)
1507: && spill_reg_order[spill_regs[i] + nr - 1] >= 0
1508: && reload_reg_in_use[spill_regs[i] + nr - 1] == 0))
1509: break;
1510: nr--;
1511: }
1512: if (nr == 1)
1513: break;
1514: }
1515: }
1516:
1517: /* We should have found a spill register by now. */
1518: if (i == n_spills)
1519: abort ();
1520:
1521: /* Mark as in use for this insn the reload regs we use for this. */
1522: {
1523: int nr = HARD_REGNO_NREGS (spill_regs[i], reload_mode);
1524: while (nr > 0)
1525: reload_reg_in_use[spill_regs[i] + --nr] = 1;
1526: }
1527:
1528: new = spill_reg_rtx[i];
1529:
1530: if (new == 0 || GET_MODE (new) != reload_mode)
1531: spill_reg_rtx[i] = new = gen_rtx (REG, reload_mode, spill_regs[i]);
1532:
1533: reload_reg_rtx[r] = new;
1534: reload_spill_index[r] = i;
1535: reg_reloaded_contents[i] = -1;
1536:
1537: /* Detect when the reload reg can't hold the reload mode. */
1538: if (! HARD_REGNO_MODE_OK (REGNO (reload_reg_rtx[r]), reload_mode))
1539: {
1540: if (! asm_noperands (PATTERN (insn)))
1541: /* It's the compiler's fault. */
1542: abort ();
1543: /* It's the user's fault; the operand's mode and constraint
1544: don't match. Disable this reload so we don't crash in final.
1545: Maybe we should print an error message too?? */
1546: reload_in[r] = 0;
1547: reload_out[r] = 0;
1548: reload_reg_rtx[r] = 0;
1549: reload_optional[r] = 1;
1550: }
1551: }
1552:
1553: /* For all the spill regs newly reloaded in this instruction,
1554: record what they were reloaded from, so subsequent instructions
1555: can inherit the reloads. */
1556:
1557: for (j = 0; j < n_reloads; j++)
1558: {
1559: register int r = reload_order[j];
1560: register int i = reload_spill_index[r];
1561:
1562: /* I is nonneg if this reload used one of the spill regs.
1563: If reload_reg_rtx[r] is 0, this is an optional reload
1564: that we opted to ignore. */
1565: if (i >= 0 && reload_reg_rtx[r] != 0)
1566: {
1567: /* Maybe the spill reg contains a copy of reload_out. */
1568: if (reload_out[r] != 0 && GET_CODE (reload_out[r]) == REG)
1569: {
1570: register int nregno = REGNO (reload_out[r]);
1571: reg_last_reload_reg[nregno] = reload_reg_rtx[r];
1572: reg_reloaded_contents[i] = nregno;
1573: reg_has_output_reload[nregno] = 1;
1574: }
1575: /* Maybe the spill reg contains a copy of reload_in. */
1576: else if (reload_out[r] == 0 && GET_CODE (reload_in[r]) == REG)
1577: {
1578: register int nregno = REGNO (reload_in[r]);
1579: /* If there are two separate reloads (one in and one out)
1580: for the same (hard or pseudo) reg, set reg_last_reload_reg
1581: based on the output reload. */
1582: if (!reg_has_output_reload[nregno])
1583: {
1584: reg_last_reload_reg[nregno] = reload_reg_rtx[r];
1585: reg_reloaded_contents[i] = nregno;
1586: }
1587: }
1588: /* Otherwise, the spill reg doesn't contain a copy of any reg.
1589: Clear out its records, lest it be taken for a copy
1590: of reload_in when that is no longer true. */
1591: else
1592: reg_reloaded_contents[i] = -1;
1593: }
1594: }
1595:
1596: /* Now output the instructions to copy the data into and out of the
1597: reload registers. Do these in the order that the reloads were reported,
1598: since reloads of base and index registers precede reloads of operands
1599: and the operands may need the base and index registers reloaded. */
1600:
1601: for (j = 0; j < n_reloads; j++)
1602: {
1603: register rtx old;
1604: rtx store_insn;
1605:
1606: old = reload_in[j];
1607: if (old != 0 && ! reload_inherited[j]
1608: && reload_reg_rtx[j] != old
1609: && reload_reg_rtx[j] != 0)
1610: {
1611: register rtx reloadreg = reload_reg_rtx[j];
1612: rtx oldequiv = 0;
1613: enum machine_mode mode;
1614:
1615: /* Strip off of OLD any size-increasing SUBREGs such as
1616: (SUBREG:SI foo:QI 0). */
1617:
1618: while (GET_CODE (old) == SUBREG && SUBREG_WORD (old) == 0
1619: && (GET_MODE_SIZE (GET_MODE (old))
1620: > GET_MODE_SIZE (GET_MODE (SUBREG_REG (old)))))
1621: old = SUBREG_REG (old);
1622:
1623: /* If reloading from memory, see if there is a register
1624: that already holds the same value. If so, reload from there.
1625: We can pass 0 as the reload_reg_p argument because
1626: any other reload has either already been emitted,
1627: in which case find_equiv_reg will see the reload-insn,
1628: or has yet to be emitted, in which case it doesn't matter
1629: because we will use this equiv reg right away. */
1630:
1631: if (GET_CODE (old) == MEM
1632: || (GET_CODE (old) == REG
1633: && REGNO (old) >= FIRST_PSEUDO_REGISTER
1634: && reg_renumber[REGNO (old)] < 0))
1635: oldequiv = find_equiv_reg (old, insn, GENERAL_REGS, -1, 0, 0);
1636:
1637: if (oldequiv == 0)
1638: oldequiv = old;
1639:
1640: /* Determine the mode to reload in.
1641: This is very tricky because we have three to choose from.
1642: There is the mode the insn operand wants (reload_inmode[J]).
1643: There is the mode of the reload register RELOADREG.
1644: There is the intrinsic mode of the operand, revealed now
1645: in OLD because we have stripped SUBREGs.
1646: It turns out that RELOADREG's mode is irrelevant:
1647: we can change that arbitrarily.
1648:
1649: Neither of the other two is always right. For example, consider
1650: (SUBREG:SI foo:QI)) appearing as an operand that must be SImode;
1651: then suppose foo is in memory. This must be loaded in QImode
1652: because we cannot fetch a byte as a word. In this case OLD's
1653: mode is correct.
1654:
1655: Then consider a one-word union which has SImode and one of its
1656: members is a float, being fetched as (SUBREG:SF union:SI).
1657: We must fetch that as SFmode because we could be loading into
1658: a float-only register. In this case OLD's mode is also correct.
1659:
1660: Consider an immediate integer: it has VOIDmode. Here we need
1661: to get a mode from something else.
1662:
1663: In some cases, there is a fourth mode, the operand's
1664: containing mode. If the insn specifies a containing mode for
1665: this operand, it overrides all others.
1666:
1667: I am not sure whether the algorithm here is always right,
1668: but it does the right things in those cases. */
1669:
1670: mode = GET_MODE (old);
1671: if (mode == VOIDmode)
1672: mode = reload_inmode[j];
1673: if (reload_strict_low[j])
1674: mode = GET_MODE (SUBREG_REG (reload_in[j]));
1675:
1676: /* Encapsulate both RELOADREG and OLDEQUIV into that mode,
1677: then load RELOADREG from OLDEQUIV. */
1678:
1679: if (GET_MODE (reloadreg) != mode)
1680: reloadreg = gen_rtx (SUBREG, mode, reloadreg, 0);
1681: if (GET_MODE (oldequiv) != VOIDmode
1682: && mode != GET_MODE (oldequiv))
1683: oldequiv = gen_rtx (SUBREG, mode, oldequiv, 0);
1684:
1685: /* If we are reloading a pseudo-register that was set by the previous
1686: insn, see if we can get rid of that pseudo-register entirely
1687: by redirecting the previous insn into our reload register. */
1688:
1689: if (optimize && GET_CODE (old) == REG
1690: && REGNO (old) >= FIRST_PSEUDO_REGISTER
1691: && PREV_INSN (insn) && GET_CODE (PREV_INSN (insn)) == INSN
1692: && GET_CODE (PATTERN (PREV_INSN (insn))) == SET
1693: && SET_DEST (PATTERN (PREV_INSN (insn))) == old
1694: && dead_or_set_p (insn, old)
1695: && reg_n_deaths[REGNO (old)] == 1
1696: && reg_n_sets[REGNO (old)] == 1)
1697: {
1698: /* For the debugging info,
1699: say the pseudo lives in this reload reg. */
1700: reg_renumber[REGNO (old)] = REGNO (reload_reg_rtx[j]);
1701: alter_reg (REGNO (old));
1702: /* Store into the reload register instead of the pseudo. */
1703: SET_DEST (PATTERN (PREV_INSN (insn))) = reloadreg;
1704: }
1705: else
1706: /* We can't do that, so output an insn to load RELOADREG. */
1707: emit_insn_before (gen_move_insn (reloadreg, oldequiv), insn);
1708:
1709: /* If this reload wants reload_in[j] incremented by a constant,
1710: output code to get this done before the insn reloaded for. */
1711:
1712: if (reload_inc[j] != 0)
1713: {
1714: /* If reload_in[j] is a register, assume we can
1715: output an insn to increment it directly. */
1716: if (GET_CODE (old) == REG &&
1717: (REGNO (old) < FIRST_PSEUDO_REGISTER
1718: || reg_renumber[REGNO (old)] >= 0))
1719: emit_insn_before (gen_add2_insn (old,
1720: gen_rtx (CONST_INT, VOIDmode,
1721: reload_inc[j])),
1722: insn);
1723: else
1724: /* Else we must not assume we can increment reload_in[j]
1725: (even though on many target machines we can);
1726: increment the copy in the reload register,
1727: save that back, then decrement the reload register
1728: so it has its original contents. */
1729: {
1730: emit_insn_before (gen_add2_insn (reloadreg,
1731: gen_rtx (CONST_INT, VOIDmode,
1732: reload_inc[j])),
1733: insn);
1734: emit_insn_before (gen_move_insn (oldequiv, reloadreg), insn);
1735: emit_insn_before (gen_sub2_insn (reloadreg,
1736: gen_rtx (CONST_INT, VOIDmode,
1737: reload_inc[j])),
1738: insn);
1739: }
1740: }
1741: }
1742:
1743: /* If we are reloading a register that was recently stored in with an
1744: output-reload, see if we can prove there was
1745: actually no need to store the old value in it. */
1746:
1747: if (optimize && reload_inherited[j] && reload_spill_index[j] >= 0
1748: && GET_CODE (reload_in[j]) == REG
1749: && spill_reg_store[reload_spill_index[j]] != 0
1750: && dead_or_set_p (insn, reload_in[j]))
1751: {
1752: register rtx i1;
1753: /* If the pseudo-reg we are reloading is no longer referenced
1754: anywhere between the store into it and here,
1755: and no jumps or labels intervene, then the value can get
1756: here through the reload reg alone. */
1757: for (i1 = NEXT_INSN (spill_reg_store[reload_spill_index[j]]);
1758: i1 != insn; i1 = NEXT_INSN (i1))
1759: {
1760: if (GET_CODE (i1) == CODE_LABEL || GET_CODE (i1) == JUMP_INSN)
1761: break;
1762: if ((GET_CODE (i1) == INSN || GET_CODE (i1) == CALL_INSN)
1763: && reg_mentioned_p (reload_in[j], PATTERN (i1)))
1764: break;
1765: }
1766: if (i1 == insn)
1767: {
1768: /* If this insn will store in the pseudo again,
1769: the previous store can be removed. */
1770: if (reload_out[j] == reload_in[j])
1771: delete_insn (spill_reg_store[reload_spill_index[j]]);
1772:
1773: /* See if the pseudo reg has been completely replaced
1774: with reload regs. If so, delete the store insn
1775: and forget we had a stack slot for the pseudo. */
1776: if (reg_n_deaths[REGNO (reload_in[j])] == 1
1777: && reg_basic_block[REGNO (reload_in[j])] >= 0)
1778: {
1779: /* We know that it was used only between here
1780: and the beginning of the current basic block.
1781: Search that range; see if any ref remains. */
1782: for (i1 = PREV_INSN (insn); i1; i1 = PREV_INSN (i1))
1783: {
1784: if (GET_CODE (i1) == CODE_LABEL
1785: || GET_CODE (i1) == JUMP_INSN)
1786: break;
1787: if ((GET_CODE (i1) == INSN || GET_CODE (i1) == CALL_INSN)
1788: && reg_mentioned_p (reload_in[j], PATTERN (i1)))
1789: goto still_used;
1790: }
1791: /* For the debugging info,
1792: say the pseudo lives in this reload reg. */
1793: reg_renumber[REGNO (old)] = REGNO (reload_reg_rtx[j]);
1794: alter_reg (REGNO (old));
1795: delete_insn (spill_reg_store[reload_spill_index[j]]);
1796: still_used: ;
1797: }
1798: }
1799: }
1800:
1801: /* Input-reloading is done. Now do output-reloading,
1802: storing the value from the reload-register after the main insn
1803: if reload_out[j] is nonzero. */
1804: old = reload_out[j];
1805: if (old != 0
1806: && reload_reg_rtx[j] != old
1807: && reload_reg_rtx[j] != 0)
1808: {
1809: register rtx reloadreg = reload_reg_rtx[j];
1810: enum machine_mode mode;
1811:
1812: /* Strip off of OLD any size-increasing SUBREGs such as
1813: (SUBREG:SI foo:QI 0). */
1814:
1815: while (GET_CODE (old) == SUBREG && SUBREG_WORD (old) == 0
1816: && (GET_MODE_SIZE (GET_MODE (old))
1817: > GET_MODE_SIZE (GET_MODE (SUBREG_REG (old)))))
1818: old = SUBREG_REG (old);
1819:
1820: /* Determine the mode to reload in.
1821: See comments above (for input reloading). */
1822:
1823: mode = GET_MODE (old);
1824: if (mode == VOIDmode)
1825: abort (); /* Should never happen for an output. */
1826: #if 0
1827: mode = reload_inmode[j];
1828: #endif
1829: if (reload_strict_low[j])
1830: mode = GET_MODE (SUBREG_REG (reload_out[j]));
1831:
1832: /* Encapsulate both RELOADREG and OLD into that mode,
1833: then load RELOADREG from OLD. */
1834: if (GET_MODE (reloadreg) != mode)
1835: reloadreg = gen_rtx (SUBREG, mode, reloadreg, 0);
1836: if (GET_MODE (old) != VOIDmode
1837: && mode != GET_MODE (old))
1838: old = gen_rtx (SUBREG, mode, old, 0);
1839: store_insn = emit_insn_after (gen_move_insn (old, reloadreg), insn);
1840: }
1841: else store_insn = 0;
1842:
1843: if (reload_spill_index[j] >= 0)
1844: spill_reg_store[reload_spill_index[j]] = store_insn;
1845: }
1846: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.