1 /* Generic sibling call optimization support
2 Copyright (C) 1999, 2000 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
27 #include "hard-reg-set.h"
29 #include "insn-config.h"
31 #include "basic-block.h"
35 static int identify_call_return_value
PARAMS ((rtx
, rtx
*, rtx
*));
36 static rtx skip_copy_to_return_value
PARAMS ((rtx
, rtx
, rtx
));
37 static rtx skip_use_of_return_value
PARAMS ((rtx
, enum rtx_code
));
38 static rtx skip_stack_adjustment
PARAMS ((rtx
));
39 static rtx skip_pic_restore
PARAMS ((rtx
));
40 static rtx skip_jump_insn
PARAMS ((rtx
));
41 static int uses_addressof
PARAMS ((rtx
));
42 static int sequence_uses_addressof
PARAMS ((rtx
));
43 static void purge_reg_equiv_notes
PARAMS ((void));
45 /* Examine a CALL_PLACEHOLDER pattern and determine where the call's
46 return value is located. P_HARD_RETURN receives the hard register
47 that the function used; P_SOFT_RETURN receives the pseudo register
48 that the sequence used. Return non-zero if the values were located. */
51 identify_call_return_value (cp
, p_hard_return
, p_soft_return
)
53 rtx
*p_hard_return
, *p_soft_return
;
55 rtx insn
, set
, hard
, soft
;
58 /* Search backward through the "normal" call sequence to the CALL insn. */
59 while (NEXT_INSN (insn
))
60 insn
= NEXT_INSN (insn
);
61 while (GET_CODE (insn
) != CALL_INSN
)
62 insn
= PREV_INSN (insn
);
64 /* Assume the pattern is (set (dest) (call ...)), or that the first
65 member of a parallel is. This is the hard return register used
67 if (GET_CODE (PATTERN (insn
)) == SET
68 && GET_CODE (SET_SRC (PATTERN (insn
))) == CALL
)
69 hard
= SET_DEST (PATTERN (insn
));
70 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
71 && GET_CODE (XVECEXP (PATTERN (insn
), 0, 0)) == SET
72 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn
), 0, 0))) == CALL
)
73 hard
= SET_DEST (XVECEXP (PATTERN (insn
), 0, 0));
77 /* If we didn't get a single hard register (e.g. a parallel), give up. */
78 if (GET_CODE (hard
) != REG
)
81 /* Stack adjustment done after call may appear here. */
82 insn
= skip_stack_adjustment (insn
);
86 /* Restore of GP register may appear here. */
87 insn
= skip_pic_restore (insn
);
91 /* If there's nothing after, there's no soft return value. */
92 insn
= NEXT_INSN (insn
);
96 /* We're looking for a source of the hard return register. */
97 set
= single_set (insn
);
98 if (! set
|| SET_SRC (set
) != hard
)
101 soft
= SET_DEST (set
);
102 insn
= NEXT_INSN (insn
);
104 /* Allow this first destination to be copied to a second register,
105 as might happen if the first register wasn't the particular pseudo
106 we'd been expecting. */
108 && (set
= single_set (insn
)) != NULL_RTX
109 && SET_SRC (set
) == soft
)
111 soft
= SET_DEST (set
);
112 insn
= NEXT_INSN (insn
);
115 /* Don't fool with anything but pseudo registers. */
116 if (GET_CODE (soft
) != REG
|| REGNO (soft
) < FIRST_PSEUDO_REGISTER
)
119 /* This value must not be modified before the end of the sequence. */
120 if (reg_set_between_p (soft
, insn
, NULL_RTX
))
123 *p_hard_return
= hard
;
124 *p_soft_return
= soft
;
129 /* If the first real insn after ORIG_INSN copies to this function's
130 return value from RETVAL, then return the insn which performs the
131 copy. Otherwise return ORIG_INSN. */
134 skip_copy_to_return_value (orig_insn
, hardret
, softret
)
136 rtx hardret
, softret
;
138 rtx insn
, set
= NULL_RTX
;
140 insn
= next_nonnote_insn (orig_insn
);
144 set
= single_set (insn
);
148 /* The destination must be the same as the called function's return
149 value to ensure that any return value is put in the same place by the
150 current function and the function we're calling.
152 Further, the source must be the same as the pseudo into which the
153 called function's return value was copied. Otherwise we're returning
156 #ifndef OUTGOING_REGNO
157 #define OUTGOING_REGNO(N) (N)
160 if (SET_DEST (set
) == current_function_return_rtx
161 && REG_P (SET_DEST (set
))
162 && OUTGOING_REGNO (REGNO (SET_DEST (set
))) == REGNO (hardret
)
163 && SET_SRC (set
) == softret
)
166 /* It did not look like a copy of the return value, so return the
167 same insn we were passed. */
171 /* If the first real insn after ORIG_INSN is a CODE of this function's return
172 value, return insn. Otherwise return ORIG_INSN. */
175 skip_use_of_return_value (orig_insn
, code
)
181 insn
= next_nonnote_insn (orig_insn
);
184 && GET_CODE (insn
) == INSN
185 && GET_CODE (PATTERN (insn
)) == code
186 && (XEXP (PATTERN (insn
), 0) == current_function_return_rtx
187 || XEXP (PATTERN (insn
), 0) == const0_rtx
))
193 /* If the first real insn after ORIG_INSN adjusts the stack pointer
194 by a constant, return the insn with the stack pointer adjustment.
195 Otherwise return ORIG_INSN. */
198 skip_stack_adjustment (orig_insn
)
201 rtx insn
, set
= NULL_RTX
;
203 insn
= next_nonnote_insn (orig_insn
);
206 set
= single_set (insn
);
210 && GET_CODE (SET_SRC (set
)) == PLUS
211 && XEXP (SET_SRC (set
), 0) == stack_pointer_rtx
212 && GET_CODE (XEXP (SET_SRC (set
), 1)) == CONST_INT
213 && SET_DEST (set
) == stack_pointer_rtx
)
219 /* If the first real insn after ORIG_INSN sets the pic register,
220 return it. Otherwise return ORIG_INSN. */
223 skip_pic_restore (orig_insn
)
226 rtx insn
, set
= NULL_RTX
;
228 insn
= next_nonnote_insn (orig_insn
);
231 set
= single_set (insn
);
233 if (insn
&& set
&& SET_DEST (set
) == pic_offset_table_rtx
)
239 /* If the first real insn after ORIG_INSN is a jump, return the JUMP_INSN.
240 Otherwise return ORIG_INSN. */
243 skip_jump_insn (orig_insn
)
248 insn
= next_nonnote_insn (orig_insn
);
251 && GET_CODE (insn
) == JUMP_INSN
252 && any_uncondjump_p (insn
))
258 /* Scan the rtx X for ADDRESSOF expressions or
259 current_function_internal_arg_pointer registers.
260 Return nonzero if an ADDRESSOF or current_function_internal_arg_pointer
261 is found outside of some MEM expression, else return zero. */
276 if (code
== ADDRESSOF
|| x
== current_function_internal_arg_pointer
)
282 /* Scan all subexpressions. */
283 fmt
= GET_RTX_FORMAT (code
);
284 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++, fmt
++)
288 if (uses_addressof (XEXP (x
, i
)))
291 else if (*fmt
== 'E')
293 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
294 if (uses_addressof (XVECEXP (x
, i
, j
)))
301 /* Scan the sequence of insns in SEQ to see if any have an ADDRESSOF
302 rtl expression or current_function_internal_arg_pointer occurences
303 not enclosed within a MEM. If an ADDRESSOF expression or
304 current_function_internal_arg_pointer is found, return nonzero, otherwise
307 This function handles CALL_PLACEHOLDERs which contain multiple sequences
311 sequence_uses_addressof (seq
)
316 for (insn
= seq
; insn
; insn
= NEXT_INSN (insn
))
319 /* If this is a CALL_PLACEHOLDER, then recursively call ourselves
320 with each nonempty sequence attached to the CALL_PLACEHOLDER. */
321 if (GET_CODE (insn
) == CALL_INSN
322 && GET_CODE (PATTERN (insn
)) == CALL_PLACEHOLDER
)
324 if (XEXP (PATTERN (insn
), 0) != NULL_RTX
325 && sequence_uses_addressof (XEXP (PATTERN (insn
), 0)))
327 if (XEXP (PATTERN (insn
), 1) != NULL_RTX
328 && sequence_uses_addressof (XEXP (PATTERN (insn
), 1)))
330 if (XEXP (PATTERN (insn
), 2) != NULL_RTX
331 && sequence_uses_addressof (XEXP (PATTERN (insn
), 2)))
334 else if (uses_addressof (PATTERN (insn
))
335 || (REG_NOTES (insn
) && uses_addressof (REG_NOTES (insn
))))
341 /* Remove all REG_EQUIV notes found in the insn chain. */
344 purge_reg_equiv_notes ()
348 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
352 rtx note
= find_reg_note (insn
, REG_EQUIV
, 0);
355 /* Remove the note and keep looking at the notes for
357 remove_note (insn
, note
);
365 /* Replace the CALL_PLACEHOLDER with one of its children. INSN should be
366 the CALL_PLACEHOLDER insn; USE tells which child to use. */
369 replace_call_placeholder (insn
, use
)
373 if (use
== sibcall_use_tail_recursion
)
374 emit_insns_before (XEXP (PATTERN (insn
), 2), insn
);
375 else if (use
== sibcall_use_sibcall
)
376 emit_insns_before (XEXP (PATTERN (insn
), 1), insn
);
377 else if (use
== sibcall_use_normal
)
378 emit_insns_before (XEXP (PATTERN (insn
), 0), insn
);
382 /* Turn off LABEL_PRESERVE_P for the tail recursion label if it
383 exists. We only had to set it long enough to keep the jump
384 pass above from deleting it as unused. */
385 if (XEXP (PATTERN (insn
), 3))
386 LABEL_PRESERVE_P (XEXP (PATTERN (insn
), 3)) = 0;
388 /* "Delete" the placeholder insn. */
389 PUT_CODE (insn
, NOTE
);
390 NOTE_SOURCE_FILE (insn
) = 0;
391 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
394 /* Given a (possibly empty) set of potential sibling or tail recursion call
395 sites, determine if optimization is possible.
397 Potential sibling or tail recursion calls are marked with CALL_PLACEHOLDER
398 insns. The CALL_PLACEHOLDER insn holds chains of insns to implement a
399 normal call, sibling call or tail recursive call.
401 Replace the CALL_PLACEHOLDER with an appropriate insn chain. */
404 optimize_sibling_and_tail_recursive_calls ()
407 basic_block alternate_exit
= EXIT_BLOCK_PTR
;
408 int current_function_uses_addressof
;
409 int successful_sibling_call
= 0;
410 int replaced_call_placeholder
= 0;
413 insns
= get_insns ();
415 /* We do not perform these calls when flag_exceptions is true, so this
416 is probably a NOP at the current time. However, we may want to support
417 sibling and tail recursion optimizations in the future, so let's plan
418 ahead and find all the EH labels. */
419 find_exception_handler_labels ();
421 /* Run a jump optimization pass to clean up the CFG. We primarily want
422 this to thread jumps so that it is obvious which blocks jump to the
424 jump_optimize_minimal (insns
);
426 /* We need cfg information to determine which blocks are succeeded
427 only by the epilogue. */
428 find_basic_blocks (insns
, max_reg_num (), 0);
431 /* If there are no basic blocks, then there is nothing to do. */
432 if (n_basic_blocks
== 0)
435 /* Find the exit block.
437 It is possible that we have blocks which can reach the exit block
438 directly. However, most of the time a block will jump (or fall into)
439 N_BASIC_BLOCKS - 1, which in turn falls into the exit block. */
440 for (e
= EXIT_BLOCK_PTR
->pred
;
441 e
&& alternate_exit
== EXIT_BLOCK_PTR
;
446 if (e
->dest
!= EXIT_BLOCK_PTR
|| e
->succ_next
!= NULL
)
449 /* Walk forwards through the last normal block and see if it
450 does nothing except fall into the exit block. */
451 for (insn
= BLOCK_HEAD (n_basic_blocks
- 1);
453 insn
= NEXT_INSN (insn
))
455 /* This should only happen once, at the start of this block. */
456 if (GET_CODE (insn
) == CODE_LABEL
)
459 if (GET_CODE (insn
) == NOTE
)
462 if (GET_CODE (insn
) == INSN
463 && GET_CODE (PATTERN (insn
)) == USE
)
469 /* If INSN is zero, then the search walked all the way through the
470 block without hitting anything interesting. This block is a
471 valid alternate exit block. */
473 alternate_exit
= e
->src
;
476 /* If the function uses ADDRESSOF, we can't (easily) determine
477 at this point if the value will end up on the stack. */
478 current_function_uses_addressof
= sequence_uses_addressof (insns
);
480 /* Walk the insn chain and find any CALL_PLACEHOLDER insns. We need to
481 select one of the insn sequences attached to each CALL_PLACEHOLDER.
483 The different sequences represent different ways to implement the call,
484 ie, tail recursion, sibling call or normal call.
486 Since we do not create nested CALL_PLACEHOLDERs, the scan
487 continues with the insn that was after a replaced CALL_PLACEHOLDER;
488 we don't rescan the replacement insns. */
489 for (insn
= insns
; insn
; insn
= NEXT_INSN (insn
))
491 if (GET_CODE (insn
) == CALL_INSN
492 && GET_CODE (PATTERN (insn
)) == CALL_PLACEHOLDER
)
494 int sibcall
= (XEXP (PATTERN (insn
), 1) != NULL_RTX
);
495 int tailrecursion
= (XEXP (PATTERN (insn
), 2) != NULL_RTX
);
496 basic_block succ_block
, call_block
;
497 rtx temp
, hardret
, softret
;
499 /* We must be careful with stack slots which are live at
500 potential optimization sites.
502 ?!? This test is overly conservative and will be replaced. */
506 /* Taking the address of a local variable is fatal to tail
507 recursion if the address is used by the recursive call. */
508 if (current_function_uses_addressof
)
511 /* alloca (until we have stack slot life analysis) inhibits
512 sibling call optimizations, but not tail recursion.
513 Similarly if we use varargs or stdarg since they implicitly
514 may take the address of an argument. */
515 if (current_function_calls_alloca
516 || current_function_varargs
|| current_function_stdarg
)
519 call_block
= BLOCK_FOR_INSN (insn
);
521 /* If the block has more than one successor, then we can not
522 perform sibcall or tail recursion optimizations. */
523 if (call_block
->succ
== NULL
524 || call_block
->succ
->succ_next
!= NULL
)
527 /* If the single successor is not the exit block, then we can not
528 perform sibcall or tail recursion optimizations.
530 Note that this test combined with the previous is sufficient
531 to prevent tail call optimization in the presense of active
532 exception handlers. */
533 succ_block
= call_block
->succ
->dest
;
534 if (succ_block
!= EXIT_BLOCK_PTR
&& succ_block
!= alternate_exit
)
537 /* If the call was the end of the block, then we're OK. */
539 if (temp
== call_block
->end
)
542 /* Skip over copying from the call's return value pseudo into
543 this function's hard return register. */
544 if (identify_call_return_value (PATTERN (insn
), &hardret
, &softret
))
546 temp
= skip_copy_to_return_value (temp
, hardret
, softret
);
547 if (temp
== call_block
->end
)
551 /* Skip any stack adjustment. */
552 temp
= skip_stack_adjustment (temp
);
553 if (temp
== call_block
->end
)
556 /* Skip over a CLOBBER of the return value (as a hard reg). */
557 temp
= skip_use_of_return_value (temp
, CLOBBER
);
558 if (temp
== call_block
->end
)
561 /* Skip over a USE of the return value (as a hard reg). */
562 temp
= skip_use_of_return_value (temp
, USE
);
563 if (temp
== call_block
->end
)
566 /* Skip over the JUMP_INSN at the end of the block. */
567 temp
= skip_jump_insn (temp
);
568 if (GET_CODE (temp
) == NOTE
)
569 temp
= next_nonnote_insn (temp
);
570 if (temp
== call_block
->end
)
573 /* There are operations at the end of the block which we must
574 execute after returning from the function call. So this call
575 can not be optimized. */
577 sibcall
= 0, tailrecursion
= 0;
580 /* Select a set of insns to implement the call and emit them.
581 Tail recursion is the most efficient, so select it over
582 a tail/sibling call. */
585 successful_sibling_call
= 1;
586 replaced_call_placeholder
= 1;
587 replace_call_placeholder (insn
,
589 ? sibcall_use_tail_recursion
591 ? sibcall_use_sibcall
592 : sibcall_use_normal
);
596 /* A sibling call sequence invalidates any REG_EQUIV notes made for
597 this function's incoming arguments.
599 At the start of RTL generation we know the only REG_EQUIV notes
600 in the rtl chain are those for incoming arguments, so we can safely
601 flush any REG_EQUIV note.
603 This is (slight) overkill. We could keep track of the highest argument
604 we clobber and be more selective in removing notes, but it does not
605 seem to be worth the effort. */
606 if (successful_sibling_call
)
607 purge_reg_equiv_notes ();
609 /* There may have been NOTE_INSN_BLOCK_{BEGIN,END} notes in the
610 CALL_PLACEHOLDER alternatives that we didn't emit. Rebuild the
611 lexical block tree to correspond to the notes that still exist. */
612 if (replaced_call_placeholder
)
615 /* This information will be invalid after inline expansion. Kill it now. */
616 free_basic_block_vars (0);