1 /* Generic sibling call optimization support
2 Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
27 #include "hard-reg-set.h"
29 #include "insn-config.h"
31 #include "basic-block.h"
36 /* In case alternate_exit_block contains copy from pseudo, to return value,
37 record the pseudo here. In such case the pseudo must be set to function
38 return in the sibcall sequence. */
39 static rtx return_value_pseudo
;
41 static int identify_call_return_value
PARAMS ((rtx
, rtx
*, rtx
*));
42 static rtx skip_copy_to_return_value
PARAMS ((rtx
));
43 static rtx skip_use_of_return_value
PARAMS ((rtx
, enum rtx_code
));
44 static rtx skip_stack_adjustment
PARAMS ((rtx
));
45 static rtx skip_pic_restore
PARAMS ((rtx
));
46 static rtx skip_jump_insn
PARAMS ((rtx
));
47 static int call_ends_block_p
PARAMS ((rtx
, rtx
));
48 static int uses_addressof
PARAMS ((rtx
));
49 static int sequence_uses_addressof
PARAMS ((rtx
));
50 static void purge_reg_equiv_notes
PARAMS ((void));
51 static void purge_mem_unchanging_flag
PARAMS ((rtx
));
52 static rtx skip_unreturned_value
PARAMS ((rtx
));
54 /* Examine a CALL_PLACEHOLDER pattern and determine where the call's
55 return value is located. P_HARD_RETURN receives the hard register
56 that the function used; P_SOFT_RETURN receives the pseudo register
57 that the sequence used. Return non-zero if the values were located. */
60 identify_call_return_value (cp
, p_hard_return
, p_soft_return
)
62 rtx
*p_hard_return
, *p_soft_return
;
64 rtx insn
, set
, hard
, soft
;
67 /* Search backward through the "normal" call sequence to the CALL insn. */
68 while (NEXT_INSN (insn
))
69 insn
= NEXT_INSN (insn
);
70 while (GET_CODE (insn
) != CALL_INSN
)
71 insn
= PREV_INSN (insn
);
73 /* Assume the pattern is (set (dest) (call ...)), or that the first
74 member of a parallel is. This is the hard return register used
76 if (GET_CODE (PATTERN (insn
)) == SET
77 && GET_CODE (SET_SRC (PATTERN (insn
))) == CALL
)
78 hard
= SET_DEST (PATTERN (insn
));
79 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
80 && GET_CODE (XVECEXP (PATTERN (insn
), 0, 0)) == SET
81 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn
), 0, 0))) == CALL
)
82 hard
= SET_DEST (XVECEXP (PATTERN (insn
), 0, 0));
86 /* If we didn't get a single hard register (e.g. a parallel), give up. */
87 if (GET_CODE (hard
) != REG
)
90 /* Stack adjustment done after call may appear here. */
91 insn
= skip_stack_adjustment (insn
);
95 /* Restore of GP register may appear here. */
96 insn
= skip_pic_restore (insn
);
100 /* If there's nothing after, there's no soft return value. */
101 insn
= NEXT_INSN (insn
);
105 /* We're looking for a source of the hard return register. */
106 set
= single_set (insn
);
107 if (! set
|| SET_SRC (set
) != hard
)
110 soft
= SET_DEST (set
);
111 insn
= NEXT_INSN (insn
);
113 /* Allow this first destination to be copied to a second register,
114 as might happen if the first register wasn't the particular pseudo
115 we'd been expecting. */
117 && (set
= single_set (insn
)) != NULL_RTX
118 && SET_SRC (set
) == soft
)
120 soft
= SET_DEST (set
);
121 insn
= NEXT_INSN (insn
);
124 /* Don't fool with anything but pseudo registers. */
125 if (GET_CODE (soft
) != REG
|| REGNO (soft
) < FIRST_PSEUDO_REGISTER
)
128 /* This value must not be modified before the end of the sequence. */
129 if (reg_set_between_p (soft
, insn
, NULL_RTX
))
132 *p_hard_return
= hard
;
133 *p_soft_return
= soft
;
138 /* If the first real insn after ORIG_INSN copies to this function's
139 return value from RETVAL, then return the insn which performs the
140 copy. Otherwise return ORIG_INSN. */
143 skip_copy_to_return_value (orig_insn
)
146 rtx insn
, set
= NULL_RTX
;
147 rtx hardret
, softret
;
149 /* If there is no return value, we have nothing to do. */
150 if (! identify_call_return_value (PATTERN (orig_insn
), &hardret
, &softret
))
153 insn
= next_nonnote_insn (orig_insn
);
157 set
= single_set (insn
);
161 if (return_value_pseudo
)
163 if (SET_DEST (set
) == return_value_pseudo
164 && SET_SRC (set
) == softret
)
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
171 current function and the function we're calling.
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
177 #ifndef OUTGOING_REGNO
178 #define OUTGOING_REGNO(N) (N)
181 if (SET_DEST (set
) == current_function_return_rtx
182 && REG_P (SET_DEST (set
))
183 && OUTGOING_REGNO (REGNO (SET_DEST (set
))) == REGNO (hardret
)
184 && SET_SRC (set
) == softret
)
187 /* Recognize the situation when the called function's return value
188 is copied in two steps: first into an intermediate pseudo, then
189 the into the calling functions return value register. */
191 if (REG_P (SET_DEST (set
))
192 && SET_SRC (set
) == softret
)
194 rtx x
= SET_DEST (set
);
196 insn
= next_nonnote_insn (insn
);
200 set
= single_set (insn
);
204 if (SET_DEST (set
) == current_function_return_rtx
205 && REG_P (SET_DEST (set
))
206 && OUTGOING_REGNO (REGNO (SET_DEST (set
))) == REGNO (hardret
)
207 && SET_SRC (set
) == x
)
211 /* It did not look like a copy of the return value, so return the
212 same insn we were passed. */
216 /* If the first real insn after ORIG_INSN is a CODE of this function's return
217 value, return insn. Otherwise return ORIG_INSN. */
220 skip_use_of_return_value (orig_insn
, code
)
226 insn
= next_nonnote_insn (orig_insn
);
229 && GET_CODE (insn
) == INSN
230 && GET_CODE (PATTERN (insn
)) == code
231 && (XEXP (PATTERN (insn
), 0) == current_function_return_rtx
232 || XEXP (PATTERN (insn
), 0) == const0_rtx
))
238 /* In case function does not return value, we get clobber of pseudo followed
239 by set to hard return value. */
241 skip_unreturned_value (orig_insn
)
244 rtx insn
= next_nonnote_insn (orig_insn
);
246 /* Skip possible clobber of pseudo return register. */
248 && GET_CODE (insn
) == INSN
249 && GET_CODE (PATTERN (insn
)) == CLOBBER
250 && REG_P (XEXP (PATTERN (insn
), 0))
251 && (REGNO (XEXP (PATTERN (insn
), 0)) >= FIRST_PSEUDO_REGISTER
))
253 rtx set_insn
= next_nonnote_insn (insn
);
257 set
= single_set (set_insn
);
259 || SET_SRC (set
) != XEXP (PATTERN (insn
), 0)
260 || SET_DEST (set
) != current_function_return_rtx
)
267 /* If the first real insn after ORIG_INSN adjusts the stack pointer
268 by a constant, return the insn with the stack pointer adjustment.
269 Otherwise return ORIG_INSN. */
272 skip_stack_adjustment (orig_insn
)
275 rtx insn
, set
= NULL_RTX
;
277 insn
= next_nonnote_insn (orig_insn
);
280 set
= single_set (insn
);
284 && GET_CODE (SET_SRC (set
)) == PLUS
285 && XEXP (SET_SRC (set
), 0) == stack_pointer_rtx
286 && GET_CODE (XEXP (SET_SRC (set
), 1)) == CONST_INT
287 && SET_DEST (set
) == stack_pointer_rtx
)
293 /* If the first real insn after ORIG_INSN sets the pic register,
294 return it. Otherwise return ORIG_INSN. */
297 skip_pic_restore (orig_insn
)
300 rtx insn
, set
= NULL_RTX
;
302 insn
= next_nonnote_insn (orig_insn
);
305 set
= single_set (insn
);
307 if (insn
&& set
&& SET_DEST (set
) == pic_offset_table_rtx
)
313 /* If the first real insn after ORIG_INSN is a jump, return the JUMP_INSN.
314 Otherwise return ORIG_INSN. */
317 skip_jump_insn (orig_insn
)
322 insn
= next_nonnote_insn (orig_insn
);
325 && GET_CODE (insn
) == JUMP_INSN
326 && any_uncondjump_p (insn
))
332 /* Using the above functions, see if INSN, skipping any of the above,
333 goes all the way to END, the end of a basic block. Return 1 if so. */
336 call_ends_block_p (insn
, end
)
341 /* END might be a note, so get the last nonnote insn of the block. */
342 end
= next_nonnote_insn (PREV_INSN (end
));
344 /* If the call was the end of the block, then we're OK. */
348 /* Skip over copying from the call's return value pseudo into
349 this function's hard return register and if that's the end
350 of the block, we're OK. */
351 new_insn
= skip_copy_to_return_value (insn
);
353 /* In case we return value in pseudo, we must set the pseudo to
354 return value of called function, otherwise we are returning
356 if (return_value_pseudo
&& insn
== new_insn
)
363 /* Skip any stack adjustment. */
364 insn
= skip_stack_adjustment (insn
);
368 /* Skip over a CLOBBER of the return value as a hard reg. */
369 insn
= skip_use_of_return_value (insn
, CLOBBER
);
373 /* Skip over a CLOBBER of the return value as a hard reg. */
374 insn
= skip_unreturned_value (insn
);
378 /* Skip over a USE of the return value (as a hard reg). */
379 insn
= skip_use_of_return_value (insn
, USE
);
383 /* Skip over a JUMP_INSN at the end of the block. If that doesn't end the
384 block, the original CALL_INSN didn't. */
385 insn
= skip_jump_insn (insn
);
389 /* Scan the rtx X for ADDRESSOF expressions or
390 current_function_internal_arg_pointer registers.
391 Return nonzero if an ADDRESSOF or current_function_internal_arg_pointer
392 is found outside of some MEM expression, else return zero. */
407 if (code
== ADDRESSOF
|| x
== current_function_internal_arg_pointer
)
413 /* Scan all subexpressions. */
414 fmt
= GET_RTX_FORMAT (code
);
415 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++, fmt
++)
419 if (uses_addressof (XEXP (x
, i
)))
422 else if (*fmt
== 'E')
424 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
425 if (uses_addressof (XVECEXP (x
, i
, j
)))
432 /* Scan the sequence of insns in SEQ to see if any have an ADDRESSOF
433 rtl expression or current_function_internal_arg_pointer occurrences
434 not enclosed within a MEM. If an ADDRESSOF expression or
435 current_function_internal_arg_pointer is found, return nonzero, otherwise
438 This function handles CALL_PLACEHOLDERs which contain multiple sequences
442 sequence_uses_addressof (seq
)
447 for (insn
= seq
; insn
; insn
= NEXT_INSN (insn
))
450 /* If this is a CALL_PLACEHOLDER, then recursively call ourselves
451 with each nonempty sequence attached to the CALL_PLACEHOLDER. */
452 if (GET_CODE (insn
) == CALL_INSN
453 && GET_CODE (PATTERN (insn
)) == CALL_PLACEHOLDER
)
455 if (XEXP (PATTERN (insn
), 0) != NULL_RTX
456 && sequence_uses_addressof (XEXP (PATTERN (insn
), 0)))
458 if (XEXP (PATTERN (insn
), 1) != NULL_RTX
459 && sequence_uses_addressof (XEXP (PATTERN (insn
), 1)))
461 if (XEXP (PATTERN (insn
), 2) != NULL_RTX
462 && sequence_uses_addressof (XEXP (PATTERN (insn
), 2)))
465 else if (uses_addressof (PATTERN (insn
))
466 || (REG_NOTES (insn
) && uses_addressof (REG_NOTES (insn
))))
472 /* Remove all REG_EQUIV notes found in the insn chain. */
475 purge_reg_equiv_notes ()
479 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
483 rtx note
= find_reg_note (insn
, REG_EQUIV
, 0);
486 /* Remove the note and keep looking at the notes for
488 remove_note (insn
, note
);
496 /* Clear RTX_UNCHANGING_P flag of incoming argument MEMs. */
499 purge_mem_unchanging_flag (x
)
513 if (RTX_UNCHANGING_P (x
)
514 && (XEXP (x
, 0) == current_function_internal_arg_pointer
515 || (GET_CODE (XEXP (x
, 0)) == PLUS
516 && XEXP (XEXP (x
, 0), 0) ==
517 current_function_internal_arg_pointer
518 && GET_CODE (XEXP (XEXP (x
, 0), 1)) == CONST_INT
)))
519 RTX_UNCHANGING_P (x
) = 0;
523 /* Scan all subexpressions. */
524 fmt
= GET_RTX_FORMAT (code
);
525 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++, fmt
++)
528 purge_mem_unchanging_flag (XEXP (x
, i
));
529 else if (*fmt
== 'E')
530 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
531 purge_mem_unchanging_flag (XVECEXP (x
, i
, j
));
535 /* Replace the CALL_PLACEHOLDER with one of its children. INSN should be
536 the CALL_PLACEHOLDER insn; USE tells which child to use. */
539 replace_call_placeholder (insn
, use
)
543 if (use
== sibcall_use_tail_recursion
)
544 emit_insns_before (XEXP (PATTERN (insn
), 2), insn
);
545 else if (use
== sibcall_use_sibcall
)
546 emit_insns_before (XEXP (PATTERN (insn
), 1), insn
);
547 else if (use
== sibcall_use_normal
)
548 emit_insns_before (XEXP (PATTERN (insn
), 0), insn
);
552 /* Turn off LABEL_PRESERVE_P for the tail recursion label if it
553 exists. We only had to set it long enough to keep the jump
554 pass above from deleting it as unused. */
555 if (XEXP (PATTERN (insn
), 3))
556 LABEL_PRESERVE_P (XEXP (PATTERN (insn
), 3)) = 0;
558 /* "Delete" the placeholder insn. */
562 /* Given a (possibly empty) set of potential sibling or tail recursion call
563 sites, determine if optimization is possible.
565 Potential sibling or tail recursion calls are marked with CALL_PLACEHOLDER
566 insns. The CALL_PLACEHOLDER insn holds chains of insns to implement a
567 normal call, sibling call or tail recursive call.
569 Replace the CALL_PLACEHOLDER with an appropriate insn chain. */
572 optimize_sibling_and_tail_recursive_calls ()
575 basic_block alternate_exit
= EXIT_BLOCK_PTR
;
576 bool no_sibcalls_this_function
= false;
577 int successful_sibling_call
= 0;
578 int replaced_call_placeholder
= 0;
581 insns
= get_insns ();
583 /* We do not perform these calls when flag_exceptions is true, so this
584 is probably a NOP at the current time. However, we may want to support
585 sibling and tail recursion optimizations in the future, so let's plan
586 ahead and find all the EH labels. */
587 find_exception_handler_labels ();
589 rebuild_jump_labels (insns
);
590 /* We need cfg information to determine which blocks are succeeded
591 only by the epilogue. */
592 find_basic_blocks (insns
, max_reg_num (), 0);
593 cleanup_cfg (CLEANUP_PRE_SIBCALL
| CLEANUP_PRE_LOOP
);
595 /* If there are no basic blocks, then there is nothing to do. */
596 if (n_basic_blocks
== 0)
599 /* If we are using sjlj exceptions, we may need to add a call to
600 _Unwind_SjLj_Unregister at exit of the function. Which means
601 that we cannot do any sibcall transformations. */
602 if (USING_SJLJ_EXCEPTIONS
&& current_function_has_exception_handlers ())
603 no_sibcalls_this_function
= true;
605 return_value_pseudo
= NULL_RTX
;
607 /* Find the exit block.
609 It is possible that we have blocks which can reach the exit block
610 directly. However, most of the time a block will jump (or fall into)
611 N_BASIC_BLOCKS - 1, which in turn falls into the exit block. */
612 for (e
= EXIT_BLOCK_PTR
->pred
;
613 e
&& alternate_exit
== EXIT_BLOCK_PTR
;
618 if (e
->dest
!= EXIT_BLOCK_PTR
|| e
->succ_next
!= NULL
)
621 /* Walk forwards through the last normal block and see if it
622 does nothing except fall into the exit block. */
623 for (insn
= BLOCK_HEAD (n_basic_blocks
- 1);
625 insn
= NEXT_INSN (insn
))
628 /* This should only happen once, at the start of this block. */
629 if (GET_CODE (insn
) == CODE_LABEL
)
632 if (GET_CODE (insn
) == NOTE
)
635 if (GET_CODE (insn
) == INSN
636 && GET_CODE (PATTERN (insn
)) == USE
)
639 /* Exit block also may contain copy from pseudo containing
640 return value to hard register. */
641 if (GET_CODE (insn
) == INSN
642 && (set
= single_set (insn
))
643 && SET_DEST (set
) == current_function_return_rtx
644 && REG_P (SET_SRC (set
))
645 && !return_value_pseudo
)
647 return_value_pseudo
= SET_SRC (set
);
654 /* If INSN is zero, then the search walked all the way through the
655 block without hitting anything interesting. This block is a
656 valid alternate exit block. */
658 alternate_exit
= e
->src
;
660 return_value_pseudo
= NULL
;
663 /* If the function uses ADDRESSOF, we can't (easily) determine
664 at this point if the value will end up on the stack. */
665 no_sibcalls_this_function
|= sequence_uses_addressof (insns
);
667 /* Walk the insn chain and find any CALL_PLACEHOLDER insns. We need to
668 select one of the insn sequences attached to each CALL_PLACEHOLDER.
670 The different sequences represent different ways to implement the call,
671 ie, tail recursion, sibling call or normal call.
673 Since we do not create nested CALL_PLACEHOLDERs, the scan
674 continues with the insn that was after a replaced CALL_PLACEHOLDER;
675 we don't rescan the replacement insns. */
676 for (insn
= insns
; insn
; insn
= NEXT_INSN (insn
))
678 if (GET_CODE (insn
) == CALL_INSN
679 && GET_CODE (PATTERN (insn
)) == CALL_PLACEHOLDER
)
681 int sibcall
= (XEXP (PATTERN (insn
), 1) != NULL_RTX
);
682 int tailrecursion
= (XEXP (PATTERN (insn
), 2) != NULL_RTX
);
683 basic_block call_block
= BLOCK_FOR_INSN (insn
);
685 /* alloca (until we have stack slot life analysis) inhibits
686 sibling call optimizations, but not tail recursion.
687 Similarly if we use varargs or stdarg since they implicitly
688 may take the address of an argument. */
689 if (current_function_calls_alloca
690 || current_function_varargs
|| current_function_stdarg
)
693 /* See if there are any reasons we can't perform either sibling or
694 tail call optimizations. We must be careful with stack slots
695 which are live at potential optimization sites. */
696 if (no_sibcalls_this_function
697 /* ??? Overly conservative. */
699 /* Any function that calls setjmp might have longjmp called from
700 any called function. ??? We really should represent this
701 properly in the CFG so that this needn't be special cased. */
702 || current_function_calls_setjmp
703 /* Can't if more than one successor or single successor is not
704 exit block. These two tests prevent tail call optimization
705 in the presense of active exception handlers. */
706 || call_block
->succ
== NULL
707 || call_block
->succ
->succ_next
!= NULL
708 || (call_block
->succ
->dest
!= EXIT_BLOCK_PTR
709 && call_block
->succ
->dest
!= alternate_exit
)
710 /* If this call doesn't end the block, there are operations at
711 the end of the block which we must execute after returning. */
712 || ! call_ends_block_p (insn
, call_block
->end
))
713 sibcall
= 0, tailrecursion
= 0;
715 /* Select a set of insns to implement the call and emit them.
716 Tail recursion is the most efficient, so select it over
717 a tail/sibling call. */
719 successful_sibling_call
= 1;
721 replaced_call_placeholder
= 1;
722 replace_call_placeholder (insn
,
724 ? sibcall_use_tail_recursion
726 ? sibcall_use_sibcall
727 : sibcall_use_normal
);
731 if (successful_sibling_call
)
736 /* A sibling call sequence invalidates any REG_EQUIV notes made for
737 this function's incoming arguments.
739 At the start of RTL generation we know the only REG_EQUIV notes
740 in the rtl chain are those for incoming arguments, so we can safely
741 flush any REG_EQUIV note.
743 This is (slight) overkill. We could keep track of the highest
744 argument we clobber and be more selective in removing notes, but it
745 does not seem to be worth the effort. */
746 purge_reg_equiv_notes ();
748 /* A sibling call sequence also may invalidate RTX_UNCHANGING_P
749 flag of some incoming arguments MEM RTLs, because it can write into
750 those slots. We clear all those bits now.
752 This is (slight) overkill, we could keep track of which arguments
753 we actually write into. */
754 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
757 purge_mem_unchanging_flag (PATTERN (insn
));
760 /* Similarly, invalidate RTX_UNCHANGING_P for any incoming
761 arguments passed in registers. */
762 for (arg
= DECL_ARGUMENTS (current_function_decl
);
764 arg
= TREE_CHAIN (arg
))
766 if (REG_P (DECL_RTL (arg
)))
767 RTX_UNCHANGING_P (DECL_RTL (arg
)) = false;
771 /* There may have been NOTE_INSN_BLOCK_{BEGIN,END} notes in the
772 CALL_PLACEHOLDER alternatives that we didn't emit. Rebuild the
773 lexical block tree to correspond to the notes that still exist. */
774 if (replaced_call_placeholder
)
777 /* This information will be invalid after inline expansion. Kill it now. */
778 free_basic_block_vars (0);