]>
Commit | Line | Data |
---|---|---|
cce8749e CH |
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 | \f | |
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 | \f | |
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 | \f | |
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 | #else | |
364 | SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM); | |
365 | #endif | |
366 | ||
367 | for (ins = born_insn; ins < dead_insn; ins++) | |
368 | IOR_HARD_REG_SET (used, after_insn_hard_regs[ins]); | |
369 | ||
370 | IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]); | |
371 | ||
372 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) | |
373 | { | |
374 | #ifdef REG_ALLOC_ORDER | |
375 | int regno = reg_alloc_order[i]; | |
376 | #else | |
377 | int regno = i; | |
378 | #endif | |
379 | ||
380 | /* If we need reasonable death info on this hard reg, | |
381 | don't use it for anything whose life spans a label or a jump. */ | |
382 | #ifdef PRESERVE_DEATH_INFO_REGNO_P | |
383 | if (PRESERVE_DEATH_INFO_REGNO_P (regno) | |
384 | && crosses_blocks) | |
385 | continue; | |
386 | #endif | |
387 | /* If a register has screwy overlap problems, | |
388 | don't use it at all if not optimizing. | |
389 | Actually this is only for the 387 stack register, | |
390 | and it's because subsequent code won't work. */ | |
391 | #ifdef OVERLAPPING_REGNO_P | |
392 | if (OVERLAPPING_REGNO_P (regno)) | |
393 | continue; | |
394 | #endif | |
395 | ||
396 | if (! TEST_HARD_REG_BIT (used, regno) | |
397 | && HARD_REGNO_MODE_OK (regno, mode)) | |
398 | { | |
399 | register int j; | |
400 | register int size1 = HARD_REGNO_NREGS (regno, mode); | |
401 | for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++); | |
402 | if (j == size1) | |
403 | { | |
404 | CLEAR_HARD_REG_SET (this_reg); | |
405 | while (--j >= 0) | |
406 | SET_HARD_REG_BIT (this_reg, regno + j); | |
407 | for (ins = born_insn; ins < dead_insn; ins++) | |
408 | { | |
409 | IOR_HARD_REG_SET (after_insn_hard_regs[ins], this_reg); | |
410 | } | |
411 | return regno; | |
412 | } | |
413 | #ifndef REG_ALLOC_ORDER | |
414 | i += j; /* Skip starting points we know will lose */ | |
415 | #endif | |
416 | } | |
417 | } | |
418 | return -1; | |
419 | } | |
420 | \f | |
421 | /* Walk X, noting all assignments and references to registers | |
422 | and recording what they imply about life spans. | |
423 | INSN is the current insn, supplied so we can find its suid. */ | |
424 | ||
425 | static void | |
426 | stupid_mark_refs (x, insn) | |
427 | rtx x, insn; | |
428 | { | |
429 | register RTX_CODE code = GET_CODE (x); | |
430 | register char *fmt; | |
431 | register int regno, i; | |
432 | ||
433 | if (code == SET || code == CLOBBER) | |
434 | { | |
435 | if (SET_DEST (x) != 0 && GET_CODE (SET_DEST (x)) == REG) | |
436 | { | |
437 | /* Register is being assigned. */ | |
438 | regno = REGNO (SET_DEST (x)); | |
439 | ||
440 | /* For hard regs, update the where-live info. */ | |
441 | if (regno < FIRST_PSEUDO_REGISTER) | |
442 | { | |
443 | register int j | |
444 | = HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (x))); | |
445 | while (--j >= 0) | |
446 | { | |
447 | regs_ever_live[regno+j] = 1; | |
448 | regs_live[regno+j] = 0; | |
449 | /* The following line is for unused outputs; | |
450 | they do get stored even though never used again. */ | |
451 | MARK_LIVE_AFTER (insn, regno); | |
452 | /* When a hard reg is clobbered, mark it in use | |
453 | just before this insn, so it is live all through. */ | |
454 | if (code == CLOBBER && INSN_SUID (insn) > 0) | |
455 | SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (insn) - 1], | |
456 | regno); | |
457 | } | |
458 | } | |
459 | /* For pseudo regs, record where born, where dead, number of | |
460 | times used, and whether live across a call. */ | |
461 | else | |
462 | { | |
463 | /* Update the life-interval bounds of this pseudo reg. */ | |
464 | ||
465 | /* When a pseudo-reg is CLOBBERed, it is born just before | |
466 | the clobbering insn. When setting, just after. */ | |
467 | int where_born = INSN_SUID (insn) - (code == CLOBBER); | |
468 | ||
469 | reg_where_born[regno] = where_born; | |
470 | /* The reg must live at least one insn even | |
471 | in it is never again used--because it has to go | |
472 | in SOME hard reg. Mark it as dying after the current | |
473 | insn so that it will conflict with any other outputs of | |
474 | this insn. */ | |
475 | if (reg_where_dead[regno] < where_born + 2) | |
476 | reg_where_dead[regno] = where_born + 2; | |
477 | ||
478 | /* Count the refs of this reg. */ | |
479 | reg_n_refs[regno]++; | |
480 | ||
481 | if (last_call_suid < reg_where_dead[regno]) | |
482 | reg_n_calls_crossed[regno] += 1; | |
483 | if (last_jump_suid < reg_where_dead[regno] | |
484 | || last_label_suid < reg_where_dead[regno]) | |
485 | reg_crosses_blocks[regno] = 1; | |
486 | } | |
487 | } | |
488 | /* Record references from the value being set, | |
489 | or from addresses in the place being set if that's not a reg. | |
490 | If setting a SUBREG, we treat the entire reg as *used*. */ | |
491 | if (code == SET) | |
492 | { | |
493 | stupid_mark_refs (SET_SRC (x), insn); | |
494 | if (GET_CODE (SET_DEST (x)) != REG) | |
495 | stupid_mark_refs (SET_DEST (x), insn); | |
496 | } | |
497 | return; | |
498 | } | |
499 | ||
500 | /* Register value being used, not set. */ | |
501 | ||
502 | if (code == REG) | |
503 | { | |
504 | regno = REGNO (x); | |
505 | if (regno < FIRST_PSEUDO_REGISTER) | |
506 | { | |
507 | /* Hard reg: mark it live for continuing scan of previous insns. */ | |
508 | register int j = HARD_REGNO_NREGS (regno, GET_MODE (x)); | |
509 | while (--j >= 0) | |
510 | { | |
511 | regs_ever_live[regno+j] = 1; | |
512 | regs_live[regno+j] = 1; | |
513 | } | |
514 | } | |
515 | else | |
516 | { | |
517 | /* Pseudo reg: record first use, last use and number of uses. */ | |
518 | ||
519 | reg_where_born[regno] = INSN_SUID (insn); | |
520 | reg_n_refs[regno]++; | |
521 | if (regs_live[regno] == 0) | |
522 | { | |
523 | regs_live[regno] = 1; | |
524 | reg_where_dead[regno] = INSN_SUID (insn); | |
525 | } | |
526 | } | |
527 | return; | |
528 | } | |
529 | ||
530 | /* Recursive scan of all other rtx's. */ | |
531 | ||
532 | fmt = GET_RTX_FORMAT (code); | |
533 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
534 | { | |
535 | if (fmt[i] == 'e') | |
536 | stupid_mark_refs (XEXP (x, i), insn); | |
537 | if (fmt[i] == 'E') | |
538 | { | |
539 | register int j; | |
540 | for (j = XVECLEN (x, i) - 1; j >= 0; j--) | |
541 | stupid_mark_refs (XVECEXP (x, i, j), insn); | |
542 | } | |
543 | } | |
544 | } |