]>
Commit | Line | Data |
---|---|---|
60ecc450 | 1 | /* Generic sibling call optimization support |
f9b1fb17 | 2 | Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004 |
60b8c5b3 | 3 | Free Software Foundation, Inc. |
60ecc450 | 4 | |
f12b58b3 | 5 | This file is part of GCC. |
60ecc450 | 6 | |
f12b58b3 | 7 | GCC is free software; you can redistribute it and/or modify it under |
8 | the terms of the GNU General Public License as published by the Free | |
9 | Software Foundation; either version 2, or (at your option) any later | |
10 | version. | |
60ecc450 | 11 | |
f12b58b3 | 12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
60ecc450 | 16 | |
17 | You should have received a copy of the GNU General Public License | |
f12b58b3 | 18 | along with GCC; see the file COPYING. If not, write to the Free |
19 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
20 | 02111-1307, USA. */ | |
60ecc450 | 21 | |
22 | #include "config.h" | |
23 | #include "system.h" | |
805e22b2 | 24 | #include "coretypes.h" |
25 | #include "tm.h" | |
60ecc450 | 26 | |
27 | #include "rtl.h" | |
28 | #include "regs.h" | |
29 | #include "function.h" | |
30 | #include "hard-reg-set.h" | |
31 | #include "flags.h" | |
32 | #include "insn-config.h" | |
33 | #include "recog.h" | |
34 | #include "basic-block.h" | |
35 | #include "output.h" | |
36 | #include "except.h" | |
99b12e3f | 37 | #include "tree.h" |
60ecc450 | 38 | |
b3663637 | 39 | /* In case alternate_exit_block contains copy from pseudo, to return value, |
40 | record the pseudo here. In such case the pseudo must be set to function | |
41 | return in the sibcall sequence. */ | |
42 | static rtx return_value_pseudo; | |
43 | ||
60b8c5b3 | 44 | static int identify_call_return_value (rtx, rtx *, rtx *); |
45 | static rtx skip_copy_to_return_value (rtx); | |
46 | static rtx skip_use_of_return_value (rtx, enum rtx_code); | |
47 | static rtx skip_stack_adjustment (rtx); | |
48 | static rtx skip_pic_restore (rtx); | |
49 | static rtx skip_jump_insn (rtx); | |
50 | static int call_ends_block_p (rtx, rtx); | |
51 | static int uses_addressof (rtx); | |
52 | static int sequence_uses_addressof (rtx); | |
53 | static void purge_reg_equiv_notes (void); | |
54 | static void purge_mem_unchanging_flag (rtx); | |
55 | static rtx skip_unreturned_value (rtx); | |
60ecc450 | 56 | |
57 | /* Examine a CALL_PLACEHOLDER pattern and determine where the call's | |
58 | return value is located. P_HARD_RETURN receives the hard register | |
59 | that the function used; P_SOFT_RETURN receives the pseudo register | |
f712a0dc | 60 | that the sequence used. Return nonzero if the values were located. */ |
60ecc450 | 61 | |
62 | static int | |
60b8c5b3 | 63 | identify_call_return_value (rtx cp, rtx *p_hard_return, rtx *p_soft_return) |
60ecc450 | 64 | { |
65 | rtx insn, set, hard, soft; | |
66 | ||
60ecc450 | 67 | insn = XEXP (cp, 0); |
6aae6e10 | 68 | /* Search backward through the "normal" call sequence to the CALL insn. */ |
69 | while (NEXT_INSN (insn)) | |
60ecc450 | 70 | insn = NEXT_INSN (insn); |
6aae6e10 | 71 | while (GET_CODE (insn) != CALL_INSN) |
72 | insn = PREV_INSN (insn); | |
60ecc450 | 73 | |
74 | /* Assume the pattern is (set (dest) (call ...)), or that the first | |
75 | member of a parallel is. This is the hard return register used | |
76 | by the function. */ | |
77 | if (GET_CODE (PATTERN (insn)) == SET | |
78 | && GET_CODE (SET_SRC (PATTERN (insn))) == CALL) | |
79 | hard = SET_DEST (PATTERN (insn)); | |
80 | else if (GET_CODE (PATTERN (insn)) == PARALLEL | |
81 | && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET | |
82 | && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == CALL) | |
83 | hard = SET_DEST (XVECEXP (PATTERN (insn), 0, 0)); | |
84 | else | |
85 | return 0; | |
86 | ||
87 | /* If we didn't get a single hard register (e.g. a parallel), give up. */ | |
88 | if (GET_CODE (hard) != REG) | |
89 | return 0; | |
40734805 | 90 | |
6aae6e10 | 91 | /* Stack adjustment done after call may appear here. */ |
92 | insn = skip_stack_adjustment (insn); | |
93 | if (! insn) | |
94 | return 0; | |
95 | ||
0907e04d | 96 | /* Restore of GP register may appear here. */ |
97 | insn = skip_pic_restore (insn); | |
98 | if (! insn) | |
99 | return 0; | |
100 | ||
60ecc450 | 101 | /* If there's nothing after, there's no soft return value. */ |
102 | insn = NEXT_INSN (insn); | |
103 | if (! insn) | |
104 | return 0; | |
40734805 | 105 | |
60ecc450 | 106 | /* We're looking for a source of the hard return register. */ |
107 | set = single_set (insn); | |
108 | if (! set || SET_SRC (set) != hard) | |
109 | return 0; | |
110 | ||
111 | soft = SET_DEST (set); | |
112 | insn = NEXT_INSN (insn); | |
113 | ||
114 | /* Allow this first destination to be copied to a second register, | |
115 | as might happen if the first register wasn't the particular pseudo | |
116 | we'd been expecting. */ | |
117 | if (insn | |
118 | && (set = single_set (insn)) != NULL_RTX | |
119 | && SET_SRC (set) == soft) | |
120 | { | |
121 | soft = SET_DEST (set); | |
122 | insn = NEXT_INSN (insn); | |
123 | } | |
124 | ||
125 | /* Don't fool with anything but pseudo registers. */ | |
126 | if (GET_CODE (soft) != REG || REGNO (soft) < FIRST_PSEUDO_REGISTER) | |
127 | return 0; | |
128 | ||
129 | /* This value must not be modified before the end of the sequence. */ | |
130 | if (reg_set_between_p (soft, insn, NULL_RTX)) | |
131 | return 0; | |
132 | ||
133 | *p_hard_return = hard; | |
134 | *p_soft_return = soft; | |
135 | ||
136 | return 1; | |
137 | } | |
138 | ||
139 | /* If the first real insn after ORIG_INSN copies to this function's | |
140 | return value from RETVAL, then return the insn which performs the | |
141 | copy. Otherwise return ORIG_INSN. */ | |
142 | ||
143 | static rtx | |
60b8c5b3 | 144 | skip_copy_to_return_value (rtx orig_insn) |
60ecc450 | 145 | { |
146 | rtx insn, set = NULL_RTX; | |
3915b59e | 147 | rtx hardret, softret; |
148 | ||
149 | /* If there is no return value, we have nothing to do. */ | |
150 | if (! identify_call_return_value (PATTERN (orig_insn), &hardret, &softret)) | |
151 | return orig_insn; | |
60ecc450 | 152 | |
153 | insn = next_nonnote_insn (orig_insn); | |
154 | if (! insn) | |
155 | return orig_insn; | |
156 | ||
157 | set = single_set (insn); | |
158 | if (! set) | |
159 | return orig_insn; | |
160 | ||
b3663637 | 161 | if (return_value_pseudo) |
162 | { | |
08771946 | 163 | if (SET_DEST (set) == return_value_pseudo |
164 | && SET_SRC (set) == softret) | |
165 | return insn; | |
b3663637 | 166 | return orig_insn; |
167 | } | |
168 | ||
60ecc450 | 169 | /* The destination must be the same as the called function's return |
170 | value to ensure that any return value is put in the same place by the | |
40734805 | 171 | current function and the function we're calling. |
60ecc450 | 172 | |
173 | Further, the source must be the same as the pseudo into which the | |
174 | called function's return value was copied. Otherwise we're returning | |
175 | some other value. */ | |
176 | ||
177 | if (SET_DEST (set) == current_function_return_rtx | |
178 | && REG_P (SET_DEST (set)) | |
7a8d641b | 179 | && OUTGOING_REGNO (REGNO (SET_DEST (set))) == REGNO (hardret) |
60ecc450 | 180 | && SET_SRC (set) == softret) |
181 | return insn; | |
182 | ||
84e81e84 | 183 | /* Recognize the situation when the called function's return value |
184 | is copied in two steps: first into an intermediate pseudo, then | |
185 | the into the calling functions return value register. */ | |
186 | ||
187 | if (REG_P (SET_DEST (set)) | |
188 | && SET_SRC (set) == softret) | |
189 | { | |
190 | rtx x = SET_DEST (set); | |
191 | ||
192 | insn = next_nonnote_insn (insn); | |
193 | if (! insn) | |
194 | return orig_insn; | |
195 | ||
196 | set = single_set (insn); | |
197 | if (! set) | |
198 | return orig_insn; | |
199 | ||
200 | if (SET_DEST (set) == current_function_return_rtx | |
201 | && REG_P (SET_DEST (set)) | |
202 | && OUTGOING_REGNO (REGNO (SET_DEST (set))) == REGNO (hardret) | |
203 | && SET_SRC (set) == x) | |
204 | return insn; | |
205 | } | |
206 | ||
60ecc450 | 207 | /* It did not look like a copy of the return value, so return the |
208 | same insn we were passed. */ | |
209 | return orig_insn; | |
210 | } | |
211 | ||
212 | /* If the first real insn after ORIG_INSN is a CODE of this function's return | |
213 | value, return insn. Otherwise return ORIG_INSN. */ | |
214 | ||
215 | static rtx | |
60b8c5b3 | 216 | skip_use_of_return_value (rtx orig_insn, enum rtx_code code) |
60ecc450 | 217 | { |
218 | rtx insn; | |
219 | ||
220 | insn = next_nonnote_insn (orig_insn); | |
221 | ||
222 | if (insn | |
223 | && GET_CODE (insn) == INSN | |
224 | && GET_CODE (PATTERN (insn)) == code | |
225 | && (XEXP (PATTERN (insn), 0) == current_function_return_rtx | |
226 | || XEXP (PATTERN (insn), 0) == const0_rtx)) | |
227 | return insn; | |
228 | ||
229 | return orig_insn; | |
230 | } | |
231 | ||
f9dc5b3b | 232 | /* In case function does not return value, we get clobber of pseudo followed |
233 | by set to hard return value. */ | |
234 | static rtx | |
60b8c5b3 | 235 | skip_unreturned_value (rtx orig_insn) |
f9dc5b3b | 236 | { |
237 | rtx insn = next_nonnote_insn (orig_insn); | |
238 | ||
239 | /* Skip possible clobber of pseudo return register. */ | |
240 | if (insn | |
241 | && GET_CODE (insn) == INSN | |
242 | && GET_CODE (PATTERN (insn)) == CLOBBER | |
243 | && REG_P (XEXP (PATTERN (insn), 0)) | |
244 | && (REGNO (XEXP (PATTERN (insn), 0)) >= FIRST_PSEUDO_REGISTER)) | |
245 | { | |
246 | rtx set_insn = next_nonnote_insn (insn); | |
247 | rtx set; | |
248 | if (!set_insn) | |
249 | return insn; | |
250 | set = single_set (set_insn); | |
251 | if (!set | |
252 | || SET_SRC (set) != XEXP (PATTERN (insn), 0) | |
253 | || SET_DEST (set) != current_function_return_rtx) | |
254 | return insn; | |
255 | return set_insn; | |
256 | } | |
257 | return orig_insn; | |
258 | } | |
259 | ||
60ecc450 | 260 | /* If the first real insn after ORIG_INSN adjusts the stack pointer |
261 | by a constant, return the insn with the stack pointer adjustment. | |
262 | Otherwise return ORIG_INSN. */ | |
263 | ||
264 | static rtx | |
60b8c5b3 | 265 | skip_stack_adjustment (rtx orig_insn) |
60ecc450 | 266 | { |
267 | rtx insn, set = NULL_RTX; | |
268 | ||
269 | insn = next_nonnote_insn (orig_insn); | |
270 | ||
271 | if (insn) | |
272 | set = single_set (insn); | |
273 | ||
60ecc450 | 274 | if (insn |
275 | && set | |
276 | && GET_CODE (SET_SRC (set)) == PLUS | |
277 | && XEXP (SET_SRC (set), 0) == stack_pointer_rtx | |
278 | && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT | |
279 | && SET_DEST (set) == stack_pointer_rtx) | |
280 | return insn; | |
281 | ||
0907e04d | 282 | return orig_insn; |
283 | } | |
284 | ||
285 | /* If the first real insn after ORIG_INSN sets the pic register, | |
286 | return it. Otherwise return ORIG_INSN. */ | |
287 | ||
288 | static rtx | |
60b8c5b3 | 289 | skip_pic_restore (rtx orig_insn) |
0907e04d | 290 | { |
291 | rtx insn, set = NULL_RTX; | |
292 | ||
293 | insn = next_nonnote_insn (orig_insn); | |
294 | ||
295 | if (insn) | |
296 | set = single_set (insn); | |
297 | ||
298 | if (insn && set && SET_DEST (set) == pic_offset_table_rtx) | |
299 | return insn; | |
300 | ||
60ecc450 | 301 | return orig_insn; |
302 | } | |
303 | ||
304 | /* If the first real insn after ORIG_INSN is a jump, return the JUMP_INSN. | |
305 | Otherwise return ORIG_INSN. */ | |
306 | ||
307 | static rtx | |
60b8c5b3 | 308 | skip_jump_insn (rtx orig_insn) |
60ecc450 | 309 | { |
310 | rtx insn; | |
311 | ||
312 | insn = next_nonnote_insn (orig_insn); | |
313 | ||
314 | if (insn | |
315 | && GET_CODE (insn) == JUMP_INSN | |
b2816317 | 316 | && any_uncondjump_p (insn)) |
60ecc450 | 317 | return insn; |
318 | ||
319 | return orig_insn; | |
320 | } | |
142f5393 | 321 | \f |
322 | /* Using the above functions, see if INSN, skipping any of the above, | |
323 | goes all the way to END, the end of a basic block. Return 1 if so. */ | |
324 | ||
325 | static int | |
60b8c5b3 | 326 | call_ends_block_p (rtx insn, rtx end) |
142f5393 | 327 | { |
b3663637 | 328 | rtx new_insn; |
142f5393 | 329 | /* END might be a note, so get the last nonnote insn of the block. */ |
330 | end = next_nonnote_insn (PREV_INSN (end)); | |
331 | ||
332 | /* If the call was the end of the block, then we're OK. */ | |
333 | if (insn == end) | |
334 | return 1; | |
335 | ||
336 | /* Skip over copying from the call's return value pseudo into | |
337 | this function's hard return register and if that's the end | |
338 | of the block, we're OK. */ | |
b3663637 | 339 | new_insn = skip_copy_to_return_value (insn); |
340 | ||
341 | /* In case we return value in pseudo, we must set the pseudo to | |
342 | return value of called function, otherwise we are returning | |
343 | something else. */ | |
344 | if (return_value_pseudo && insn == new_insn) | |
345 | return 0; | |
346 | insn = new_insn; | |
347 | ||
142f5393 | 348 | if (insn == end) |
349 | return 1; | |
350 | ||
351 | /* Skip any stack adjustment. */ | |
352 | insn = skip_stack_adjustment (insn); | |
353 | if (insn == end) | |
354 | return 1; | |
355 | ||
356 | /* Skip over a CLOBBER of the return value as a hard reg. */ | |
357 | insn = skip_use_of_return_value (insn, CLOBBER); | |
358 | if (insn == end) | |
359 | return 1; | |
360 | ||
f9dc5b3b | 361 | /* Skip over a CLOBBER of the return value as a hard reg. */ |
362 | insn = skip_unreturned_value (insn); | |
363 | if (insn == end) | |
364 | return 1; | |
365 | ||
142f5393 | 366 | /* Skip over a USE of the return value (as a hard reg). */ |
367 | insn = skip_use_of_return_value (insn, USE); | |
368 | if (insn == end) | |
369 | return 1; | |
370 | ||
371 | /* Skip over a JUMP_INSN at the end of the block. If that doesn't end the | |
372 | block, the original CALL_INSN didn't. */ | |
373 | insn = skip_jump_insn (insn); | |
374 | return insn == end; | |
375 | } | |
60ecc450 | 376 | |
6e9acf75 | 377 | /* Scan the rtx X for ADDRESSOF expressions or |
378 | current_function_internal_arg_pointer registers. | |
cd921bcb | 379 | Return nonzero if an ADDRESSOF or current_function_internal_arg_pointer |
380 | is found outside of some MEM expression, else return zero. */ | |
60ecc450 | 381 | |
382 | static int | |
60b8c5b3 | 383 | uses_addressof (rtx x) |
60ecc450 | 384 | { |
385 | RTX_CODE code; | |
386 | int i, j; | |
387 | const char *fmt; | |
388 | ||
389 | if (x == NULL_RTX) | |
390 | return 0; | |
391 | ||
392 | code = GET_CODE (x); | |
393 | ||
cd921bcb | 394 | if (code == ADDRESSOF || x == current_function_internal_arg_pointer) |
6e9acf75 | 395 | return 1; |
396 | ||
397 | if (code == MEM) | |
cd921bcb | 398 | return 0; |
6e9acf75 | 399 | |
1be87b72 | 400 | /* Scan all subexpressions. */ |
60ecc450 | 401 | fmt = GET_RTX_FORMAT (code); |
402 | for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++) | |
403 | { | |
404 | if (*fmt == 'e') | |
405 | { | |
cd921bcb | 406 | if (uses_addressof (XEXP (x, i))) |
60ecc450 | 407 | return 1; |
408 | } | |
409 | else if (*fmt == 'E') | |
410 | { | |
411 | for (j = 0; j < XVECLEN (x, i); j++) | |
cd921bcb | 412 | if (uses_addressof (XVECEXP (x, i, j))) |
60ecc450 | 413 | return 1; |
414 | } | |
415 | } | |
416 | return 0; | |
417 | } | |
418 | ||
419 | /* Scan the sequence of insns in SEQ to see if any have an ADDRESSOF | |
424da949 | 420 | rtl expression or current_function_internal_arg_pointer occurrences |
6e9acf75 | 421 | not enclosed within a MEM. If an ADDRESSOF expression or |
422 | current_function_internal_arg_pointer is found, return nonzero, otherwise | |
423 | return zero. | |
60ecc450 | 424 | |
425 | This function handles CALL_PLACEHOLDERs which contain multiple sequences | |
426 | of insns. */ | |
427 | ||
428 | static int | |
60b8c5b3 | 429 | sequence_uses_addressof (rtx seq) |
60ecc450 | 430 | { |
431 | rtx insn; | |
432 | ||
433 | for (insn = seq; insn; insn = NEXT_INSN (insn)) | |
9204e736 | 434 | if (INSN_P (insn)) |
60ecc450 | 435 | { |
436 | /* If this is a CALL_PLACEHOLDER, then recursively call ourselves | |
437 | with each nonempty sequence attached to the CALL_PLACEHOLDER. */ | |
438 | if (GET_CODE (insn) == CALL_INSN | |
439 | && GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER) | |
440 | { | |
441 | if (XEXP (PATTERN (insn), 0) != NULL_RTX | |
442 | && sequence_uses_addressof (XEXP (PATTERN (insn), 0))) | |
443 | return 1; | |
444 | if (XEXP (PATTERN (insn), 1) != NULL_RTX | |
445 | && sequence_uses_addressof (XEXP (PATTERN (insn), 1))) | |
446 | return 1; | |
447 | if (XEXP (PATTERN (insn), 2) != NULL_RTX | |
448 | && sequence_uses_addressof (XEXP (PATTERN (insn), 2))) | |
449 | return 1; | |
450 | } | |
cd921bcb | 451 | else if (uses_addressof (PATTERN (insn)) |
452 | || (REG_NOTES (insn) && uses_addressof (REG_NOTES (insn)))) | |
60ecc450 | 453 | return 1; |
454 | } | |
455 | return 0; | |
456 | } | |
457 | ||
458 | /* Remove all REG_EQUIV notes found in the insn chain. */ | |
459 | ||
460 | static void | |
60b8c5b3 | 461 | purge_reg_equiv_notes (void) |
60ecc450 | 462 | { |
463 | rtx insn; | |
464 | ||
465 | for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) | |
466 | { | |
467 | while (1) | |
468 | { | |
469 | rtx note = find_reg_note (insn, REG_EQUIV, 0); | |
470 | if (note) | |
471 | { | |
472 | /* Remove the note and keep looking at the notes for | |
473 | this insn. */ | |
474 | remove_note (insn, note); | |
475 | continue; | |
476 | } | |
477 | break; | |
478 | } | |
479 | } | |
480 | } | |
481 | ||
a3d180ac | 482 | /* Clear RTX_UNCHANGING_P flag of incoming argument MEMs. */ |
483 | ||
484 | static void | |
60b8c5b3 | 485 | purge_mem_unchanging_flag (rtx x) |
a3d180ac | 486 | { |
487 | RTX_CODE code; | |
488 | int i, j; | |
489 | const char *fmt; | |
490 | ||
491 | if (x == NULL_RTX) | |
492 | return; | |
493 | ||
494 | code = GET_CODE (x); | |
495 | ||
496 | if (code == MEM) | |
497 | { | |
498 | if (RTX_UNCHANGING_P (x) | |
499 | && (XEXP (x, 0) == current_function_internal_arg_pointer | |
500 | || (GET_CODE (XEXP (x, 0)) == PLUS | |
501 | && XEXP (XEXP (x, 0), 0) == | |
502 | current_function_internal_arg_pointer | |
503 | && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT))) | |
504 | RTX_UNCHANGING_P (x) = 0; | |
505 | return; | |
506 | } | |
507 | ||
1be87b72 | 508 | /* Scan all subexpressions. */ |
a3d180ac | 509 | fmt = GET_RTX_FORMAT (code); |
510 | for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++) | |
511 | { | |
512 | if (*fmt == 'e') | |
513 | purge_mem_unchanging_flag (XEXP (x, i)); | |
514 | else if (*fmt == 'E') | |
515 | for (j = 0; j < XVECLEN (x, i); j++) | |
516 | purge_mem_unchanging_flag (XVECEXP (x, i, j)); | |
517 | } | |
518 | } | |
519 | ||
60ecc450 | 520 | /* Replace the CALL_PLACEHOLDER with one of its children. INSN should be |
521 | the CALL_PLACEHOLDER insn; USE tells which child to use. */ | |
522 | ||
523 | void | |
60b8c5b3 | 524 | replace_call_placeholder (rtx insn, sibcall_use_t use) |
60ecc450 | 525 | { |
526 | if (use == sibcall_use_tail_recursion) | |
31d3e01c | 527 | emit_insn_before (XEXP (PATTERN (insn), 2), insn); |
60ecc450 | 528 | else if (use == sibcall_use_sibcall) |
31d3e01c | 529 | emit_insn_before (XEXP (PATTERN (insn), 1), insn); |
60ecc450 | 530 | else if (use == sibcall_use_normal) |
31d3e01c | 531 | emit_insn_before (XEXP (PATTERN (insn), 0), insn); |
60ecc450 | 532 | else |
47c251e5 | 533 | abort (); |
60ecc450 | 534 | |
535 | /* Turn off LABEL_PRESERVE_P for the tail recursion label if it | |
536 | exists. We only had to set it long enough to keep the jump | |
537 | pass above from deleting it as unused. */ | |
538 | if (XEXP (PATTERN (insn), 3)) | |
539 | LABEL_PRESERVE_P (XEXP (PATTERN (insn), 3)) = 0; | |
40734805 | 540 | |
1be87b72 | 541 | /* "Delete" the placeholder insn. */ |
b36d64df | 542 | remove_insn (insn); |
60ecc450 | 543 | } |
544 | ||
60ecc450 | 545 | /* Given a (possibly empty) set of potential sibling or tail recursion call |
546 | sites, determine if optimization is possible. | |
547 | ||
548 | Potential sibling or tail recursion calls are marked with CALL_PLACEHOLDER | |
549 | insns. The CALL_PLACEHOLDER insn holds chains of insns to implement a | |
550 | normal call, sibling call or tail recursive call. | |
551 | ||
552 | Replace the CALL_PLACEHOLDER with an appropriate insn chain. */ | |
553 | ||
554 | void | |
60b8c5b3 | 555 | optimize_sibling_and_tail_recursive_calls (void) |
60ecc450 | 556 | { |
557 | rtx insn, insns; | |
558 | basic_block alternate_exit = EXIT_BLOCK_PTR; | |
7cb6ef9c | 559 | bool no_sibcalls_this_function = false; |
2ce5f0b9 | 560 | bool successful_replacement = false; |
561 | bool replaced_call_placeholder = false; | |
60ecc450 | 562 | edge e; |
563 | ||
564 | insns = get_insns (); | |
565 | ||
4d1f4307 | 566 | cleanup_cfg (CLEANUP_PRE_SIBCALL | CLEANUP_PRE_LOOP); |
60ecc450 | 567 | |
568 | /* If there are no basic blocks, then there is nothing to do. */ | |
b3d6de89 | 569 | if (n_basic_blocks == 0) |
60ecc450 | 570 | return; |
571 | ||
40734805 | 572 | /* If we are using sjlj exceptions, we may need to add a call to |
7cb6ef9c | 573 | _Unwind_SjLj_Unregister at exit of the function. Which means |
574 | that we cannot do any sibcall transformations. */ | |
575 | if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ()) | |
576 | no_sibcalls_this_function = true; | |
577 | ||
b3663637 | 578 | return_value_pseudo = NULL_RTX; |
579 | ||
60ecc450 | 580 | /* Find the exit block. |
581 | ||
582 | It is possible that we have blocks which can reach the exit block | |
583 | directly. However, most of the time a block will jump (or fall into) | |
584 | N_BASIC_BLOCKS - 1, which in turn falls into the exit block. */ | |
585 | for (e = EXIT_BLOCK_PTR->pred; | |
586 | e && alternate_exit == EXIT_BLOCK_PTR; | |
587 | e = e->pred_next) | |
588 | { | |
589 | rtx insn; | |
590 | ||
591 | if (e->dest != EXIT_BLOCK_PTR || e->succ_next != NULL) | |
592 | continue; | |
593 | ||
594 | /* Walk forwards through the last normal block and see if it | |
595 | does nothing except fall into the exit block. */ | |
5496dbfc | 596 | for (insn = BB_HEAD (EXIT_BLOCK_PTR->prev_bb); |
60ecc450 | 597 | insn; |
598 | insn = NEXT_INSN (insn)) | |
599 | { | |
b3663637 | 600 | rtx set; |
60ecc450 | 601 | /* This should only happen once, at the start of this block. */ |
602 | if (GET_CODE (insn) == CODE_LABEL) | |
603 | continue; | |
604 | ||
605 | if (GET_CODE (insn) == NOTE) | |
606 | continue; | |
607 | ||
608 | if (GET_CODE (insn) == INSN | |
609 | && GET_CODE (PATTERN (insn)) == USE) | |
610 | continue; | |
611 | ||
b3663637 | 612 | /* Exit block also may contain copy from pseudo containing |
613 | return value to hard register. */ | |
614 | if (GET_CODE (insn) == INSN | |
615 | && (set = single_set (insn)) | |
616 | && SET_DEST (set) == current_function_return_rtx | |
617 | && REG_P (SET_SRC (set)) | |
618 | && !return_value_pseudo) | |
619 | { | |
620 | return_value_pseudo = SET_SRC (set); | |
621 | continue; | |
622 | } | |
623 | ||
60ecc450 | 624 | break; |
625 | } | |
626 | ||
627 | /* If INSN is zero, then the search walked all the way through the | |
628 | block without hitting anything interesting. This block is a | |
629 | valid alternate exit block. */ | |
630 | if (insn == NULL) | |
631 | alternate_exit = e->src; | |
b3663637 | 632 | else |
633 | return_value_pseudo = NULL; | |
60ecc450 | 634 | } |
635 | ||
636 | /* If the function uses ADDRESSOF, we can't (easily) determine | |
637 | at this point if the value will end up on the stack. */ | |
7cb6ef9c | 638 | no_sibcalls_this_function |= sequence_uses_addressof (insns); |
60ecc450 | 639 | |
640 | /* Walk the insn chain and find any CALL_PLACEHOLDER insns. We need to | |
641 | select one of the insn sequences attached to each CALL_PLACEHOLDER. | |
642 | ||
643 | The different sequences represent different ways to implement the call, | |
644 | ie, tail recursion, sibling call or normal call. | |
645 | ||
646 | Since we do not create nested CALL_PLACEHOLDERs, the scan | |
647 | continues with the insn that was after a replaced CALL_PLACEHOLDER; | |
648 | we don't rescan the replacement insns. */ | |
649 | for (insn = insns; insn; insn = NEXT_INSN (insn)) | |
650 | { | |
651 | if (GET_CODE (insn) == CALL_INSN | |
652 | && GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER) | |
653 | { | |
654 | int sibcall = (XEXP (PATTERN (insn), 1) != NULL_RTX); | |
655 | int tailrecursion = (XEXP (PATTERN (insn), 2) != NULL_RTX); | |
142f5393 | 656 | basic_block call_block = BLOCK_FOR_INSN (insn); |
cd921bcb | 657 | |
60ecc450 | 658 | /* alloca (until we have stack slot life analysis) inhibits |
659 | sibling call optimizations, but not tail recursion. | |
60ecc450 | 660 | Similarly if we use varargs or stdarg since they implicitly |
661 | may take the address of an argument. */ | |
7ccc713a | 662 | if (current_function_calls_alloca || current_function_stdarg) |
60ecc450 | 663 | sibcall = 0; |
664 | ||
142f5393 | 665 | /* See if there are any reasons we can't perform either sibling or |
666 | tail call optimizations. We must be careful with stack slots | |
7cb6ef9c | 667 | which are live at potential optimization sites. */ |
668 | if (no_sibcalls_this_function | |
669 | /* ??? Overly conservative. */ | |
670 | || frame_offset | |
f630ec0a | 671 | /* Any function that calls setjmp might have longjmp called from |
672 | any called function. ??? We really should represent this | |
673 | properly in the CFG so that this needn't be special cased. */ | |
674 | || current_function_calls_setjmp | |
142f5393 | 675 | /* Can't if more than one successor or single successor is not |
676 | exit block. These two tests prevent tail call optimization | |
de132707 | 677 | in the presence of active exception handlers. */ |
142f5393 | 678 | || call_block->succ == NULL |
00394ce8 | 679 | || call_block->succ->succ_next != NULL |
680 | || (call_block->succ->dest != EXIT_BLOCK_PTR | |
142f5393 | 681 | && call_block->succ->dest != alternate_exit) |
682 | /* If this call doesn't end the block, there are operations at | |
1be87b72 | 683 | the end of the block which we must execute after returning. */ |
5496dbfc | 684 | || ! call_ends_block_p (insn, BB_END (call_block))) |
00394ce8 | 685 | sibcall = 0, tailrecursion = 0; |
60ecc450 | 686 | |
687 | /* Select a set of insns to implement the call and emit them. | |
688 | Tail recursion is the most efficient, so select it over | |
689 | a tail/sibling call. */ | |
00394ce8 | 690 | |
2ce5f0b9 | 691 | if (sibcall || tailrecursion) |
692 | successful_replacement = true; | |
693 | replaced_call_placeholder = true; | |
694 | ||
40734805 | 695 | replace_call_placeholder (insn, |
696 | tailrecursion != 0 | |
60ecc450 | 697 | ? sibcall_use_tail_recursion |
698 | : sibcall != 0 | |
699 | ? sibcall_use_sibcall | |
700 | : sibcall_use_normal); | |
701 | } | |
702 | } | |
703 | ||
2ce5f0b9 | 704 | if (successful_replacement) |
a3d180ac | 705 | { |
706 | rtx insn; | |
99b12e3f | 707 | tree arg; |
a3d180ac | 708 | |
709 | /* A sibling call sequence invalidates any REG_EQUIV notes made for | |
40734805 | 710 | this function's incoming arguments. |
a3d180ac | 711 | |
712 | At the start of RTL generation we know the only REG_EQUIV notes | |
713 | in the rtl chain are those for incoming arguments, so we can safely | |
40734805 | 714 | flush any REG_EQUIV note. |
a3d180ac | 715 | |
716 | This is (slight) overkill. We could keep track of the highest | |
717 | argument we clobber and be more selective in removing notes, but it | |
718 | does not seem to be worth the effort. */ | |
719 | purge_reg_equiv_notes (); | |
720 | ||
721 | /* A sibling call sequence also may invalidate RTX_UNCHANGING_P | |
722 | flag of some incoming arguments MEM RTLs, because it can write into | |
723 | those slots. We clear all those bits now. | |
40734805 | 724 | |
a3d180ac | 725 | This is (slight) overkill, we could keep track of which arguments |
726 | we actually write into. */ | |
727 | for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) | |
728 | { | |
e902cfce | 729 | if (INSN_P (insn)) |
a3d180ac | 730 | purge_mem_unchanging_flag (PATTERN (insn)); |
731 | } | |
99b12e3f | 732 | |
733 | /* Similarly, invalidate RTX_UNCHANGING_P for any incoming | |
a113df96 | 734 | arguments passed in registers. */ |
40734805 | 735 | for (arg = DECL_ARGUMENTS (current_function_decl); |
736 | arg; | |
99b12e3f | 737 | arg = TREE_CHAIN (arg)) |
738 | { | |
739 | if (REG_P (DECL_RTL (arg))) | |
740 | RTX_UNCHANGING_P (DECL_RTL (arg)) = false; | |
741 | } | |
a3d180ac | 742 | } |
60ecc450 | 743 | |
40734805 | 744 | /* There may have been NOTE_INSN_BLOCK_{BEGIN,END} notes in the |
60ecc450 | 745 | CALL_PLACEHOLDER alternatives that we didn't emit. Rebuild the |
746 | lexical block tree to correspond to the notes that still exist. */ | |
747 | if (replaced_call_placeholder) | |
f1ab82be | 748 | reorder_blocks (); |
60ecc450 | 749 | |
750 | /* This information will be invalid after inline expansion. Kill it now. */ | |
e086b176 | 751 | free_basic_block_vars (); |
cd0fe062 | 752 | free_EXPR_LIST_list (&tail_recursion_label_list); |
60ecc450 | 753 | } |