![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to stupid.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 stupid.c CVS log | Up to [Apple XNU] / GNUtools / cc |
1.1 root 1: /* Dummy data flow analysis for GNU compiler in nonoptimizing mode.
2: Copyright (C) 1987, 1991 Free Software Foundation, Inc.
3:
4: This file is part of GNU CC.
5:
6: GNU CC is free software; you can redistribute it and/or modify
7: it under the terms of the GNU General Public License as published by
8: the Free Software Foundation; either version 2, or (at your option)
9: any later version.
10:
11: GNU CC is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14: GNU General Public License for more details.
15:
16: You should have received a copy of the GNU General Public License
17: along with GNU CC; see the file COPYING. If not, write to
18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20:
21: /* This file performs stupid register allocation, which is used
22: when cc1 gets the -noreg switch (which is when cc does not get -O).
23:
24: Stupid register allocation goes in place of the the flow_analysis,
25: local_alloc and global_alloc passes. combine_instructions cannot
26: be done with stupid allocation because the data flow info that it needs
27: is not computed here.
28:
29: In stupid allocation, the only user-defined variables that can
30: go in registers are those declared "register". They are assumed
31: to have a life span equal to their scope. Other user variables
32: are given stack slots in the rtl-generation pass and are not
33: represented as pseudo regs. A compiler-generated temporary
34: is assumed to live from its first mention to its last mention.
35:
36: Since each pseudo-reg's life span is just an interval, it can be
37: represented as a pair of numbers, each of which identifies an insn by
38: its position in the function (number of insns before it). The first
39: thing done for stupid allocation is to compute such a number for each
40: insn. It is called the suid. Then the life-interval of each
41: pseudo reg is computed. Then the pseudo regs are ordered by priority
42: and assigned hard regs in priority order. */
43:
44: #include <stdio.h>
45: #include "config.h"
46: #include "rtl.h"
47: #include "hard-reg-set.h"
48: #include "regs.h"
49: #include "flags.h"
50:
51: /* Vector mapping INSN_UIDs to suids.
52: The suids are like uids but increase monotonically always.
53: We use them to see whether a subroutine call came
54: between a variable's birth and its death. */
55:
56: static int *uid_suid;
57:
58: /* Get the suid of an insn. */
59:
60: #define INSN_SUID(INSN) (uid_suid[INSN_UID (INSN)])
61:
62: /* Record the suid of the last CALL_INSN
63: so we can tell whether a pseudo reg crosses any calls. */
64:
65: static int last_call_suid;
66:
67: /* Record the suid of the last JUMP_INSN
68: so we can tell whether a pseudo reg crosses any jumps. */
69:
70: static int last_jump_suid;
71:
72: /* Record the suid of the last CODE_LABEL
73: so we can tell whether a pseudo reg crosses any labels. */
74:
75: static int last_label_suid;
76:
77: /* Element N is suid of insn where life span of pseudo reg N ends.
78: Element is 0 if register N has not been seen yet on backward scan. */
79:
80: static int *reg_where_dead;
81:
82: /* Element N is suid of insn where life span of pseudo reg N begins. */
83:
84: static int *reg_where_born;
85:
86: /* Element N is 1 if pseudo reg N lives across labels or jumps. */
87:
88: static char *reg_crosses_blocks;
89:
90: /* Numbers of pseudo-regs to be allocated, highest priority first. */
91:
92: static int *reg_order;
93:
94: /* Indexed by reg number (hard or pseudo), nonzero if register is live
95: at the current point in the instruction stream. */
96:
97: static char *regs_live;
98:
99: /* Indexed by insn's suid, the set of hard regs live after that insn. */
100:
101: static HARD_REG_SET *after_insn_hard_regs;
102:
103: /* Record that hard reg REGNO is live after insn INSN. */
104:
105: #define MARK_LIVE_AFTER(INSN,REGNO) \
106: SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (INSN)], (REGNO))
107:
108: static void stupid_mark_refs ();
109: static int stupid_reg_compare ();
110: static int stupid_find_reg ();
111:
112: /* Stupid life analysis is for the case where only variables declared
113: `register' go in registers. For this case, we mark all
114: pseudo-registers that belong to register variables as
115: dying in the last instruction of the function, and all other
116: pseudo registers as dying in the last place they are referenced.
117: Hard registers are marked as dying in the last reference before
118: the end or before each store into them. */
119:
120: void
121: stupid_life_analysis (f, nregs, file)
122: rtx f;
123: int nregs;
124: FILE *file;
125: {
126: register int i;
127: register rtx last, insn;
128: int max_uid;
129:
130: bzero (regs_ever_live, sizeof regs_ever_live);
131:
132: regs_live = (char *) alloca (nregs);
133:
134: /* First find the last real insn, and count the number of insns,
135: and assign insns their suids. */
136:
137: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
138: if (INSN_UID (insn) > i)
139: i = INSN_UID (insn);
140:
141: max_uid = i + 1;
142: uid_suid = (int *) alloca ((i + 1) * sizeof (int));
143:
144: /* Compute the mapping from uids to suids.
145: Suids are numbers assigned to insns, like uids,
146: except that suids increase monotonically through the code. */
147:
148: last = 0; /* In case of empty function body */
149: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
150: {
151: if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN
152: || GET_CODE (insn) == JUMP_INSN)
153: last = insn;
154: INSN_SUID (insn) = ++i;
155: }
156:
157: last_call_suid = i + 1;
158: last_jump_suid = i + 1;
159: last_label_suid = i + 1;
160:
161: max_regno = nregs;
162:
163: /* Allocate tables to record info about regs. */
164:
165: reg_where_dead = (int *) alloca (nregs * sizeof (int));
166: bzero (reg_where_dead, nregs * sizeof (int));
167:
168: reg_where_born = (int *) alloca (nregs * sizeof (int));
169: bzero (reg_where_born, nregs * sizeof (int));
170:
171: reg_crosses_blocks = (char *) alloca (nregs);
172: bzero (reg_crosses_blocks, nregs);
173:
174: reg_order = (int *) alloca (nregs * sizeof (int));
175: bzero (reg_order, nregs * sizeof (int));
176:
177: reg_renumber = (short *) oballoc (nregs * sizeof (short));
178: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
179: reg_renumber[i] = i;
180:
181: for (i = FIRST_VIRTUAL_REGISTER; i <= LAST_VIRTUAL_REGISTER; i++)
182: reg_renumber[i] = -1;
183:
184: after_insn_hard_regs = (HARD_REG_SET *) alloca (max_uid * sizeof (HARD_REG_SET));
185: bzero (after_insn_hard_regs, max_uid * sizeof (HARD_REG_SET));
186:
187: /* Allocate and zero out many data structures
188: that will record the data from lifetime analysis. */
189:
190: allocate_for_life_analysis ();
191:
192: for (i = 0; i < max_regno; i++)
193: {
194: reg_n_deaths[i] = 1;
195: }
196:
197: bzero (regs_live, nregs);
198:
199: /* Find where each pseudo register is born and dies,
200: by scanning all insns from the end to the start
201: and noting all mentions of the registers.
202:
203: Also find where each hard register is live
204: and record that info in after_insn_hard_regs.
205: regs_live[I] is 1 if hard reg I is live
206: at the current point in the scan. */
207:
208: for (insn = last; insn; insn = PREV_INSN (insn))
209: {
210: register HARD_REG_SET *p = after_insn_hard_regs + INSN_SUID (insn);
211:
212: /* Copy the info in regs_live
213: into the element of after_insn_hard_regs
214: for the current position in the rtl code. */
215:
216: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
217: if (regs_live[i])
218: SET_HARD_REG_BIT (*p, i);
219:
220: /* Mark all call-clobbered regs as live after each call insn
221: so that a pseudo whose life span includes this insn
222: will not go in one of them.
223: Then mark those regs as all dead for the continuing scan
224: of the insns before the call. */
225:
226: if (GET_CODE (insn) == CALL_INSN)
227: {
228: last_call_suid = INSN_SUID (insn);
229: IOR_HARD_REG_SET (after_insn_hard_regs[last_call_suid],
230: call_used_reg_set);
231: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
232: if (call_used_regs[i])
233: regs_live[i] = 0;
234: }
235:
236: if (GET_CODE (insn) == JUMP_INSN)
237: last_jump_suid = INSN_SUID (insn);
238:
239: if (GET_CODE (insn) == CODE_LABEL)
240: last_label_suid = INSN_SUID (insn);
241:
242: /* Update which hard regs are currently live
243: and also the birth and death suids of pseudo regs
244: based on the pattern of this insn. */
245:
246: if (GET_CODE (insn) == INSN
247: || GET_CODE (insn) == CALL_INSN
248: || GET_CODE (insn) == JUMP_INSN)
249: {
250: stupid_mark_refs (PATTERN (insn), insn);
251: }
252: }
253:
254: /* Now decide the order in which to allocate the pseudo registers. */
255:
256: for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++)
257: reg_order[i] = i;
258:
259: qsort (®_order[LAST_VIRTUAL_REGISTER + 1],
260: max_regno - LAST_VIRTUAL_REGISTER - 1, sizeof (int),
261: stupid_reg_compare);
262:
263: /* Now, in that order, try to find hard registers for those pseudo regs. */
264:
265: for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++)
266: {
267: register int r = reg_order[i];
268: enum reg_class class;
269:
270: /* Some regnos disappear from the rtl. Ignore them to avoid crash. */
271: if (regno_reg_rtx[r] == 0)
272: continue;
273:
274: /* Now find the best hard-register class for this pseudo register */
275: if (N_REG_CLASSES > 1)
276: {
277: class = reg_preferred_class (r);
278:
279: reg_renumber[r] = stupid_find_reg (reg_n_calls_crossed[r], class,
280: PSEUDO_REGNO_MODE (r),
281: reg_where_born[r],
282: reg_where_dead[r],
283: reg_crosses_blocks[r]);
284: }
285: else
286: reg_renumber[r] = -1;
287:
288: /* If no reg available in that class,
289: try any reg. */
290: if (reg_renumber[r] == -1)
291: reg_renumber[r] = stupid_find_reg (reg_n_calls_crossed[r],
292: GENERAL_REGS,
293: PSEUDO_REGNO_MODE (r),
294: reg_where_born[r],
295: reg_where_dead[r],
296: reg_crosses_blocks[r]);
297: }
298:
299: if (file)
300: dump_flow_info (file);
301: }
302:
303: /* Comparison function for qsort.
304: Returns -1 (1) if register *R1P is higher priority than *R2P. */
305:
306: static int
307: stupid_reg_compare (r1p, r2p)
308: int *r1p, *r2p;
309: {
310: register int r1 = *r1p, r2 = *r2p;
311: register int len1 = reg_where_dead[r1] - reg_where_born[r1];
312: register int len2 = reg_where_dead[r2] - reg_where_born[r2];
313: int tem;
314:
315: tem = len2 - len1;
316: if (tem != 0) return tem;
317:
318: tem = reg_n_refs[r1] - reg_n_refs[r2];
319: if (tem != 0) return tem;
320:
321: /* If regs are equally good, sort by regno,
322: so that the results of qsort leave nothing to chance. */
323: return r1 - r2;
324: }
325:
326: /* Find a block of SIZE words of hard registers in reg_class CLASS
327: that can hold a value of machine-mode MODE
328: (but actually we test only the first of the block for holding MODE)
329: currently free from after insn whose suid is BIRTH
330: through the insn whose suid is DEATH,
331: and return the number of the first of them.
332: Return -1 if such a block cannot be found.
333:
334: If CALL_PRESERVED is nonzero, insist on registers preserved
335: over subroutine calls, and return -1 if cannot find such.
336: If CROSSES_BLOCKS is nonzero, reject registers for which
337: PRESERVE_DEATH_INFO_REGNO_P is true. */
338:
339: static int
340: stupid_find_reg (call_preserved, class, mode,
341: born_insn, dead_insn, crosses_blocks)
342: int call_preserved;
343: enum reg_class class;
344: enum machine_mode mode;
345: int born_insn, dead_insn;
346: int crosses_blocks;
347: {
348: register int i, ins;
349: #ifdef HARD_REG_SET
350: register /* Declare them register if they are scalars. */
351: #endif
352: HARD_REG_SET used, this_reg;
353: #ifdef ELIMINABLE_REGS
354: static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
355: #endif
356:
357: COPY_HARD_REG_SET (used,
358: call_preserved ? call_used_reg_set : fixed_reg_set);
359:
360: #ifdef ELIMINABLE_REGS
361: for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
362: SET_HARD_REG_BIT (used, eliminables[i].from);
363: #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
364: SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM);
365: #endif
366: #else
367: SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM);
368: #endif
369:
370: for (ins = born_insn; ins < dead_insn; ins++)
371: IOR_HARD_REG_SET (used, after_insn_hard_regs[ins]);
372:
373: IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]);
374:
375: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
376: {
377: #ifdef REG_ALLOC_ORDER
378: int regno = reg_alloc_order[i];
379: #else
380: int regno = i;
381: #endif
382:
383: /* If we need reasonable death info on this hard reg,
384: don't use it for anything whose life spans a label or a jump. */
385: #ifdef PRESERVE_DEATH_INFO_REGNO_P
386: if (PRESERVE_DEATH_INFO_REGNO_P (regno)
387: && crosses_blocks)
388: continue;
389: #endif
390: /* If a register has screwy overlap problems,
391: don't use it at all if not optimizing.
392: Actually this is only for the 387 stack register,
393: and it's because subsequent code won't work. */
394: #ifdef OVERLAPPING_REGNO_P
395: if (OVERLAPPING_REGNO_P (regno))
396: continue;
397: #endif
398:
399: if (! TEST_HARD_REG_BIT (used, regno)
400: && HARD_REGNO_MODE_OK (regno, mode))
401: {
402: register int j;
403: register int size1 = HARD_REGNO_NREGS (regno, mode);
404: for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++);
405: if (j == size1)
406: {
407: CLEAR_HARD_REG_SET (this_reg);
408: while (--j >= 0)
409: SET_HARD_REG_BIT (this_reg, regno + j);
410: for (ins = born_insn; ins < dead_insn; ins++)
411: {
412: IOR_HARD_REG_SET (after_insn_hard_regs[ins], this_reg);
413: }
414: return regno;
415: }
416: #ifndef REG_ALLOC_ORDER
417: i += j; /* Skip starting points we know will lose */
418: #endif
419: }
420: }
421: return -1;
422: }
423:
424: /* Walk X, noting all assignments and references to registers
425: and recording what they imply about life spans.
426: INSN is the current insn, supplied so we can find its suid. */
427:
428: static void
429: stupid_mark_refs (x, insn)
430: rtx x, insn;
431: {
432: register RTX_CODE code = GET_CODE (x);
433: register char *fmt;
434: register int regno, i;
435:
436: if (code == SET || code == CLOBBER)
437: {
438: if (SET_DEST (x) != 0 && GET_CODE (SET_DEST (x)) == REG)
439: {
440: /* Register is being assigned. */
441: regno = REGNO (SET_DEST (x));
442:
443: /* For hard regs, update the where-live info. */
444: if (regno < FIRST_PSEUDO_REGISTER)
445: {
446: register int j
447: = HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (x)));
448: while (--j >= 0)
449: {
450: regs_ever_live[regno+j] = 1;
451: regs_live[regno+j] = 0;
452: /* The following line is for unused outputs;
453: they do get stored even though never used again. */
454: MARK_LIVE_AFTER (insn, regno);
455: /* When a hard reg is clobbered, mark it in use
456: just before this insn, so it is live all through. */
457: if (code == CLOBBER && INSN_SUID (insn) > 0)
458: SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (insn) - 1],
459: regno);
460: }
461: }
462: /* For pseudo regs, record where born, where dead, number of
463: times used, and whether live across a call. */
464: else
465: {
466: /* Update the life-interval bounds of this pseudo reg. */
467:
468: /* When a pseudo-reg is CLOBBERed, it is born just before
469: the clobbering insn. When setting, just after. */
470: int where_born = INSN_SUID (insn) - (code == CLOBBER);
471:
472: reg_where_born[regno] = where_born;
473: /* The reg must live at least one insn even
474: in it is never again used--because it has to go
475: in SOME hard reg. Mark it as dying after the current
476: insn so that it will conflict with any other outputs of
477: this insn. */
478: if (reg_where_dead[regno] < where_born + 2)
479: reg_where_dead[regno] = where_born + 2;
480:
481: /* Count the refs of this reg. */
482: reg_n_refs[regno]++;
483:
484: if (last_call_suid < reg_where_dead[regno])
485: reg_n_calls_crossed[regno] += 1;
486: if (last_jump_suid < reg_where_dead[regno]
487: || last_label_suid < reg_where_dead[regno])
488: reg_crosses_blocks[regno] = 1;
489: }
490: }
491: /* Record references from the value being set,
492: or from addresses in the place being set if that's not a reg.
493: If setting a SUBREG, we treat the entire reg as *used*. */
494: if (code == SET)
495: {
496: stupid_mark_refs (SET_SRC (x), insn);
497: if (GET_CODE (SET_DEST (x)) != REG)
498: stupid_mark_refs (SET_DEST (x), insn);
499: }
500: return;
501: }
502:
503: /* Register value being used, not set. */
504:
505: if (code == REG)
506: {
507: regno = REGNO (x);
508: if (regno < FIRST_PSEUDO_REGISTER)
509: {
510: /* Hard reg: mark it live for continuing scan of previous insns. */
511: register int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
512: while (--j >= 0)
513: {
514: regs_ever_live[regno+j] = 1;
515: regs_live[regno+j] = 1;
516: }
517: }
518: else
519: {
520: /* Pseudo reg: record first use, last use and number of uses. */
521:
522: reg_where_born[regno] = INSN_SUID (insn);
523: reg_n_refs[regno]++;
524: if (regs_live[regno] == 0)
525: {
526: regs_live[regno] = 1;
527: reg_where_dead[regno] = INSN_SUID (insn);
528: }
529: }
530: return;
531: }
532:
533: /* Recursive scan of all other rtx's. */
534:
535: fmt = GET_RTX_FORMAT (code);
536: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
537: {
538: if (fmt[i] == 'e')
539: stupid_mark_refs (XEXP (x, i), insn);
540: if (fmt[i] == 'E')
541: {
542: register int j;
543: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
544: stupid_mark_refs (XVECEXP (x, i, j), insn);
545: }
546: }
547: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.