1 /* Dummy data flow analysis for GNU compiler in nonoptimizing mode.
2 Copyright (C) 1987, 91, 94, 95, 96, 1997 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. */
49 #include "hard-reg-set.h"
53 /* Vector mapping INSN_UIDs to suids.
54 The suids are like uids but increase monotonically always.
55 We use them to see whether a subroutine call came
56 between a variable's birth and its death. */
60 /* Get the suid of an insn. */
62 #define INSN_SUID(INSN) (uid_suid[INSN_UID (INSN)])
64 /* Record the suid of the last CALL_INSN
65 so we can tell whether a pseudo reg crosses any calls. */
67 static int last_call_suid
;
69 /* Record the suid of the last NOTE_INSN_SETJMP
70 so we can tell whether a pseudo reg crosses any setjmp. */
72 static int last_setjmp_suid
;
74 /* Element N is suid of insn where life span of pseudo reg N ends.
75 Element is 0 if register N has not been seen yet on backward scan. */
77 static int *reg_where_dead
;
79 /* Element N is suid of insn where life span of pseudo reg N begins. */
81 static int *reg_where_born
;
83 /* Numbers of pseudo-regs to be allocated, highest priority first. */
85 static int *reg_order
;
87 /* Indexed by reg number (hard or pseudo), nonzero if register is live
88 at the current point in the instruction stream. */
90 static char *regs_live
;
92 /* Indexed by reg number, nonzero if reg was used in a SUBREG that changes
95 static char *regs_change_size
;
97 /* Indexed by reg number, nonzero if reg crosses a setjmp. */
99 static char *regs_crosses_setjmp
;
101 /* Indexed by insn's suid, the set of hard regs live after that insn. */
103 static HARD_REG_SET
*after_insn_hard_regs
;
105 /* Record that hard reg REGNO is live after insn INSN. */
107 #define MARK_LIVE_AFTER(INSN,REGNO) \
108 SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (INSN)], (REGNO))
110 static int stupid_reg_compare
PROTO((const GENERIC_PTR
,const GENERIC_PTR
));
111 static int stupid_find_reg
PROTO((int, enum reg_class
, enum machine_mode
,
113 static void stupid_mark_refs
PROTO((rtx
, rtx
));
115 /* Stupid life analysis is for the case where only variables declared
116 `register' go in registers. For this case, we mark all
117 pseudo-registers that belong to register variables as
118 dying in the last instruction of the function, and all other
119 pseudo registers as dying in the last place they are referenced.
120 Hard registers are marked as dying in the last reference before
121 the end or before each store into them. */
124 stupid_life_analysis (f
, nregs
, file
)
130 register rtx last
, insn
;
131 int max_uid
, max_suid
;
133 bzero (regs_ever_live
, sizeof regs_ever_live
);
135 regs_live
= (char *) alloca (nregs
);
137 /* First find the last real insn, and count the number of insns,
138 and assign insns their suids. */
140 for (insn
= f
, i
= 0; insn
; insn
= NEXT_INSN (insn
))
141 if (INSN_UID (insn
) > i
)
145 uid_suid
= (int *) alloca ((i
+ 1) * sizeof (int));
147 /* Compute the mapping from uids to suids.
148 Suids are numbers assigned to insns, like uids,
149 except that suids increase monotonically through the code. */
151 last
= 0; /* In case of empty function body */
152 for (insn
= f
, i
= 0; insn
; insn
= NEXT_INSN (insn
))
154 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
157 INSN_SUID (insn
) = ++i
;
160 last_call_suid
= i
+ 1;
161 last_setjmp_suid
= i
+ 1;
166 /* Allocate tables to record info about regs. */
168 reg_where_dead
= (int *) alloca (nregs
* sizeof (int));
169 bzero ((char *) reg_where_dead
, nregs
* sizeof (int));
171 reg_where_born
= (int *) alloca (nregs
* sizeof (int));
172 bzero ((char *) reg_where_born
, nregs
* sizeof (int));
174 reg_order
= (int *) alloca (nregs
* sizeof (int));
175 bzero ((char *) reg_order
, nregs
* sizeof (int));
177 regs_change_size
= (char *) alloca (nregs
* sizeof (char));
178 bzero ((char *) regs_change_size
, nregs
* sizeof (char));
180 regs_crosses_setjmp
= (char *) alloca (nregs
* sizeof (char));
181 bzero ((char *) regs_crosses_setjmp
, nregs
* sizeof (char));
183 /* Allocate the reg_renumber array */
184 allocate_reg_info (max_regno
, FALSE
, TRUE
);
185 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
189 = (HARD_REG_SET
*) alloca (max_suid
* sizeof (HARD_REG_SET
));
191 bzero ((char *) after_insn_hard_regs
, max_suid
* sizeof (HARD_REG_SET
));
193 /* Allocate and zero out many data structures
194 that will record the data from lifetime analysis. */
196 allocate_for_life_analysis ();
198 for (i
= 0; i
< max_regno
; i
++)
199 REG_N_DEATHS (i
) = 1;
201 bzero (regs_live
, nregs
);
203 /* Find where each pseudo register is born and dies,
204 by scanning all insns from the end to the start
205 and noting all mentions of the registers.
207 Also find where each hard register is live
208 and record that info in after_insn_hard_regs.
209 regs_live[I] is 1 if hard reg I is live
210 at the current point in the scan. */
212 for (insn
= last
; insn
; insn
= PREV_INSN (insn
))
214 register HARD_REG_SET
*p
= after_insn_hard_regs
+ INSN_SUID (insn
);
216 /* Copy the info in regs_live into the element of after_insn_hard_regs
217 for the current position in the rtl code. */
219 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
221 SET_HARD_REG_BIT (*p
, i
);
223 /* Update which hard regs are currently live
224 and also the birth and death suids of pseudo regs
225 based on the pattern of this insn. */
227 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
228 stupid_mark_refs (PATTERN (insn
), insn
);
230 if (GET_CODE (insn
) == NOTE
231 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
)
232 last_setjmp_suid
= INSN_SUID (insn
);
234 /* Mark all call-clobbered regs as dead after each call insn so that
235 a pseudo whose life span includes this insn will not go in one of
236 them. If the function contains a non-local goto, mark all hard
237 registers dead (except for stack related bits).
239 Then mark those regs as all dead for the continuing scan
240 of the insns before the call. */
242 if (GET_CODE (insn
) == CALL_INSN
)
244 last_call_suid
= INSN_SUID (insn
);
246 if (current_function_has_nonlocal_label
)
248 IOR_COMPL_HARD_REG_SET (after_insn_hard_regs
[last_call_suid
],
250 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
256 IOR_HARD_REG_SET (after_insn_hard_regs
[last_call_suid
],
258 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
259 if (call_used_regs
[i
])
263 /* It is important that this be done after processing the insn's
264 pattern because we want the function result register to still
265 be live if it's also used to pass arguments. */
266 stupid_mark_refs (CALL_INSN_FUNCTION_USAGE (insn
), insn
);
270 /* Now decide the order in which to allocate the pseudo registers. */
272 for (i
= LAST_VIRTUAL_REGISTER
+ 1; i
< max_regno
; i
++)
275 qsort (®_order
[LAST_VIRTUAL_REGISTER
+ 1],
276 max_regno
- LAST_VIRTUAL_REGISTER
- 1, sizeof (int),
279 /* Now, in that order, try to find hard registers for those pseudo regs. */
281 for (i
= LAST_VIRTUAL_REGISTER
+ 1; i
< max_regno
; i
++)
283 register int r
= reg_order
[i
];
285 /* Some regnos disappear from the rtl. Ignore them to avoid crash.
286 Also don't allocate registers that cross a setjmp, or live across
287 a call if this function receives a nonlocal goto. */
288 if (regno_reg_rtx
[r
] == 0 || regs_crosses_setjmp
[r
]
289 || (REG_N_CALLS_CROSSED (r
) > 0
290 && current_function_has_nonlocal_label
))
293 /* Now find the best hard-register class for this pseudo register */
294 if (N_REG_CLASSES
> 1)
295 reg_renumber
[r
] = stupid_find_reg (REG_N_CALLS_CROSSED (r
),
296 reg_preferred_class (r
),
297 PSEUDO_REGNO_MODE (r
),
300 regs_change_size
[r
]);
302 /* If no reg available in that class, try alternate class. */
303 if (reg_renumber
[r
] == -1 && reg_alternate_class (r
) != NO_REGS
)
304 reg_renumber
[r
] = stupid_find_reg (REG_N_CALLS_CROSSED (r
),
305 reg_alternate_class (r
),
306 PSEUDO_REGNO_MODE (r
),
309 regs_change_size
[r
]);
313 dump_flow_info (file
);
316 /* Comparison function for qsort.
317 Returns -1 (1) if register *R1P is higher priority than *R2P. */
320 stupid_reg_compare (r1p
, r2p
)
321 const GENERIC_PTR r1p
;
322 const GENERIC_PTR r2p
;
324 register int r1
= *(int *)r1p
, r2
= *(int *)r2p
;
325 register int len1
= reg_where_dead
[r1
] - reg_where_born
[r1
];
326 register int len2
= reg_where_dead
[r2
] - reg_where_born
[r2
];
333 tem
= REG_N_REFS (r1
) - REG_N_REFS (r2
);
337 /* If regs are equally good, sort by regno,
338 so that the results of qsort leave nothing to chance. */
342 /* Find a block of SIZE words of hard registers in reg_class CLASS
343 that can hold a value of machine-mode MODE
344 (but actually we test only the first of the block for holding MODE)
345 currently free from after insn whose suid is BORN_INSN
346 through the insn whose suid is DEAD_INSN,
347 and return the number of the first of them.
348 Return -1 if such a block cannot be found.
350 If CALL_PRESERVED is nonzero, insist on registers preserved
351 over subroutine calls, and return -1 if cannot find such.
353 If CHANGES_SIZE is nonzero, it means this register was used as the
354 operand of a SUBREG that changes its size. */
357 stupid_find_reg (call_preserved
, class, mode
,
358 born_insn
, dead_insn
, changes_size
)
360 enum reg_class
class;
361 enum machine_mode mode
;
362 int born_insn
, dead_insn
;
367 register /* Declare them register if they are scalars. */
369 HARD_REG_SET used
, this_reg
;
370 #ifdef ELIMINABLE_REGS
371 static struct {int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
374 /* If this register's life is more than 5,000 insns, we probably
375 can't allocate it, so don't waste the time trying. This avoids
376 quadratic behavior on programs that have regularly-occurring
378 if (dead_insn
> born_insn
+ 5000)
381 COPY_HARD_REG_SET (used
,
382 call_preserved
? call_used_reg_set
: fixed_reg_set
);
384 #ifdef ELIMINABLE_REGS
385 for (i
= 0; i
< sizeof eliminables
/ sizeof eliminables
[0]; i
++)
386 SET_HARD_REG_BIT (used
, eliminables
[i
].from
);
387 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
388 SET_HARD_REG_BIT (used
, HARD_FRAME_POINTER_REGNUM
);
391 SET_HARD_REG_BIT (used
, FRAME_POINTER_REGNUM
);
394 for (ins
= born_insn
; ins
< dead_insn
; ins
++)
395 IOR_HARD_REG_SET (used
, after_insn_hard_regs
[ins
]);
397 IOR_COMPL_HARD_REG_SET (used
, reg_class_contents
[(int) class]);
399 #ifdef CLASS_CANNOT_CHANGE_SIZE
401 IOR_HARD_REG_SET (used
,
402 reg_class_contents
[(int) CLASS_CANNOT_CHANGE_SIZE
]);
405 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
407 #ifdef REG_ALLOC_ORDER
408 int regno
= reg_alloc_order
[i
];
413 /* If a register has screwy overlap problems,
414 don't use it at all if not optimizing.
415 Actually this is only for the 387 stack register,
416 and it's because subsequent code won't work. */
417 #ifdef OVERLAPPING_REGNO_P
418 if (OVERLAPPING_REGNO_P (regno
))
422 if (! TEST_HARD_REG_BIT (used
, regno
)
423 && HARD_REGNO_MODE_OK (regno
, mode
))
426 register int size1
= HARD_REGNO_NREGS (regno
, mode
);
427 for (j
= 1; j
< size1
&& ! TEST_HARD_REG_BIT (used
, regno
+ j
); j
++);
430 CLEAR_HARD_REG_SET (this_reg
);
432 SET_HARD_REG_BIT (this_reg
, regno
+ j
);
433 for (ins
= born_insn
; ins
< dead_insn
; ins
++)
435 IOR_HARD_REG_SET (after_insn_hard_regs
[ins
], this_reg
);
439 #ifndef REG_ALLOC_ORDER
440 i
+= j
; /* Skip starting points we know will lose */
448 /* Walk X, noting all assignments and references to registers
449 and recording what they imply about life spans.
450 INSN is the current insn, supplied so we can find its suid. */
453 stupid_mark_refs (x
, insn
)
456 register RTX_CODE code
;
458 register int regno
, i
;
465 if (code
== SET
|| code
== CLOBBER
)
467 if (SET_DEST (x
) != 0
468 && (GET_CODE (SET_DEST (x
)) == REG
469 || (GET_CODE (SET_DEST (x
)) == SUBREG
470 && GET_CODE (SUBREG_REG (SET_DEST (x
))) == REG
471 && (REGNO (SUBREG_REG (SET_DEST (x
)))
472 >= FIRST_PSEUDO_REGISTER
))))
474 /* Register is being assigned. */
475 /* If setting a SUBREG, we treat the entire reg as being set. */
476 if (GET_CODE (SET_DEST (x
)) == SUBREG
)
477 regno
= REGNO (SUBREG_REG (SET_DEST (x
)));
479 regno
= REGNO (SET_DEST (x
));
481 /* For hard regs, update the where-live info. */
482 if (regno
< FIRST_PSEUDO_REGISTER
)
485 = HARD_REGNO_NREGS (regno
, GET_MODE (SET_DEST (x
)));
489 regs_ever_live
[regno
+j
] = 1;
490 regs_live
[regno
+j
] = 0;
492 /* The following line is for unused outputs;
493 they do get stored even though never used again. */
494 MARK_LIVE_AFTER (insn
, regno
+j
);
496 /* When a hard reg is clobbered, mark it in use
497 just before this insn, so it is live all through. */
498 if (code
== CLOBBER
&& INSN_SUID (insn
) > 0)
499 SET_HARD_REG_BIT (after_insn_hard_regs
[INSN_SUID (insn
) - 1],
503 /* For pseudo regs, record where born, where dead, number of
504 times used, and whether live across a call. */
507 /* Update the life-interval bounds of this pseudo reg. */
509 /* When a pseudo-reg is CLOBBERed, it is born just before
510 the clobbering insn. When setting, just after. */
511 int where_born
= INSN_SUID (insn
) - (code
== CLOBBER
);
513 reg_where_born
[regno
] = where_born
;
515 /* The reg must live at least one insn even
516 in it is never again used--because it has to go
517 in SOME hard reg. Mark it as dying after the current
518 insn so that it will conflict with any other outputs of
520 if (reg_where_dead
[regno
] < where_born
+ 2)
522 reg_where_dead
[regno
] = where_born
+ 2;
523 regs_live
[regno
] = 1;
526 /* Count the refs of this reg. */
527 REG_N_REFS (regno
)++;
529 if (last_call_suid
< reg_where_dead
[regno
])
530 REG_N_CALLS_CROSSED (regno
) += 1;
532 if (last_setjmp_suid
< reg_where_dead
[regno
])
533 regs_crosses_setjmp
[regno
] = 1;
535 /* If this register is only used in this insn and is only
536 set, mark it unused. We have to do this even when not
537 optimizing so that MD patterns which count on this
538 behavior (e.g., it not causing an output reload on
539 an insn setting CC) will operate correctly. */
540 if (GET_CODE (SET_DEST (x
)) == REG
541 && REGNO_FIRST_UID (regno
) == INSN_UID (insn
)
542 && REGNO_LAST_UID (regno
) == INSN_UID (insn
)
543 && (code
== CLOBBER
|| ! reg_mentioned_p (SET_DEST (x
),
545 REG_NOTES (insn
) = gen_rtx_EXPR_LIST (REG_UNUSED
,
551 /* Record references from the value being set,
552 or from addresses in the place being set if that's not a reg.
553 If setting a SUBREG, we treat the entire reg as *used*. */
556 stupid_mark_refs (SET_SRC (x
), insn
);
557 if (GET_CODE (SET_DEST (x
)) != REG
)
558 stupid_mark_refs (SET_DEST (x
), insn
);
563 else if (code
== SUBREG
564 && GET_CODE (SUBREG_REG (x
)) == REG
565 && REGNO (SUBREG_REG (x
)) >= FIRST_PSEUDO_REGISTER
566 && (GET_MODE_SIZE (GET_MODE (x
))
567 != GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
))))
568 && (INTEGRAL_MODE_P (GET_MODE (x
))
569 || INTEGRAL_MODE_P (GET_MODE (SUBREG_REG (x
)))))
570 regs_change_size
[REGNO (SUBREG_REG (x
))] = 1;
572 /* Register value being used, not set. */
574 else if (code
== REG
)
577 if (regno
< FIRST_PSEUDO_REGISTER
)
579 /* Hard reg: mark it live for continuing scan of previous insns. */
580 register int j
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
583 regs_ever_live
[regno
+j
] = 1;
584 regs_live
[regno
+j
] = 1;
589 /* Pseudo reg: record first use, last use and number of uses. */
591 reg_where_born
[regno
] = INSN_SUID (insn
);
592 REG_N_REFS (regno
)++;
593 if (regs_live
[regno
] == 0)
595 regs_live
[regno
] = 1;
596 reg_where_dead
[regno
] = INSN_SUID (insn
);
602 /* Recursive scan of all other rtx's. */
604 fmt
= GET_RTX_FORMAT (code
);
605 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
608 stupid_mark_refs (XEXP (x
, i
), insn
);
612 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
613 stupid_mark_refs (XVECEXP (x
, i
, j
), insn
);