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