1 /* Dummy data flow analysis for GNU compiler in nonoptimizing mode.
2 Copyright (C) 1987, 1991, 1994, 1995, 1996 Free Software Foundation, Inc.
4 This file is part of GNU CC.
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)
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.
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, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
22 /* This file performs stupid register allocation, which is used
23 when cc1 gets the -noreg switch (which is when cc does not get -O).
25 Stupid register allocation goes in place of the the flow_analysis,
26 local_alloc and global_alloc passes. combine_instructions cannot
27 be done with stupid allocation because the data flow info that it needs
30 In stupid allocation, the only user-defined variables that can
31 go in registers are those declared "register". They are assumed
32 to have a life span equal to their scope. Other user variables
33 are given stack slots in the rtl-generation pass and are not
34 represented as pseudo regs. A compiler-generated temporary
35 is assumed to live from its first mention to its last mention.
37 Since each pseudo-reg's life span is just an interval, it can be
38 represented as a pair of numbers, each of which identifies an insn by
39 its position in the function (number of insns before it). The first
40 thing done for stupid allocation is to compute such a number for each
41 insn. It is called the suid. Then the life-interval of each
42 pseudo reg is computed. Then the pseudo regs are ordered by priority
43 and assigned hard regs in priority order. */
48 #include "hard-reg-set.h"
52 /* Vector mapping INSN_UIDs to suids.
53 The suids are like uids but increase monotonically always.
54 We use them to see whether a subroutine call came
55 between a variable's birth and its death. */
59 /* Get the suid of an insn. */
61 #define INSN_SUID(INSN) (uid_suid[INSN_UID (INSN)])
63 /* Record the suid of the last CALL_INSN
64 so we can tell whether a pseudo reg crosses any calls. */
66 static int last_call_suid;
68 /* Record the suid of the last NOTE_INSN_SETJMP
69 so we can tell whether a pseudo reg crosses any setjmp. */
71 static int last_setjmp_suid;
73 /* Element N is suid of insn where life span of pseudo reg N ends.
74 Element is 0 if register N has not been seen yet on backward scan. */
76 static int *reg_where_dead;
78 /* Element N is suid of insn where life span of pseudo reg N begins. */
80 static int *reg_where_born;
82 /* Numbers of pseudo-regs to be allocated, highest priority first. */
84 static int *reg_order;
86 /* Indexed by reg number (hard or pseudo), nonzero if register is live
87 at the current point in the instruction stream. */
89 static char *regs_live;
91 /* Indexed by reg number, nonzero if reg was used in a SUBREG that changes
94 static char *regs_change_size;
96 /* Indexed by reg number, nonzero if reg crosses a setjmp. */
98 static char *regs_crosses_setjmp;
100 /* Indexed by insn's suid, the set of hard regs live after that insn. */
102 static HARD_REG_SET *after_insn_hard_regs;
104 /* Record that hard reg REGNO is live after insn INSN. */
106 #define MARK_LIVE_AFTER(INSN,REGNO) \
107 SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (INSN)], (REGNO))
109 static int stupid_reg_compare PROTO((const GENERIC_PTR,const GENERIC_PTR));
110 static int stupid_find_reg PROTO((int, enum reg_class, enum machine_mode,
112 static void stupid_mark_refs PROTO((rtx, rtx));
114 /* Stupid life analysis is for the case where only variables declared
115 `register' go in registers. For this case, we mark all
116 pseudo-registers that belong to register variables as
117 dying in the last instruction of the function, and all other
118 pseudo registers as dying in the last place they are referenced.
119 Hard registers are marked as dying in the last reference before
120 the end or before each store into them. */
123 stupid_life_analysis (f, nregs, file)
129 register rtx last, insn;
130 int max_uid, max_suid;
132 bzero (regs_ever_live, sizeof regs_ever_live);
134 regs_live = (char *) alloca (nregs);
136 /* First find the last real insn, and count the number of insns,
137 and assign insns their suids. */
139 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
140 if (INSN_UID (insn) > i)
144 uid_suid = (int *) alloca ((i + 1) * sizeof (int));
146 /* Compute the mapping from uids to suids.
147 Suids are numbers assigned to insns, like uids,
148 except that suids increase monotonically through the code. */
150 last = 0; /* In case of empty function body */
151 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
153 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
156 INSN_SUID (insn) = ++i;
159 last_call_suid = i + 1;
160 last_setjmp_suid = i + 1;
165 /* Allocate tables to record info about regs. */
167 reg_where_dead = (int *) alloca (nregs * sizeof (int));
168 bzero ((char *) reg_where_dead, nregs * sizeof (int));
170 reg_where_born = (int *) alloca (nregs * sizeof (int));
171 bzero ((char *) reg_where_born, nregs * sizeof (int));
173 reg_order = (int *) alloca (nregs * sizeof (int));
174 bzero ((char *) reg_order, nregs * sizeof (int));
176 regs_change_size = (char *) alloca (nregs * sizeof (char));
177 bzero ((char *) regs_change_size, nregs * sizeof (char));
179 regs_crosses_setjmp = (char *) alloca (nregs * sizeof (char));
180 bzero ((char *) regs_crosses_setjmp, nregs * sizeof (char));
182 reg_renumber = (short *) oballoc (nregs * sizeof (short));
183 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
186 for (i = FIRST_VIRTUAL_REGISTER; i < max_regno; i++)
187 reg_renumber[i] = -1;
190 = (HARD_REG_SET *) alloca (max_suid * sizeof (HARD_REG_SET));
192 bzero ((char *) after_insn_hard_regs, max_suid * sizeof (HARD_REG_SET));
194 /* Allocate and zero out many data structures
195 that will record the data from lifetime analysis. */
197 allocate_for_life_analysis ();
199 for (i = 0; i < max_regno; i++)
202 bzero (regs_live, nregs);
204 /* Find where each pseudo register is born and dies,
205 by scanning all insns from the end to the start
206 and noting all mentions of the registers.
208 Also find where each hard register is live
209 and record that info in after_insn_hard_regs.
210 regs_live[I] is 1 if hard reg I is live
211 at the current point in the scan. */
213 for (insn = last; insn; insn = PREV_INSN (insn))
215 register HARD_REG_SET *p = after_insn_hard_regs + INSN_SUID (insn);
217 /* Copy the info in regs_live into the element of after_insn_hard_regs
218 for the current position in the rtl code. */
220 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
222 SET_HARD_REG_BIT (*p, i);
224 /* Update which hard regs are currently live
225 and also the birth and death suids of pseudo regs
226 based on the pattern of this insn. */
228 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
229 stupid_mark_refs (PATTERN (insn), insn);
231 if (GET_CODE (insn) == NOTE
232 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
233 last_setjmp_suid = INSN_SUID (insn);
235 /* Mark all call-clobbered regs as live after each call insn
236 so that a pseudo whose life span includes this insn
237 will not go in one of them.
238 Then mark those regs as all dead for the continuing scan
239 of the insns before the call. */
241 if (GET_CODE (insn) == CALL_INSN)
243 last_call_suid = INSN_SUID (insn);
244 IOR_HARD_REG_SET (after_insn_hard_regs[last_call_suid],
247 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
248 if (call_used_regs[i])
251 /* It is important that this be done after processing the insn's
252 pattern because we want the function result register to still
253 be live if it's also used to pass arguments. */
254 stupid_mark_refs (CALL_INSN_FUNCTION_USAGE (insn), insn);
258 /* Now decide the order in which to allocate the pseudo registers. */
260 for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++)
263 qsort (®_order[LAST_VIRTUAL_REGISTER + 1],
264 max_regno - LAST_VIRTUAL_REGISTER - 1, sizeof (int),
267 /* Now, in that order, try to find hard registers for those pseudo regs. */
269 for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++)
271 register int r = reg_order[i];
273 /* Some regnos disappear from the rtl. Ignore them to avoid crash.
274 Also don't allocate registers that cross a setjmp. */
275 if (regno_reg_rtx[r] == 0 || regs_crosses_setjmp[r])
278 /* Now find the best hard-register class for this pseudo register */
279 if (N_REG_CLASSES > 1)
280 reg_renumber[r] = stupid_find_reg (reg_n_calls_crossed[r],
281 reg_preferred_class (r),
282 PSEUDO_REGNO_MODE (r),
285 regs_change_size[r]);
287 /* If no reg available in that class, try alternate class. */
288 if (reg_renumber[r] == -1 && reg_alternate_class (r) != NO_REGS)
289 reg_renumber[r] = stupid_find_reg (reg_n_calls_crossed[r],
290 reg_alternate_class (r),
291 PSEUDO_REGNO_MODE (r),
294 regs_change_size[r]);
298 dump_flow_info (file);
301 /* Comparison function for qsort.
302 Returns -1 (1) if register *R1P is higher priority than *R2P. */
305 stupid_reg_compare (r1p, r2p)
306 const GENERIC_PTR r1p;
307 const GENERIC_PTR r2p;
309 register int r1 = *(int *)r1p, r2 = *(int *)r2p;
310 register int len1 = reg_where_dead[r1] - reg_where_born[r1];
311 register int len2 = reg_where_dead[r2] - reg_where_born[r2];
318 tem = reg_n_refs[r1] - reg_n_refs[r2];
322 /* If regs are equally good, sort by regno,
323 so that the results of qsort leave nothing to chance. */
327 /* Find a block of SIZE words of hard registers in reg_class CLASS
328 that can hold a value of machine-mode MODE
329 (but actually we test only the first of the block for holding MODE)
330 currently free from after insn whose suid is BORN_INSN
331 through the insn whose suid is DEAD_INSN,
332 and return the number of the first of them.
333 Return -1 if such a block cannot be found.
335 If CALL_PRESERVED is nonzero, insist on registers preserved
336 over subroutine calls, and return -1 if cannot find such.
338 If CHANGES_SIZE is nonzero, it means this register was used as the
339 operand of a SUBREG that changes its size. */
342 stupid_find_reg (call_preserved, class, mode,
343 born_insn, dead_insn, changes_size)
345 enum reg_class class;
346 enum machine_mode mode;
347 int born_insn, dead_insn;
352 register /* Declare them register if they are scalars. */
354 HARD_REG_SET used, this_reg;
355 #ifdef ELIMINABLE_REGS
356 static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
359 /* If this register's life is more than 5,000 insns, we probably
360 can't allocate it, so don't waste the time trying. This avoids
361 quadratic behavior on programs that have regularly-occurring
363 if (dead_insn > born_insn + 5000)
366 COPY_HARD_REG_SET (used,
367 call_preserved ? call_used_reg_set : fixed_reg_set);
369 #ifdef ELIMINABLE_REGS
370 for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
371 SET_HARD_REG_BIT (used, eliminables[i].from);
372 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
373 SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM);
376 SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM);
379 for (ins = born_insn; ins < dead_insn; ins++)
380 IOR_HARD_REG_SET (used, after_insn_hard_regs[ins]);
382 IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]);
384 #ifdef CLASS_CANNOT_CHANGE_SIZE
386 IOR_HARD_REG_SET (used,
387 reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]);
390 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
392 #ifdef REG_ALLOC_ORDER
393 int regno = reg_alloc_order[i];
398 /* If a register has screwy overlap problems,
399 don't use it at all if not optimizing.
400 Actually this is only for the 387 stack register,
401 and it's because subsequent code won't work. */
402 #ifdef OVERLAPPING_REGNO_P
403 if (OVERLAPPING_REGNO_P (regno))
407 if (! TEST_HARD_REG_BIT (used, regno)
408 && HARD_REGNO_MODE_OK (regno, mode))
411 register int size1 = HARD_REGNO_NREGS (regno, mode);
412 for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++);
415 CLEAR_HARD_REG_SET (this_reg);
417 SET_HARD_REG_BIT (this_reg, regno + j);
418 for (ins = born_insn; ins < dead_insn; ins++)
420 IOR_HARD_REG_SET (after_insn_hard_regs[ins], this_reg);
424 #ifndef REG_ALLOC_ORDER
425 i += j; /* Skip starting points we know will lose */
433 /* Walk X, noting all assignments and references to registers
434 and recording what they imply about life spans.
435 INSN is the current insn, supplied so we can find its suid. */
438 stupid_mark_refs (x, insn)
441 register RTX_CODE code;
443 register int regno, i;
450 if (code == SET || code == CLOBBER)
452 if (SET_DEST (x) != 0
453 && (GET_CODE (SET_DEST (x)) == REG
454 || (GET_CODE (SET_DEST (x)) == SUBREG
455 && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
456 && (REGNO (SUBREG_REG (SET_DEST (x)))
457 >= FIRST_PSEUDO_REGISTER))))
459 /* Register is being assigned. */
460 /* If setting a SUBREG, we treat the entire reg as being set. */
461 if (GET_CODE (SET_DEST (x)) == SUBREG)
462 regno = REGNO (SUBREG_REG (SET_DEST (x)));
464 regno = REGNO (SET_DEST (x));
466 /* For hard regs, update the where-live info. */
467 if (regno < FIRST_PSEUDO_REGISTER)
470 = HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (x)));
474 regs_ever_live[regno+j] = 1;
475 regs_live[regno+j] = 0;
477 /* The following line is for unused outputs;
478 they do get stored even though never used again. */
479 MARK_LIVE_AFTER (insn, regno+j);
481 /* When a hard reg is clobbered, mark it in use
482 just before this insn, so it is live all through. */
483 if (code == CLOBBER && INSN_SUID (insn) > 0)
484 SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (insn) - 1],
488 /* For pseudo regs, record where born, where dead, number of
489 times used, and whether live across a call. */
492 /* Update the life-interval bounds of this pseudo reg. */
494 /* When a pseudo-reg is CLOBBERed, it is born just before
495 the clobbering insn. When setting, just after. */
496 int where_born = INSN_SUID (insn) - (code == CLOBBER);
498 reg_where_born[regno] = where_born;
500 /* The reg must live at least one insn even
501 in it is never again used--because it has to go
502 in SOME hard reg. Mark it as dying after the current
503 insn so that it will conflict with any other outputs of
505 if (reg_where_dead[regno] < where_born + 2)
507 reg_where_dead[regno] = where_born + 2;
508 regs_live[regno] = 1;
511 /* Count the refs of this reg. */
514 if (last_call_suid < reg_where_dead[regno])
515 reg_n_calls_crossed[regno] += 1;
517 if (last_setjmp_suid < reg_where_dead[regno])
518 regs_crosses_setjmp[regno] = 1;
522 /* Record references from the value being set,
523 or from addresses in the place being set if that's not a reg.
524 If setting a SUBREG, we treat the entire reg as *used*. */
527 stupid_mark_refs (SET_SRC (x), insn);
528 if (GET_CODE (SET_DEST (x)) != REG)
529 stupid_mark_refs (SET_DEST (x), insn);
534 else if (code == SUBREG
535 && GET_CODE (SUBREG_REG (x)) == REG
536 && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER
537 && (GET_MODE_SIZE (GET_MODE (x))
538 != GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
539 && (INTEGRAL_MODE_P (GET_MODE (x))
540 || INTEGRAL_MODE_P (GET_MODE (SUBREG_REG (x)))))
541 regs_change_size[REGNO (SUBREG_REG (x))] = 1;
543 /* Register value being used, not set. */
545 else if (code == REG)
548 if (regno < FIRST_PSEUDO_REGISTER)
550 /* Hard reg: mark it live for continuing scan of previous insns. */
551 register int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
554 regs_ever_live[regno+j] = 1;
555 regs_live[regno+j] = 1;
560 /* Pseudo reg: record first use, last use and number of uses. */
562 reg_where_born[regno] = INSN_SUID (insn);
564 if (regs_live[regno] == 0)
566 regs_live[regno] = 1;
567 reg_where_dead[regno] = INSN_SUID (insn);
573 /* Recursive scan of all other rtx's. */
575 fmt = GET_RTX_FORMAT (code);
576 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
579 stupid_mark_refs (XEXP (x, i), insn);
583 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
584 stupid_mark_refs (XVECEXP (x, i, j), insn);