]>
Commit | Line | Data |
---|---|---|
cce8749e | 1 | /* Dummy data flow analysis for GNU compiler in nonoptimizing mode. |
a544cfd2 | 2 | Copyright (C) 1987, 91, 94-96, 98, 99, 2000 Free Software Foundation, Inc. |
cce8749e CH |
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 | |
e9fa0c7c RK |
18 | the Free Software Foundation, 59 Temple Place - Suite 330, |
19 | Boston, MA 02111-1307, USA. */ | |
cce8749e CH |
20 | |
21 | ||
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). | |
24 | ||
38e01259 | 25 | Stupid register allocation goes in place of the flow_analysis, |
cce8749e CH |
26 | local_alloc and global_alloc passes. combine_instructions cannot |
27 | be done with stupid allocation because the data flow info that it needs | |
28 | is not computed here. | |
29 | ||
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. | |
36 | ||
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. */ | |
44 | ||
cce8749e | 45 | #include "config.h" |
670ee920 | 46 | #include "system.h" |
ccd043a9 | 47 | |
cce8749e CH |
48 | #include "rtl.h" |
49 | #include "hard-reg-set.h" | |
cad6f7d0 | 50 | #include "basic-block.h" |
cce8749e | 51 | #include "regs.h" |
49ad7cfa | 52 | #include "function.h" |
cad6f7d0 BS |
53 | #include "insn-config.h" |
54 | #include "reload.h" | |
cce8749e | 55 | #include "flags.h" |
2e107e9e | 56 | #include "toplev.h" |
7bdb32b9 | 57 | #include "tm_p.h" |
cce8749e CH |
58 | \f |
59 | /* Vector mapping INSN_UIDs to suids. | |
60 | The suids are like uids but increase monotonically always. | |
61 | We use them to see whether a subroutine call came | |
62 | between a variable's birth and its death. */ | |
63 | ||
64 | static int *uid_suid; | |
65 | ||
66 | /* Get the suid of an insn. */ | |
67 | ||
68 | #define INSN_SUID(INSN) (uid_suid[INSN_UID (INSN)]) | |
69 | ||
70 | /* Record the suid of the last CALL_INSN | |
71 | so we can tell whether a pseudo reg crosses any calls. */ | |
72 | ||
73 | static int last_call_suid; | |
74 | ||
68f02135 RK |
75 | /* Record the suid of the last NOTE_INSN_SETJMP |
76 | so we can tell whether a pseudo reg crosses any setjmp. */ | |
77 | ||
78 | static int last_setjmp_suid; | |
79 | ||
cce8749e CH |
80 | /* Element N is suid of insn where life span of pseudo reg N ends. |
81 | Element is 0 if register N has not been seen yet on backward scan. */ | |
82 | ||
83 | static int *reg_where_dead; | |
84 | ||
cad6f7d0 BS |
85 | /* Likewise, but point to the insn_chain structure of the insn at which |
86 | the reg dies. */ | |
87 | static struct insn_chain **reg_where_dead_chain; | |
88 | ||
cce8749e | 89 | /* Element N is suid of insn where life span of pseudo reg N begins. */ |
cad6f7d0 BS |
90 | static int *reg_where_born_exact; |
91 | ||
92 | /* Element N is 1 if the birth of pseudo reg N is due to a CLOBBER, | |
93 | 0 otherwise. */ | |
94 | static int *reg_where_born_clobber; | |
cce8749e | 95 | |
cad6f7d0 BS |
96 | /* Return the suid of the insn where the register is born, or the suid |
97 | of the insn before if the birth is due to a CLOBBER. */ | |
98 | #define REG_WHERE_BORN(N) \ | |
99 | (reg_where_born_exact[(N)] - reg_where_born_clobber[(N)]) | |
cce8749e | 100 | |
cce8749e CH |
101 | /* Numbers of pseudo-regs to be allocated, highest priority first. */ |
102 | ||
103 | static int *reg_order; | |
104 | ||
105 | /* Indexed by reg number (hard or pseudo), nonzero if register is live | |
106 | at the current point in the instruction stream. */ | |
107 | ||
108 | static char *regs_live; | |
109 | ||
cc33944a RK |
110 | /* Indexed by reg number, nonzero if reg was used in a SUBREG that changes |
111 | its size. */ | |
112 | ||
113 | static char *regs_change_size; | |
114 | ||
68f02135 RK |
115 | /* Indexed by reg number, nonzero if reg crosses a setjmp. */ |
116 | ||
117 | static char *regs_crosses_setjmp; | |
118 | ||
cce8749e CH |
119 | /* Indexed by insn's suid, the set of hard regs live after that insn. */ |
120 | ||
121 | static HARD_REG_SET *after_insn_hard_regs; | |
122 | ||
123 | /* Record that hard reg REGNO is live after insn INSN. */ | |
124 | ||
125 | #define MARK_LIVE_AFTER(INSN,REGNO) \ | |
126 | SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (INSN)], (REGNO)) | |
127 | ||
e1b6684c | 128 | static int stupid_reg_compare PROTO((const PTR,const PTR)); |
70ceb906 | 129 | static int stupid_find_reg PROTO((int, enum reg_class, enum machine_mode, |
cc33944a | 130 | int, int, int)); |
cad6f7d0 | 131 | static void stupid_mark_refs PROTO((rtx, struct insn_chain *)); |
84832317 | 132 | static void find_clobbered_regs PROTO((rtx, rtx, void *)); |
285f3cf0 | 133 | static void mark_hard_ref PROTO((rtx, int, struct insn_chain *)); |
cad6f7d0 BS |
134 | \f |
135 | /* For communication between stupid_life_analysis and find_clobbered_regs. */ | |
136 | static struct insn_chain *current_chain; | |
137 | ||
138 | /* This function, called via note_stores, marks any hard registers that are | |
285f3cf0 | 139 | clobbered in an insn as being live in the live_throughout field |
cad6f7d0 BS |
140 | of the appropriate insn_chain structure. */ |
141 | ||
142 | static void | |
84832317 | 143 | find_clobbered_regs (reg, setter, data) |
cad6f7d0 | 144 | rtx reg, setter; |
84832317 | 145 | void *data ATTRIBUTE_UNUSED; |
cad6f7d0 BS |
146 | { |
147 | int regno, nregs; | |
148 | if (setter == 0 || GET_CODE (setter) != CLOBBER) | |
149 | return; | |
150 | ||
151 | if (GET_CODE (reg) == SUBREG) | |
152 | reg = SUBREG_REG (reg); | |
153 | ||
154 | if (GET_CODE (reg) != REG) | |
155 | return; | |
156 | regno = REGNO (reg); | |
157 | if (regno >= FIRST_PSEUDO_REGISTER) | |
158 | return; | |
159 | ||
160 | if (GET_MODE (reg) == VOIDmode) | |
161 | abort (); | |
162 | else | |
163 | nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg)); | |
164 | while (nregs-- > 0) | |
165 | { | |
239a0f5b | 166 | SET_REGNO_REG_SET (¤t_chain->live_throughout, regno++); |
cad6f7d0 BS |
167 | } |
168 | } | |
cce8749e CH |
169 | \f |
170 | /* Stupid life analysis is for the case where only variables declared | |
171 | `register' go in registers. For this case, we mark all | |
172 | pseudo-registers that belong to register variables as | |
173 | dying in the last instruction of the function, and all other | |
174 | pseudo registers as dying in the last place they are referenced. | |
175 | Hard registers are marked as dying in the last reference before | |
176 | the end or before each store into them. */ | |
177 | ||
178 | void | |
179 | stupid_life_analysis (f, nregs, file) | |
180 | rtx f; | |
181 | int nregs; | |
182 | FILE *file; | |
183 | { | |
184 | register int i; | |
185 | register rtx last, insn; | |
70ceb906 | 186 | int max_uid, max_suid; |
cce8749e | 187 | |
4d1d8045 BS |
188 | current_function_has_computed_jump = 0; |
189 | ||
cce8749e CH |
190 | bzero (regs_ever_live, sizeof regs_ever_live); |
191 | ||
56a65848 | 192 | regs_live = (char *) xmalloc (nregs); |
cce8749e CH |
193 | |
194 | /* First find the last real insn, and count the number of insns, | |
195 | and assign insns their suids. */ | |
196 | ||
197 | for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) | |
198 | if (INSN_UID (insn) > i) | |
199 | i = INSN_UID (insn); | |
200 | ||
201 | max_uid = i + 1; | |
56a65848 | 202 | uid_suid = (int *) xmalloc ((i + 1) * sizeof (int)); |
cce8749e CH |
203 | |
204 | /* Compute the mapping from uids to suids. | |
205 | Suids are numbers assigned to insns, like uids, | |
206 | except that suids increase monotonically through the code. */ | |
207 | ||
208 | last = 0; /* In case of empty function body */ | |
209 | for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) | |
210 | { | |
70ceb906 | 211 | if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') |
cce8749e | 212 | last = insn; |
70ceb906 | 213 | |
cce8749e CH |
214 | INSN_SUID (insn) = ++i; |
215 | } | |
216 | ||
217 | last_call_suid = i + 1; | |
68f02135 | 218 | last_setjmp_suid = i + 1; |
70ceb906 | 219 | max_suid = i + 1; |
cce8749e CH |
220 | |
221 | max_regno = nregs; | |
222 | ||
223 | /* Allocate tables to record info about regs. */ | |
224 | ||
ad85216e KG |
225 | reg_where_dead = (int *) xcalloc (nregs, sizeof (int)); |
226 | reg_where_born_exact = (int *) xcalloc (nregs, sizeof (int)); | |
227 | reg_where_born_clobber = (int *) xcalloc (nregs, sizeof (int)); | |
228 | reg_where_dead_chain = (struct insn_chain **) | |
229 | xcalloc (nregs, sizeof (struct insn_chain *)); | |
230 | reg_order = (int *) xcalloc (nregs, sizeof (int)); | |
231 | regs_change_size = (char *) xcalloc (nregs, sizeof (char)); | |
232 | regs_crosses_setjmp = (char *) xcalloc (nregs, sizeof (char)); | |
68f02135 | 233 | |
39379e67 MM |
234 | /* Allocate the reg_renumber array */ |
235 | allocate_reg_info (max_regno, FALSE, TRUE); | |
cce8749e CH |
236 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) |
237 | reg_renumber[i] = i; | |
238 | ||
ad85216e KG |
239 | after_insn_hard_regs = |
240 | (HARD_REG_SET *) xcalloc (max_suid, sizeof (HARD_REG_SET)); | |
cce8749e CH |
241 | |
242 | /* Allocate and zero out many data structures | |
243 | that will record the data from lifetime analysis. */ | |
244 | ||
359da67d RH |
245 | allocate_reg_life_data (); |
246 | allocate_bb_life_data (); | |
cce8749e CH |
247 | |
248 | for (i = 0; i < max_regno; i++) | |
b1f21e0a | 249 | REG_N_DEATHS (i) = 1; |
cce8749e CH |
250 | |
251 | bzero (regs_live, nregs); | |
252 | ||
253 | /* Find where each pseudo register is born and dies, | |
254 | by scanning all insns from the end to the start | |
255 | and noting all mentions of the registers. | |
256 | ||
257 | Also find where each hard register is live | |
258 | and record that info in after_insn_hard_regs. | |
259 | regs_live[I] is 1 if hard reg I is live | |
cad6f7d0 BS |
260 | at the current point in the scan. |
261 | ||
262 | Build reload_insn_chain while we're walking the insns. */ | |
cce8749e | 263 | |
cad6f7d0 | 264 | reload_insn_chain = 0; |
cce8749e CH |
265 | for (insn = last; insn; insn = PREV_INSN (insn)) |
266 | { | |
267 | register HARD_REG_SET *p = after_insn_hard_regs + INSN_SUID (insn); | |
a544cfd2 | 268 | struct insn_chain *chain = 0; |
cce8749e | 269 | |
70ceb906 | 270 | /* Copy the info in regs_live into the element of after_insn_hard_regs |
cce8749e CH |
271 | for the current position in the rtl code. */ |
272 | ||
273 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) | |
274 | if (regs_live[i]) | |
275 | SET_HARD_REG_BIT (*p, i); | |
276 | ||
cad6f7d0 BS |
277 | if (GET_CODE (insn) != NOTE && GET_CODE (insn) != BARRIER) |
278 | { | |
279 | chain = new_insn_chain (); | |
280 | if (reload_insn_chain) | |
281 | reload_insn_chain->prev = chain; | |
282 | chain->next = reload_insn_chain; | |
283 | chain->prev = 0; | |
284 | reload_insn_chain = chain; | |
285 | chain->block = 0; | |
286 | chain->insn = insn; | |
287 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) | |
288 | if (regs_live[i]) | |
239a0f5b | 289 | SET_REGNO_REG_SET (&chain->live_throughout, i); |
cad6f7d0 BS |
290 | } |
291 | ||
56b5e76b DE |
292 | /* Update which hard regs are currently live |
293 | and also the birth and death suids of pseudo regs | |
294 | based on the pattern of this insn. */ | |
295 | ||
296 | if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') | |
cad6f7d0 | 297 | stupid_mark_refs (PATTERN (insn), chain); |
56b5e76b | 298 | |
68f02135 RK |
299 | if (GET_CODE (insn) == NOTE |
300 | && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP) | |
301 | last_setjmp_suid = INSN_SUID (insn); | |
302 | ||
f35bcbc5 RH |
303 | /* Mark all call-clobbered regs as dead after each call insn so that |
304 | a pseudo whose life span includes this insn will not go in one of | |
305 | them. If the function contains a non-local goto, mark all hard | |
306 | registers dead (except for stack related bits). | |
307 | ||
cce8749e CH |
308 | Then mark those regs as all dead for the continuing scan |
309 | of the insns before the call. */ | |
310 | ||
311 | if (GET_CODE (insn) == CALL_INSN) | |
312 | { | |
313 | last_call_suid = INSN_SUID (insn); | |
70ceb906 | 314 | |
f35bcbc5 RH |
315 | if (current_function_has_nonlocal_label) |
316 | { | |
317 | IOR_COMPL_HARD_REG_SET (after_insn_hard_regs[last_call_suid], | |
318 | fixed_reg_set); | |
319 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) | |
320 | if (! fixed_regs[i]) | |
321 | regs_live[i] = 0; | |
322 | } | |
323 | else | |
324 | { | |
325 | IOR_HARD_REG_SET (after_insn_hard_regs[last_call_suid], | |
326 | call_used_reg_set); | |
327 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) | |
328 | if (call_used_regs[i]) | |
329 | regs_live[i] = 0; | |
330 | } | |
e21fa13a | 331 | |
56b5e76b DE |
332 | /* It is important that this be done after processing the insn's |
333 | pattern because we want the function result register to still | |
334 | be live if it's also used to pass arguments. */ | |
cad6f7d0 | 335 | stupid_mark_refs (CALL_INSN_FUNCTION_USAGE (insn), chain); |
cce8749e | 336 | } |
cad6f7d0 BS |
337 | |
338 | if (GET_CODE (insn) != NOTE && GET_CODE (insn) != BARRIER) | |
339 | { | |
cad6f7d0 BS |
340 | /* The regs_live array doesn't say anything about hard registers |
341 | clobbered by this insn. So we need an extra pass over the | |
342 | pattern. */ | |
343 | current_chain = chain; | |
344 | if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') | |
84832317 | 345 | note_stores (PATTERN (insn), find_clobbered_regs, NULL); |
cad6f7d0 BS |
346 | } |
347 | ||
4d1d8045 BS |
348 | if (GET_CODE (insn) == JUMP_INSN && computed_jump_p (insn)) |
349 | current_function_has_computed_jump = 1; | |
cce8749e CH |
350 | } |
351 | ||
352 | /* Now decide the order in which to allocate the pseudo registers. */ | |
353 | ||
354 | for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++) | |
355 | reg_order[i] = i; | |
356 | ||
357 | qsort (®_order[LAST_VIRTUAL_REGISTER + 1], | |
358 | max_regno - LAST_VIRTUAL_REGISTER - 1, sizeof (int), | |
359 | stupid_reg_compare); | |
360 | ||
361 | /* Now, in that order, try to find hard registers for those pseudo regs. */ | |
362 | ||
363 | for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++) | |
364 | { | |
365 | register int r = reg_order[i]; | |
cce8749e | 366 | |
68f02135 | 367 | /* Some regnos disappear from the rtl. Ignore them to avoid crash. |
f35bcbc5 | 368 | Also don't allocate registers that cross a setjmp, or live across |
cad6f7d0 BS |
369 | a call if this function receives a nonlocal goto. |
370 | Also ignore registers we didn't see during the scan. */ | |
f35bcbc5 | 371 | if (regno_reg_rtx[r] == 0 || regs_crosses_setjmp[r] |
cad6f7d0 | 372 | || (reg_where_born_exact[r] == 0 && reg_where_dead[r] == 0) |
f35bcbc5 RH |
373 | || (REG_N_CALLS_CROSSED (r) > 0 |
374 | && current_function_has_nonlocal_label)) | |
cce8749e CH |
375 | continue; |
376 | ||
377 | /* Now find the best hard-register class for this pseudo register */ | |
378 | if (N_REG_CLASSES > 1) | |
b1f21e0a | 379 | reg_renumber[r] = stupid_find_reg (REG_N_CALLS_CROSSED (r), |
70ceb906 RK |
380 | reg_preferred_class (r), |
381 | PSEUDO_REGNO_MODE (r), | |
cad6f7d0 | 382 | REG_WHERE_BORN (r), |
cc33944a RK |
383 | reg_where_dead[r], |
384 | regs_change_size[r]); | |
cce8749e | 385 | |
70ceb906 RK |
386 | /* If no reg available in that class, try alternate class. */ |
387 | if (reg_renumber[r] == -1 && reg_alternate_class (r) != NO_REGS) | |
b1f21e0a | 388 | reg_renumber[r] = stupid_find_reg (REG_N_CALLS_CROSSED (r), |
70ceb906 | 389 | reg_alternate_class (r), |
cce8749e | 390 | PSEUDO_REGNO_MODE (r), |
cad6f7d0 | 391 | REG_WHERE_BORN (r), |
cc33944a RK |
392 | reg_where_dead[r], |
393 | regs_change_size[r]); | |
cce8749e CH |
394 | } |
395 | ||
cad6f7d0 BS |
396 | /* Fill in the pseudo reg life information into the insn chain. */ |
397 | for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++) | |
398 | { | |
399 | struct insn_chain *chain; | |
400 | int regno; | |
401 | ||
402 | regno = reg_renumber[i]; | |
403 | if (regno < 0) | |
404 | continue; | |
405 | ||
406 | chain = reg_where_dead_chain[i]; | |
239a0f5b | 407 | SET_REGNO_REG_SET (&chain->dead_or_set, i); |
cad6f7d0 | 408 | |
285f3cf0 R |
409 | while ((chain = chain->prev) |
410 | && INSN_SUID (chain->insn) > reg_where_born_exact[i]) | |
239a0f5b | 411 | SET_REGNO_REG_SET (&chain->live_throughout, i); |
cad6f7d0 | 412 | |
285f3cf0 | 413 | if (chain) |
239a0f5b | 414 | SET_REGNO_REG_SET (&chain->dead_or_set, i); |
cad6f7d0 BS |
415 | } |
416 | ||
cce8749e CH |
417 | if (file) |
418 | dump_flow_info (file); | |
56a65848 DB |
419 | |
420 | free (regs_live); | |
421 | free (uid_suid); | |
422 | free (reg_where_dead); | |
cad6f7d0 BS |
423 | free (reg_where_born_exact); |
424 | free (reg_where_born_clobber); | |
425 | free (reg_where_dead_chain); | |
56a65848 DB |
426 | free (reg_order); |
427 | free (regs_change_size); | |
428 | free (regs_crosses_setjmp); | |
429 | free (after_insn_hard_regs); | |
cce8749e CH |
430 | } |
431 | ||
432 | /* Comparison function for qsort. | |
433 | Returns -1 (1) if register *R1P is higher priority than *R2P. */ | |
434 | ||
435 | static int | |
436 | stupid_reg_compare (r1p, r2p) | |
e1b6684c KG |
437 | const PTR r1p; |
438 | const PTR r2p; | |
cce8749e | 439 | { |
ec0ce6e2 | 440 | register int r1 = *(const int *)r1p, r2 = *(const int *)r2p; |
cad6f7d0 BS |
441 | register int len1 = reg_where_dead[r1] - REG_WHERE_BORN (r1); |
442 | register int len2 = reg_where_dead[r2] - REG_WHERE_BORN (r2); | |
cce8749e CH |
443 | int tem; |
444 | ||
445 | tem = len2 - len1; | |
70ceb906 RK |
446 | if (tem != 0) |
447 | return tem; | |
cce8749e | 448 | |
b1f21e0a | 449 | tem = REG_N_REFS (r1) - REG_N_REFS (r2); |
70ceb906 RK |
450 | if (tem != 0) |
451 | return tem; | |
cce8749e CH |
452 | |
453 | /* If regs are equally good, sort by regno, | |
454 | so that the results of qsort leave nothing to chance. */ | |
455 | return r1 - r2; | |
456 | } | |
457 | \f | |
458 | /* Find a block of SIZE words of hard registers in reg_class CLASS | |
459 | that can hold a value of machine-mode MODE | |
460 | (but actually we test only the first of the block for holding MODE) | |
f395cd86 RK |
461 | currently free from after insn whose suid is BORN_INSN |
462 | through the insn whose suid is DEAD_INSN, | |
cce8749e CH |
463 | and return the number of the first of them. |
464 | Return -1 if such a block cannot be found. | |
465 | ||
466 | If CALL_PRESERVED is nonzero, insist on registers preserved | |
cc33944a RK |
467 | over subroutine calls, and return -1 if cannot find such. |
468 | ||
469 | If CHANGES_SIZE is nonzero, it means this register was used as the | |
470 | operand of a SUBREG that changes its size. */ | |
cce8749e CH |
471 | |
472 | static int | |
cc33944a RK |
473 | stupid_find_reg (call_preserved, class, mode, |
474 | born_insn, dead_insn, changes_size) | |
cce8749e CH |
475 | int call_preserved; |
476 | enum reg_class class; | |
477 | enum machine_mode mode; | |
478 | int born_insn, dead_insn; | |
e51712db | 479 | int changes_size ATTRIBUTE_UNUSED; |
cce8749e CH |
480 | { |
481 | register int i, ins; | |
482 | #ifdef HARD_REG_SET | |
483 | register /* Declare them register if they are scalars. */ | |
484 | #endif | |
485 | HARD_REG_SET used, this_reg; | |
486 | #ifdef ELIMINABLE_REGS | |
487 | static struct {int from, to; } eliminables[] = ELIMINABLE_REGS; | |
488 | #endif | |
489 | ||
f395cd86 | 490 | /* If this register's life is more than 5,000 insns, we probably |
0f41302f | 491 | can't allocate it, so don't waste the time trying. This avoids |
f395cd86 RK |
492 | quadratic behavior on programs that have regularly-occurring |
493 | SAVE_EXPRs. */ | |
494 | if (dead_insn > born_insn + 5000) | |
495 | return -1; | |
496 | ||
cce8749e CH |
497 | COPY_HARD_REG_SET (used, |
498 | call_preserved ? call_used_reg_set : fixed_reg_set); | |
499 | ||
500 | #ifdef ELIMINABLE_REGS | |
e51712db | 501 | for (i = 0; i < (int)(sizeof eliminables / sizeof eliminables[0]); i++) |
cce8749e | 502 | SET_HARD_REG_BIT (used, eliminables[i].from); |
1e513cfb DE |
503 | #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM |
504 | SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM); | |
505 | #endif | |
cce8749e CH |
506 | #else |
507 | SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM); | |
508 | #endif | |
509 | ||
510 | for (ins = born_insn; ins < dead_insn; ins++) | |
511 | IOR_HARD_REG_SET (used, after_insn_hard_regs[ins]); | |
512 | ||
4d1d8045 BS |
513 | #ifdef STACK_REGS |
514 | if (current_function_has_computed_jump) | |
515 | for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++) | |
516 | SET_HARD_REG_BIT (used, i); | |
517 | #endif | |
518 | ||
cce8749e CH |
519 | IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]); |
520 | ||
cc33944a RK |
521 | #ifdef CLASS_CANNOT_CHANGE_SIZE |
522 | if (changes_size) | |
523 | IOR_HARD_REG_SET (used, | |
524 | reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]); | |
525 | #endif | |
526 | ||
cce8749e CH |
527 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) |
528 | { | |
529 | #ifdef REG_ALLOC_ORDER | |
530 | int regno = reg_alloc_order[i]; | |
531 | #else | |
532 | int regno = i; | |
533 | #endif | |
534 | ||
cce8749e CH |
535 | if (! TEST_HARD_REG_BIT (used, regno) |
536 | && HARD_REGNO_MODE_OK (regno, mode)) | |
537 | { | |
538 | register int j; | |
539 | register int size1 = HARD_REGNO_NREGS (regno, mode); | |
540 | for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++); | |
541 | if (j == size1) | |
542 | { | |
543 | CLEAR_HARD_REG_SET (this_reg); | |
544 | while (--j >= 0) | |
545 | SET_HARD_REG_BIT (this_reg, regno + j); | |
546 | for (ins = born_insn; ins < dead_insn; ins++) | |
547 | { | |
548 | IOR_HARD_REG_SET (after_insn_hard_regs[ins], this_reg); | |
549 | } | |
550 | return regno; | |
551 | } | |
552 | #ifndef REG_ALLOC_ORDER | |
70ceb906 | 553 | i += j; /* Skip starting points we know will lose */ |
cce8749e CH |
554 | #endif |
555 | } | |
556 | } | |
70ceb906 | 557 | |
cce8749e CH |
558 | return -1; |
559 | } | |
560 | \f | |
285f3cf0 R |
561 | /* Note that REG is being set or referenced, and add the appropriate |
562 | REG_DEAD / REG_UNUSED note(s). For sets, LIVE_BEFORE_P will be 0, | |
563 | while for references, LIVE_BEFORE_P will be 1. | |
564 | INSN is the instruction that the reg notes have to be added to. */ | |
565 | static void | |
566 | mark_hard_ref (reg, live_before_p, chain) | |
567 | rtx reg; | |
568 | int live_before_p; | |
569 | struct insn_chain *chain; | |
570 | { | |
571 | /* Hard reg: mark it live for continuing scan of previous insns. */ | |
572 | int regno = REGNO (reg); | |
573 | char *live = regs_live; | |
574 | register int j; | |
575 | int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg)); | |
576 | ||
577 | for (j = nregs - 1; j >= 0; j--) | |
578 | { | |
579 | if (! fixed_regs[regno+j] | |
580 | && (! live_before_p || ! live[regno+j])) | |
239a0f5b | 581 | SET_REGNO_REG_SET (&chain->dead_or_set, regno+j); |
285f3cf0 R |
582 | regs_ever_live[regno+j] = 1; |
583 | live[regno+j] = live_before_p; | |
584 | } | |
585 | } | |
586 | ||
cce8749e CH |
587 | /* Walk X, noting all assignments and references to registers |
588 | and recording what they imply about life spans. | |
589 | INSN is the current insn, supplied so we can find its suid. */ | |
590 | ||
591 | static void | |
cad6f7d0 BS |
592 | stupid_mark_refs (x, chain) |
593 | rtx x; | |
594 | struct insn_chain *chain; | |
cce8749e | 595 | { |
e21fa13a | 596 | register RTX_CODE code; |
6f7d635c | 597 | register const char *fmt; |
cce8749e | 598 | register int regno, i; |
cad6f7d0 | 599 | rtx insn = chain->insn; |
cce8749e | 600 | |
e21fa13a RK |
601 | if (x == 0) |
602 | return; | |
603 | ||
604 | code = GET_CODE (x); | |
605 | ||
cce8749e CH |
606 | if (code == SET || code == CLOBBER) |
607 | { | |
2d43e089 RK |
608 | if (SET_DEST (x) != 0 |
609 | && (GET_CODE (SET_DEST (x)) == REG | |
610 | || (GET_CODE (SET_DEST (x)) == SUBREG | |
611 | && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG | |
612 | && (REGNO (SUBREG_REG (SET_DEST (x))) | |
613 | >= FIRST_PSEUDO_REGISTER)))) | |
cce8749e CH |
614 | { |
615 | /* Register is being assigned. */ | |
285f3cf0 R |
616 | rtx reg = SET_DEST (x); |
617 | ||
2d43e089 RK |
618 | /* If setting a SUBREG, we treat the entire reg as being set. */ |
619 | if (GET_CODE (SET_DEST (x)) == SUBREG) | |
285f3cf0 R |
620 | reg = SUBREG_REG (reg); |
621 | ||
622 | regno = REGNO (reg); | |
cce8749e CH |
623 | |
624 | /* For hard regs, update the where-live info. */ | |
625 | if (regno < FIRST_PSEUDO_REGISTER) | |
626 | { | |
627 | register int j | |
628 | = HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (x))); | |
70ceb906 | 629 | |
285f3cf0 R |
630 | mark_hard_ref (reg, 0, chain); |
631 | ||
cce8749e CH |
632 | while (--j >= 0) |
633 | { | |
cce8749e CH |
634 | /* The following line is for unused outputs; |
635 | they do get stored even though never used again. */ | |
50b46d92 | 636 | MARK_LIVE_AFTER (insn, regno+j); |
70ceb906 | 637 | |
239a0f5b | 638 | CLEAR_REGNO_REG_SET (&chain->live_throughout, regno + j); |
285f3cf0 | 639 | |
cce8749e CH |
640 | /* When a hard reg is clobbered, mark it in use |
641 | just before this insn, so it is live all through. */ | |
642 | if (code == CLOBBER && INSN_SUID (insn) > 0) | |
643 | SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (insn) - 1], | |
50b46d92 | 644 | regno+j); |
cce8749e CH |
645 | } |
646 | } | |
647 | /* For pseudo regs, record where born, where dead, number of | |
648 | times used, and whether live across a call. */ | |
649 | else | |
650 | { | |
651 | /* Update the life-interval bounds of this pseudo reg. */ | |
652 | ||
653 | /* When a pseudo-reg is CLOBBERed, it is born just before | |
654 | the clobbering insn. When setting, just after. */ | |
655 | int where_born = INSN_SUID (insn) - (code == CLOBBER); | |
656 | ||
cad6f7d0 BS |
657 | reg_where_born_exact[regno] = INSN_SUID (insn); |
658 | reg_where_born_clobber[regno] = (code == CLOBBER); | |
659 | ||
660 | if (reg_where_dead_chain[regno] == 0) | |
661 | reg_where_dead_chain[regno] = chain; | |
70ceb906 | 662 | |
cce8749e CH |
663 | /* The reg must live at least one insn even |
664 | in it is never again used--because it has to go | |
665 | in SOME hard reg. Mark it as dying after the current | |
666 | insn so that it will conflict with any other outputs of | |
667 | this insn. */ | |
668 | if (reg_where_dead[regno] < where_born + 2) | |
63cc239c RK |
669 | { |
670 | reg_where_dead[regno] = where_born + 2; | |
671 | regs_live[regno] = 1; | |
672 | } | |
cce8749e CH |
673 | |
674 | /* Count the refs of this reg. */ | |
b1f21e0a | 675 | REG_N_REFS (regno)++; |
cce8749e CH |
676 | |
677 | if (last_call_suid < reg_where_dead[regno]) | |
b1f21e0a | 678 | REG_N_CALLS_CROSSED (regno) += 1; |
68f02135 RK |
679 | |
680 | if (last_setjmp_suid < reg_where_dead[regno]) | |
681 | regs_crosses_setjmp[regno] = 1; | |
79d06d29 | 682 | |
10195bd8 JW |
683 | /* If this register is clobbered or it is only used in |
684 | this insn and is only set, mark it unused. We have | |
685 | to do this even when not optimizing so that MD patterns | |
686 | which count on this behavior (e.g., it not causing an | |
687 | output reload on an insn setting CC) will operate | |
688 | correctly. */ | |
79d06d29 | 689 | if (GET_CODE (SET_DEST (x)) == REG |
10195bd8 JW |
690 | && (code == CLOBBER |
691 | || (REGNO_FIRST_UID (regno) == INSN_UID (insn) | |
692 | && REGNO_LAST_UID (regno) == INSN_UID (insn) | |
693 | && ! reg_mentioned_p (SET_DEST (x), | |
694 | SET_SRC (x))))) | |
38a448ca RH |
695 | REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_UNUSED, |
696 | SET_DEST (x), | |
697 | REG_NOTES (insn)); | |
cce8749e CH |
698 | } |
699 | } | |
70ceb906 | 700 | |
cce8749e CH |
701 | /* Record references from the value being set, |
702 | or from addresses in the place being set if that's not a reg. | |
703 | If setting a SUBREG, we treat the entire reg as *used*. */ | |
704 | if (code == SET) | |
705 | { | |
cad6f7d0 | 706 | stupid_mark_refs (SET_SRC (x), chain); |
cce8749e | 707 | if (GET_CODE (SET_DEST (x)) != REG) |
cad6f7d0 | 708 | stupid_mark_refs (SET_DEST (x), chain); |
cce8749e CH |
709 | } |
710 | return; | |
711 | } | |
712 | ||
cc33944a RK |
713 | else if (code == SUBREG |
714 | && GET_CODE (SUBREG_REG (x)) == REG | |
715 | && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER | |
716 | && (GET_MODE_SIZE (GET_MODE (x)) | |
7d79bcc1 RK |
717 | != GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))) |
718 | && (INTEGRAL_MODE_P (GET_MODE (x)) | |
719 | || INTEGRAL_MODE_P (GET_MODE (SUBREG_REG (x))))) | |
cc33944a RK |
720 | regs_change_size[REGNO (SUBREG_REG (x))] = 1; |
721 | ||
cce8749e CH |
722 | /* Register value being used, not set. */ |
723 | ||
cc33944a | 724 | else if (code == REG) |
cce8749e CH |
725 | { |
726 | regno = REGNO (x); | |
727 | if (regno < FIRST_PSEUDO_REGISTER) | |
285f3cf0 R |
728 | /* Hard reg: mark it live for continuing scan of previous insns. */ |
729 | mark_hard_ref (x, 1, chain); | |
cce8749e CH |
730 | else |
731 | { | |
732 | /* Pseudo reg: record first use, last use and number of uses. */ | |
733 | ||
cad6f7d0 BS |
734 | reg_where_born_exact[regno] = INSN_SUID (insn); |
735 | reg_where_born_clobber[regno] = 0; | |
b1f21e0a | 736 | REG_N_REFS (regno)++; |
cce8749e CH |
737 | if (regs_live[regno] == 0) |
738 | { | |
739 | regs_live[regno] = 1; | |
740 | reg_where_dead[regno] = INSN_SUID (insn); | |
cad6f7d0 | 741 | reg_where_dead_chain[regno] = chain; |
cce8749e CH |
742 | } |
743 | } | |
744 | return; | |
745 | } | |
746 | ||
747 | /* Recursive scan of all other rtx's. */ | |
748 | ||
749 | fmt = GET_RTX_FORMAT (code); | |
750 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
751 | { | |
752 | if (fmt[i] == 'e') | |
cad6f7d0 | 753 | stupid_mark_refs (XEXP (x, i), chain); |
d4757e6a | 754 | else if (fmt[i] == 'E') |
cce8749e CH |
755 | { |
756 | register int j; | |
757 | for (j = XVECLEN (x, i) - 1; j >= 0; j--) | |
cad6f7d0 | 758 | stupid_mark_refs (XVECEXP (x, i, j), chain); |
cce8749e CH |
759 | } |
760 | } | |
761 | } |