1 /* Generic sibling call optimization support
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004
3 Free Software Foundation, Inc.
5 This file is part of GCC.
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
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
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 #include "coretypes.h"
30 #include "hard-reg-set.h"
32 #include "insn-config.h"
34 #include "basic-block.h"
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
;
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
);
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
60 that the sequence used. Return nonzero if the values were located. */
63 identify_call_return_value (rtx cp
, rtx
*p_hard_return
, rtx
*p_soft_return
)
65 rtx insn
, set
, hard
, soft
;
68 /* Search backward through the "normal" call sequence to the CALL insn. */
69 while (NEXT_INSN (insn
))
70 insn
= NEXT_INSN (insn
);
71 while (GET_CODE (insn
) != CALL_INSN
)
72 insn
= PREV_INSN (insn
);
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
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));
87 /* If we didn't get a single hard register (e.g. a parallel), give up. */
88 if (GET_CODE (hard
) != REG
)
91 /* Stack adjustment done after call may appear here. */
92 insn
= skip_stack_adjustment (insn
);
96 /* Restore of GP register may appear here. */
97 insn
= skip_pic_restore (insn
);
101 /* If there's nothing after, there's no soft return value. */
102 insn
= NEXT_INSN (insn
);
106 /* We're looking for a source of the hard return register. */
107 set
= single_set (insn
);
108 if (! set
|| SET_SRC (set
) != hard
)
111 soft
= SET_DEST (set
);
112 insn
= NEXT_INSN (insn
);
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. */
118 && (set
= single_set (insn
)) != NULL_RTX
119 && SET_SRC (set
) == soft
)
121 soft
= SET_DEST (set
);
122 insn
= NEXT_INSN (insn
);
125 /* Don't fool with anything but pseudo registers. */
126 if (GET_CODE (soft
) != REG
|| REGNO (soft
) < FIRST_PSEUDO_REGISTER
)
129 /* This value must not be modified before the end of the sequence. */
130 if (reg_set_between_p (soft
, insn
, NULL_RTX
))
133 *p_hard_return
= hard
;
134 *p_soft_return
= soft
;
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. */
144 skip_copy_to_return_value (rtx 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 if (SET_DEST (set
) == current_function_return_rtx
178 && REG_P (SET_DEST (set
))
179 && OUTGOING_REGNO (REGNO (SET_DEST (set
))) == REGNO (hardret
)
180 && SET_SRC (set
) == softret
)
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. */
187 if (REG_P (SET_DEST (set
))
188 && SET_SRC (set
) == softret
)
190 rtx x
= SET_DEST (set
);
192 insn
= next_nonnote_insn (insn
);
196 set
= single_set (insn
);
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
)
207 /* It did not look like a copy of the return value, so return the
208 same insn we were passed. */
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. */
216 skip_use_of_return_value (rtx orig_insn
, enum rtx_code code
)
220 insn
= next_nonnote_insn (orig_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
))
232 /* In case function does not return value, we get clobber of pseudo followed
233 by set to hard return value. */
235 skip_unreturned_value (rtx orig_insn
)
237 rtx insn
= next_nonnote_insn (orig_insn
);
239 /* Skip possible clobber of pseudo return register. */
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
))
246 rtx set_insn
= next_nonnote_insn (insn
);
250 set
= single_set (set_insn
);
252 || SET_SRC (set
) != XEXP (PATTERN (insn
), 0)
253 || SET_DEST (set
) != current_function_return_rtx
)
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. */
265 skip_stack_adjustment (rtx orig_insn
)
267 rtx insn
, set
= NULL_RTX
;
269 insn
= next_nonnote_insn (orig_insn
);
272 set
= single_set (insn
);
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
)
285 /* If the first real insn after ORIG_INSN sets the pic register,
286 return it. Otherwise return ORIG_INSN. */
289 skip_pic_restore (rtx orig_insn
)
291 rtx insn
, set
= NULL_RTX
;
293 insn
= next_nonnote_insn (orig_insn
);
296 set
= single_set (insn
);
298 if (insn
&& set
&& SET_DEST (set
) == pic_offset_table_rtx
)
304 /* If the first real insn after ORIG_INSN is a jump, return the JUMP_INSN.
305 Otherwise return ORIG_INSN. */
308 skip_jump_insn (rtx orig_insn
)
312 insn
= next_nonnote_insn (orig_insn
);
315 && GET_CODE (insn
) == JUMP_INSN
316 && any_uncondjump_p (insn
))
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. */
326 call_ends_block_p (rtx insn
, rtx end
)
329 /* END might be a note, so get the last nonnote insn of the block. */
330 end
= next_nonnote_insn (PREV_INSN (end
));
332 /* If the call was the end of the block, then we're OK. */
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. */
339 new_insn
= skip_copy_to_return_value (insn
);
341 /* In case we return value in pseudo, we must set the pseudo to
342 return value of called function, otherwise we are returning
344 if (return_value_pseudo
&& insn
== new_insn
)
351 /* Skip any stack adjustment. */
352 insn
= skip_stack_adjustment (insn
);
356 /* Skip over a CLOBBER of the return value as a hard reg. */
357 insn
= skip_use_of_return_value (insn
, CLOBBER
);
361 /* Skip over a CLOBBER of the return value as a hard reg. */
362 insn
= skip_unreturned_value (insn
);
366 /* Skip over a USE of the return value (as a hard reg). */
367 insn
= skip_use_of_return_value (insn
, USE
);
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
);
377 /* Scan the rtx X for ADDRESSOF expressions or
378 current_function_internal_arg_pointer registers.
379 Return nonzero if an ADDRESSOF or current_function_internal_arg_pointer
380 is found outside of some MEM expression, else return zero. */
383 uses_addressof (rtx x
)
394 if (code
== ADDRESSOF
|| x
== current_function_internal_arg_pointer
)
400 /* Scan all subexpressions. */
401 fmt
= GET_RTX_FORMAT (code
);
402 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++, fmt
++)
406 if (uses_addressof (XEXP (x
, i
)))
409 else if (*fmt
== 'E')
411 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
412 if (uses_addressof (XVECEXP (x
, i
, j
)))
419 /* Scan the sequence of insns in SEQ to see if any have an ADDRESSOF
420 rtl expression or current_function_internal_arg_pointer occurrences
421 not enclosed within a MEM. If an ADDRESSOF expression or
422 current_function_internal_arg_pointer is found, return nonzero, otherwise
425 This function handles CALL_PLACEHOLDERs which contain multiple sequences
429 sequence_uses_addressof (rtx seq
)
433 for (insn
= seq
; insn
; insn
= NEXT_INSN (insn
))
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
)
441 if (XEXP (PATTERN (insn
), 0) != NULL_RTX
442 && sequence_uses_addressof (XEXP (PATTERN (insn
), 0)))
444 if (XEXP (PATTERN (insn
), 1) != NULL_RTX
445 && sequence_uses_addressof (XEXP (PATTERN (insn
), 1)))
447 if (XEXP (PATTERN (insn
), 2) != NULL_RTX
448 && sequence_uses_addressof (XEXP (PATTERN (insn
), 2)))
451 else if (uses_addressof (PATTERN (insn
))
452 || (REG_NOTES (insn
) && uses_addressof (REG_NOTES (insn
))))
458 /* Remove all REG_EQUIV notes found in the insn chain. */
461 purge_reg_equiv_notes (void)
465 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
469 rtx note
= find_reg_note (insn
, REG_EQUIV
, 0);
472 /* Remove the note and keep looking at the notes for
474 remove_note (insn
, note
);
482 /* Clear RTX_UNCHANGING_P flag of incoming argument MEMs. */
485 purge_mem_unchanging_flag (rtx x
)
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;
508 /* Scan all subexpressions. */
509 fmt
= GET_RTX_FORMAT (code
);
510 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++, fmt
++)
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
));
520 /* Replace the CALL_PLACEHOLDER with one of its children. INSN should be
521 the CALL_PLACEHOLDER insn; USE tells which child to use. */
524 replace_call_placeholder (rtx insn
, sibcall_use_t use
)
526 if (use
== sibcall_use_tail_recursion
)
527 emit_insn_before (XEXP (PATTERN (insn
), 2), insn
);
528 else if (use
== sibcall_use_sibcall
)
529 emit_insn_before (XEXP (PATTERN (insn
), 1), insn
);
530 else if (use
== sibcall_use_normal
)
531 emit_insn_before (XEXP (PATTERN (insn
), 0), insn
);
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;
541 /* "Delete" the placeholder insn. */
545 /* Given a (possibly empty) set of potential sibling or tail recursion call
546 sites, determine if optimization is possible.
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.
552 Replace the CALL_PLACEHOLDER with an appropriate insn chain. */
555 optimize_sibling_and_tail_recursive_calls (void)
558 basic_block alternate_exit
= EXIT_BLOCK_PTR
;
559 bool no_sibcalls_this_function
= false;
560 bool successful_replacement
= false;
561 bool replaced_call_placeholder
= false;
564 insns
= get_insns ();
566 cleanup_cfg (CLEANUP_PRE_SIBCALL
| CLEANUP_PRE_LOOP
);
568 /* If there are no basic blocks, then there is nothing to do. */
569 if (n_basic_blocks
== 0)
572 /* If we are using sjlj exceptions, we may need to add a call to
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;
578 return_value_pseudo
= NULL_RTX
;
580 /* Find the exit block.
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
;
591 if (e
->dest
!= EXIT_BLOCK_PTR
|| e
->succ_next
!= NULL
)
594 /* Walk forwards through the last normal block and see if it
595 does nothing except fall into the exit block. */
596 for (insn
= BB_HEAD (EXIT_BLOCK_PTR
->prev_bb
);
598 insn
= NEXT_INSN (insn
))
601 /* This should only happen once, at the start of this block. */
602 if (GET_CODE (insn
) == CODE_LABEL
)
605 if (GET_CODE (insn
) == NOTE
)
608 if (GET_CODE (insn
) == INSN
609 && GET_CODE (PATTERN (insn
)) == USE
)
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
)
620 return_value_pseudo
= SET_SRC (set
);
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. */
631 alternate_exit
= e
->src
;
633 return_value_pseudo
= NULL
;
636 /* If the function uses ADDRESSOF, we can't (easily) determine
637 at this point if the value will end up on the stack. */
638 no_sibcalls_this_function
|= sequence_uses_addressof (insns
);
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.
643 The different sequences represent different ways to implement the call,
644 ie, tail recursion, sibling call or normal call.
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
))
651 if (GET_CODE (insn
) == CALL_INSN
652 && GET_CODE (PATTERN (insn
)) == CALL_PLACEHOLDER
)
654 int sibcall
= (XEXP (PATTERN (insn
), 1) != NULL_RTX
);
655 int tailrecursion
= (XEXP (PATTERN (insn
), 2) != NULL_RTX
);
656 basic_block call_block
= BLOCK_FOR_INSN (insn
);
658 /* alloca (until we have stack slot life analysis) inhibits
659 sibling call optimizations, but not tail recursion.
660 Similarly if we use varargs or stdarg since they implicitly
661 may take the address of an argument. */
662 if (current_function_calls_alloca
|| current_function_stdarg
)
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
667 which are live at potential optimization sites. */
668 if (no_sibcalls_this_function
669 /* ??? Overly conservative. */
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
675 /* Can't if more than one successor or single successor is not
676 exit block. These two tests prevent tail call optimization
677 in the presence of active exception handlers. */
678 || call_block
->succ
== NULL
679 || call_block
->succ
->succ_next
!= NULL
680 || (call_block
->succ
->dest
!= EXIT_BLOCK_PTR
681 && call_block
->succ
->dest
!= alternate_exit
)
682 /* If this call doesn't end the block, there are operations at
683 the end of the block which we must execute after returning. */
684 || ! call_ends_block_p (insn
, BB_END (call_block
)))
685 sibcall
= 0, tailrecursion
= 0;
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. */
691 if (sibcall
|| tailrecursion
)
692 successful_replacement
= true;
693 replaced_call_placeholder
= true;
695 replace_call_placeholder (insn
,
697 ? sibcall_use_tail_recursion
699 ? sibcall_use_sibcall
700 : sibcall_use_normal
);
704 if (successful_replacement
)
709 /* A sibling call sequence invalidates any REG_EQUIV notes made for
710 this function's incoming arguments.
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
714 flush any REG_EQUIV note.
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 ();
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.
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
))
730 purge_mem_unchanging_flag (PATTERN (insn
));
733 /* Similarly, invalidate RTX_UNCHANGING_P for any incoming
734 arguments passed in registers. */
735 for (arg
= DECL_ARGUMENTS (current_function_decl
);
737 arg
= TREE_CHAIN (arg
))
739 if (REG_P (DECL_RTL (arg
)))
740 RTX_UNCHANGING_P (DECL_RTL (arg
)) = false;
744 /* There may have been NOTE_INSN_BLOCK_{BEGIN,END} notes in the
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
)
750 /* This information will be invalid after inline expansion. Kill it now. */
751 free_basic_block_vars (0);
752 free_EXPR_LIST_list (&tail_recursion_label_list
);