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
23 #include "coretypes.h"
29 #include "hard-reg-set.h"
31 #include "insn-config.h"
33 #include "basic-block.h"
38 /* In case alternate_exit_block contains copy from pseudo, to return value,
39 record the pseudo here. In such case the pseudo must be set to function
40 return in the sibcall sequence. */
41 static rtx return_value_pseudo
;
43 static int identify_call_return_value
PARAMS ((rtx
, rtx
*, rtx
*));
44 static rtx skip_copy_to_return_value
PARAMS ((rtx
));
45 static rtx skip_use_of_return_value
PARAMS ((rtx
, enum rtx_code
));
46 static rtx skip_stack_adjustment
PARAMS ((rtx
));
47 static rtx skip_pic_restore
PARAMS ((rtx
));
48 static rtx skip_jump_insn
PARAMS ((rtx
));
49 static int call_ends_block_p
PARAMS ((rtx
, rtx
));
50 static int uses_addressof
PARAMS ((rtx
));
51 static int sequence_uses_addressof
PARAMS ((rtx
));
52 static void purge_reg_equiv_notes
PARAMS ((void));
53 static void purge_mem_unchanging_flag
PARAMS ((rtx
));
54 static rtx skip_unreturned_value
PARAMS ((rtx
));
56 /* Examine a CALL_PLACEHOLDER pattern and determine where the call's
57 return value is located. P_HARD_RETURN receives the hard register
58 that the function used; P_SOFT_RETURN receives the pseudo register
59 that the sequence used. Return nonzero if the values were located. */
62 identify_call_return_value (cp
, p_hard_return
, p_soft_return
)
64 rtx
*p_hard_return
, *p_soft_return
;
66 rtx insn
, set
, hard
, soft
;
69 /* Search backward through the "normal" call sequence to the CALL insn. */
70 while (NEXT_INSN (insn
))
71 insn
= NEXT_INSN (insn
);
72 while (GET_CODE (insn
) != CALL_INSN
)
73 insn
= PREV_INSN (insn
);
75 /* Assume the pattern is (set (dest) (call ...)), or that the first
76 member of a parallel is. This is the hard return register used
78 if (GET_CODE (PATTERN (insn
)) == SET
79 && GET_CODE (SET_SRC (PATTERN (insn
))) == CALL
)
80 hard
= SET_DEST (PATTERN (insn
));
81 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
82 && GET_CODE (XVECEXP (PATTERN (insn
), 0, 0)) == SET
83 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn
), 0, 0))) == CALL
)
84 hard
= SET_DEST (XVECEXP (PATTERN (insn
), 0, 0));
88 /* If we didn't get a single hard register (e.g. a parallel), give up. */
89 if (GET_CODE (hard
) != REG
)
92 /* Stack adjustment done after call may appear here. */
93 insn
= skip_stack_adjustment (insn
);
97 /* Restore of GP register may appear here. */
98 insn
= skip_pic_restore (insn
);
102 /* If there's nothing after, there's no soft return value. */
103 insn
= NEXT_INSN (insn
);
107 /* We're looking for a source of the hard return register. */
108 set
= single_set (insn
);
109 if (! set
|| SET_SRC (set
) != hard
)
112 soft
= SET_DEST (set
);
113 insn
= NEXT_INSN (insn
);
115 /* Allow this first destination to be copied to a second register,
116 as might happen if the first register wasn't the particular pseudo
117 we'd been expecting. */
119 && (set
= single_set (insn
)) != NULL_RTX
120 && SET_SRC (set
) == soft
)
122 soft
= SET_DEST (set
);
123 insn
= NEXT_INSN (insn
);
126 /* Don't fool with anything but pseudo registers. */
127 if (GET_CODE (soft
) != REG
|| REGNO (soft
) < FIRST_PSEUDO_REGISTER
)
130 /* This value must not be modified before the end of the sequence. */
131 if (reg_set_between_p (soft
, insn
, NULL_RTX
))
134 *p_hard_return
= hard
;
135 *p_soft_return
= soft
;
140 /* If the first real insn after ORIG_INSN copies to this function's
141 return value from RETVAL, then return the insn which performs the
142 copy. Otherwise return ORIG_INSN. */
145 skip_copy_to_return_value (orig_insn
)
148 rtx insn
, set
= NULL_RTX
;
149 rtx hardret
, softret
;
151 /* If there is no return value, we have nothing to do. */
152 if (! identify_call_return_value (PATTERN (orig_insn
), &hardret
, &softret
))
155 insn
= next_nonnote_insn (orig_insn
);
159 set
= single_set (insn
);
163 if (return_value_pseudo
)
165 if (SET_DEST (set
) == return_value_pseudo
166 && SET_SRC (set
) == softret
)
171 /* The destination must be the same as the called function's return
172 value to ensure that any return value is put in the same place by the
173 current function and the function we're calling.
175 Further, the source must be the same as the pseudo into which the
176 called function's return value was copied. Otherwise we're returning
179 #ifndef OUTGOING_REGNO
180 #define OUTGOING_REGNO(N) (N)
183 if (SET_DEST (set
) == current_function_return_rtx
184 && REG_P (SET_DEST (set
))
185 && OUTGOING_REGNO (REGNO (SET_DEST (set
))) == REGNO (hardret
)
186 && SET_SRC (set
) == softret
)
189 /* Recognize the situation when the called function's return value
190 is copied in two steps: first into an intermediate pseudo, then
191 the into the calling functions return value register. */
193 if (REG_P (SET_DEST (set
))
194 && SET_SRC (set
) == softret
)
196 rtx x
= SET_DEST (set
);
198 insn
= next_nonnote_insn (insn
);
202 set
= single_set (insn
);
206 if (SET_DEST (set
) == current_function_return_rtx
207 && REG_P (SET_DEST (set
))
208 && OUTGOING_REGNO (REGNO (SET_DEST (set
))) == REGNO (hardret
)
209 && SET_SRC (set
) == x
)
213 /* It did not look like a copy of the return value, so return the
214 same insn we were passed. */
218 /* If the first real insn after ORIG_INSN is a CODE of this function's return
219 value, return insn. Otherwise return ORIG_INSN. */
222 skip_use_of_return_value (orig_insn
, code
)
228 insn
= next_nonnote_insn (orig_insn
);
231 && GET_CODE (insn
) == INSN
232 && GET_CODE (PATTERN (insn
)) == code
233 && (XEXP (PATTERN (insn
), 0) == current_function_return_rtx
234 || XEXP (PATTERN (insn
), 0) == const0_rtx
))
240 /* In case function does not return value, we get clobber of pseudo followed
241 by set to hard return value. */
243 skip_unreturned_value (orig_insn
)
246 rtx insn
= next_nonnote_insn (orig_insn
);
248 /* Skip possible clobber of pseudo return register. */
250 && GET_CODE (insn
) == INSN
251 && GET_CODE (PATTERN (insn
)) == CLOBBER
252 && REG_P (XEXP (PATTERN (insn
), 0))
253 && (REGNO (XEXP (PATTERN (insn
), 0)) >= FIRST_PSEUDO_REGISTER
))
255 rtx set_insn
= next_nonnote_insn (insn
);
259 set
= single_set (set_insn
);
261 || SET_SRC (set
) != XEXP (PATTERN (insn
), 0)
262 || SET_DEST (set
) != current_function_return_rtx
)
269 /* If the first real insn after ORIG_INSN adjusts the stack pointer
270 by a constant, return the insn with the stack pointer adjustment.
271 Otherwise return ORIG_INSN. */
274 skip_stack_adjustment (orig_insn
)
277 rtx insn
, set
= NULL_RTX
;
279 insn
= next_nonnote_insn (orig_insn
);
282 set
= single_set (insn
);
286 && GET_CODE (SET_SRC (set
)) == PLUS
287 && XEXP (SET_SRC (set
), 0) == stack_pointer_rtx
288 && GET_CODE (XEXP (SET_SRC (set
), 1)) == CONST_INT
289 && SET_DEST (set
) == stack_pointer_rtx
)
295 /* If the first real insn after ORIG_INSN sets the pic register,
296 return it. Otherwise return ORIG_INSN. */
299 skip_pic_restore (orig_insn
)
302 rtx insn
, set
= NULL_RTX
;
304 insn
= next_nonnote_insn (orig_insn
);
307 set
= single_set (insn
);
309 if (insn
&& set
&& SET_DEST (set
) == pic_offset_table_rtx
)
315 /* If the first real insn after ORIG_INSN is a jump, return the JUMP_INSN.
316 Otherwise return ORIG_INSN. */
319 skip_jump_insn (orig_insn
)
324 insn
= next_nonnote_insn (orig_insn
);
327 && GET_CODE (insn
) == JUMP_INSN
328 && any_uncondjump_p (insn
))
334 /* Using the above functions, see if INSN, skipping any of the above,
335 goes all the way to END, the end of a basic block. Return 1 if so. */
338 call_ends_block_p (insn
, end
)
343 /* END might be a note, so get the last nonnote insn of the block. */
344 end
= next_nonnote_insn (PREV_INSN (end
));
346 /* If the call was the end of the block, then we're OK. */
350 /* Skip over copying from the call's return value pseudo into
351 this function's hard return register and if that's the end
352 of the block, we're OK. */
353 new_insn
= skip_copy_to_return_value (insn
);
355 /* In case we return value in pseudo, we must set the pseudo to
356 return value of called function, otherwise we are returning
358 if (return_value_pseudo
&& insn
== new_insn
)
365 /* Skip any stack adjustment. */
366 insn
= skip_stack_adjustment (insn
);
370 /* Skip over a CLOBBER of the return value as a hard reg. */
371 insn
= skip_use_of_return_value (insn
, CLOBBER
);
375 /* Skip over a CLOBBER of the return value as a hard reg. */
376 insn
= skip_unreturned_value (insn
);
380 /* Skip over a USE of the return value (as a hard reg). */
381 insn
= skip_use_of_return_value (insn
, USE
);
385 /* Skip over a JUMP_INSN at the end of the block. If that doesn't end the
386 block, the original CALL_INSN didn't. */
387 insn
= skip_jump_insn (insn
);
391 /* Scan the rtx X for ADDRESSOF expressions or
392 current_function_internal_arg_pointer registers.
393 Return nonzero if an ADDRESSOF or current_function_internal_arg_pointer
394 is found outside of some MEM expression, else return zero. */
409 if (code
== ADDRESSOF
|| x
== current_function_internal_arg_pointer
)
415 /* Scan all subexpressions. */
416 fmt
= GET_RTX_FORMAT (code
);
417 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++, fmt
++)
421 if (uses_addressof (XEXP (x
, i
)))
424 else if (*fmt
== 'E')
426 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
427 if (uses_addressof (XVECEXP (x
, i
, j
)))
434 /* Scan the sequence of insns in SEQ to see if any have an ADDRESSOF
435 rtl expression or current_function_internal_arg_pointer occurrences
436 not enclosed within a MEM. If an ADDRESSOF expression or
437 current_function_internal_arg_pointer is found, return nonzero, otherwise
440 This function handles CALL_PLACEHOLDERs which contain multiple sequences
444 sequence_uses_addressof (seq
)
449 for (insn
= seq
; insn
; insn
= NEXT_INSN (insn
))
452 /* If this is a CALL_PLACEHOLDER, then recursively call ourselves
453 with each nonempty sequence attached to the CALL_PLACEHOLDER. */
454 if (GET_CODE (insn
) == CALL_INSN
455 && GET_CODE (PATTERN (insn
)) == CALL_PLACEHOLDER
)
457 if (XEXP (PATTERN (insn
), 0) != NULL_RTX
458 && sequence_uses_addressof (XEXP (PATTERN (insn
), 0)))
460 if (XEXP (PATTERN (insn
), 1) != NULL_RTX
461 && sequence_uses_addressof (XEXP (PATTERN (insn
), 1)))
463 if (XEXP (PATTERN (insn
), 2) != NULL_RTX
464 && sequence_uses_addressof (XEXP (PATTERN (insn
), 2)))
467 else if (uses_addressof (PATTERN (insn
))
468 || (REG_NOTES (insn
) && uses_addressof (REG_NOTES (insn
))))
474 /* Remove all REG_EQUIV notes found in the insn chain. */
477 purge_reg_equiv_notes ()
481 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
485 rtx note
= find_reg_note (insn
, REG_EQUIV
, 0);
488 /* Remove the note and keep looking at the notes for
490 remove_note (insn
, note
);
498 /* Clear RTX_UNCHANGING_P flag of incoming argument MEMs. */
501 purge_mem_unchanging_flag (x
)
515 if (RTX_UNCHANGING_P (x
)
516 && (XEXP (x
, 0) == current_function_internal_arg_pointer
517 || (GET_CODE (XEXP (x
, 0)) == PLUS
518 && XEXP (XEXP (x
, 0), 0) ==
519 current_function_internal_arg_pointer
520 && GET_CODE (XEXP (XEXP (x
, 0), 1)) == CONST_INT
)))
521 RTX_UNCHANGING_P (x
) = 0;
525 /* Scan all subexpressions. */
526 fmt
= GET_RTX_FORMAT (code
);
527 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++, fmt
++)
530 purge_mem_unchanging_flag (XEXP (x
, i
));
531 else if (*fmt
== 'E')
532 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
533 purge_mem_unchanging_flag (XVECEXP (x
, i
, j
));
537 /* Replace the CALL_PLACEHOLDER with one of its children. INSN should be
538 the CALL_PLACEHOLDER insn; USE tells which child to use. */
541 replace_call_placeholder (insn
, use
)
545 if (use
== sibcall_use_tail_recursion
)
546 emit_insn_before (XEXP (PATTERN (insn
), 2), insn
);
547 else if (use
== sibcall_use_sibcall
)
548 emit_insn_before (XEXP (PATTERN (insn
), 1), insn
);
549 else if (use
== sibcall_use_normal
)
550 emit_insn_before (XEXP (PATTERN (insn
), 0), insn
);
554 /* Turn off LABEL_PRESERVE_P for the tail recursion label if it
555 exists. We only had to set it long enough to keep the jump
556 pass above from deleting it as unused. */
557 if (XEXP (PATTERN (insn
), 3))
558 LABEL_PRESERVE_P (XEXP (PATTERN (insn
), 3)) = 0;
560 /* "Delete" the placeholder insn. */
564 /* Given a (possibly empty) set of potential sibling or tail recursion call
565 sites, determine if optimization is possible.
567 Potential sibling or tail recursion calls are marked with CALL_PLACEHOLDER
568 insns. The CALL_PLACEHOLDER insn holds chains of insns to implement a
569 normal call, sibling call or tail recursive call.
571 Replace the CALL_PLACEHOLDER with an appropriate insn chain. */
574 optimize_sibling_and_tail_recursive_calls ()
577 basic_block alternate_exit
= EXIT_BLOCK_PTR
;
578 bool no_sibcalls_this_function
= false;
579 bool successful_replacement
= false;
580 bool replaced_call_placeholder
= false;
583 insns
= get_insns ();
585 cleanup_cfg (CLEANUP_PRE_SIBCALL
| CLEANUP_PRE_LOOP
);
587 /* If there are no basic blocks, then there is nothing to do. */
588 if (n_basic_blocks
== 0)
591 /* If we are using sjlj exceptions, we may need to add a call to
592 _Unwind_SjLj_Unregister at exit of the function. Which means
593 that we cannot do any sibcall transformations. */
594 if (USING_SJLJ_EXCEPTIONS
&& current_function_has_exception_handlers ())
595 no_sibcalls_this_function
= true;
597 return_value_pseudo
= NULL_RTX
;
599 /* Find the exit block.
601 It is possible that we have blocks which can reach the exit block
602 directly. However, most of the time a block will jump (or fall into)
603 N_BASIC_BLOCKS - 1, which in turn falls into the exit block. */
604 for (e
= EXIT_BLOCK_PTR
->pred
;
605 e
&& alternate_exit
== EXIT_BLOCK_PTR
;
610 if (e
->dest
!= EXIT_BLOCK_PTR
|| e
->succ_next
!= NULL
)
613 /* Walk forwards through the last normal block and see if it
614 does nothing except fall into the exit block. */
615 for (insn
= EXIT_BLOCK_PTR
->prev_bb
->head
;
617 insn
= NEXT_INSN (insn
))
620 /* This should only happen once, at the start of this block. */
621 if (GET_CODE (insn
) == CODE_LABEL
)
624 if (GET_CODE (insn
) == NOTE
)
627 if (GET_CODE (insn
) == INSN
628 && GET_CODE (PATTERN (insn
)) == USE
)
631 /* Exit block also may contain copy from pseudo containing
632 return value to hard register. */
633 if (GET_CODE (insn
) == INSN
634 && (set
= single_set (insn
))
635 && SET_DEST (set
) == current_function_return_rtx
636 && REG_P (SET_SRC (set
))
637 && !return_value_pseudo
)
639 return_value_pseudo
= SET_SRC (set
);
646 /* If INSN is zero, then the search walked all the way through the
647 block without hitting anything interesting. This block is a
648 valid alternate exit block. */
650 alternate_exit
= e
->src
;
652 return_value_pseudo
= NULL
;
655 /* If the function uses ADDRESSOF, we can't (easily) determine
656 at this point if the value will end up on the stack. */
657 no_sibcalls_this_function
|= sequence_uses_addressof (insns
);
659 /* Walk the insn chain and find any CALL_PLACEHOLDER insns. We need to
660 select one of the insn sequences attached to each CALL_PLACEHOLDER.
662 The different sequences represent different ways to implement the call,
663 ie, tail recursion, sibling call or normal call.
665 Since we do not create nested CALL_PLACEHOLDERs, the scan
666 continues with the insn that was after a replaced CALL_PLACEHOLDER;
667 we don't rescan the replacement insns. */
668 for (insn
= insns
; insn
; insn
= NEXT_INSN (insn
))
670 if (GET_CODE (insn
) == CALL_INSN
671 && GET_CODE (PATTERN (insn
)) == CALL_PLACEHOLDER
)
673 int sibcall
= (XEXP (PATTERN (insn
), 1) != NULL_RTX
);
674 int tailrecursion
= (XEXP (PATTERN (insn
), 2) != NULL_RTX
);
675 basic_block call_block
= BLOCK_FOR_INSN (insn
);
677 /* alloca (until we have stack slot life analysis) inhibits
678 sibling call optimizations, but not tail recursion.
679 Similarly if we use varargs or stdarg since they implicitly
680 may take the address of an argument. */
681 if (current_function_calls_alloca
|| current_function_stdarg
)
684 /* See if there are any reasons we can't perform either sibling or
685 tail call optimizations. We must be careful with stack slots
686 which are live at potential optimization sites. */
687 if (no_sibcalls_this_function
688 /* ??? Overly conservative. */
690 /* Any function that calls setjmp might have longjmp called from
691 any called function. ??? We really should represent this
692 properly in the CFG so that this needn't be special cased. */
693 || current_function_calls_setjmp
694 /* Can't if more than one successor or single successor is not
695 exit block. These two tests prevent tail call optimization
696 in the presence of active exception handlers. */
697 || call_block
->succ
== NULL
698 || call_block
->succ
->succ_next
!= NULL
699 || (call_block
->succ
->dest
!= EXIT_BLOCK_PTR
700 && call_block
->succ
->dest
!= alternate_exit
)
701 /* If this call doesn't end the block, there are operations at
702 the end of the block which we must execute after returning. */
703 || ! call_ends_block_p (insn
, call_block
->end
))
704 sibcall
= 0, tailrecursion
= 0;
706 /* Select a set of insns to implement the call and emit them.
707 Tail recursion is the most efficient, so select it over
708 a tail/sibling call. */
710 if (sibcall
|| tailrecursion
)
711 successful_replacement
= true;
712 replaced_call_placeholder
= true;
714 replace_call_placeholder (insn
,
716 ? sibcall_use_tail_recursion
718 ? sibcall_use_sibcall
719 : sibcall_use_normal
);
723 if (successful_replacement
)
728 /* A sibling call sequence invalidates any REG_EQUIV notes made for
729 this function's incoming arguments.
731 At the start of RTL generation we know the only REG_EQUIV notes
732 in the rtl chain are those for incoming arguments, so we can safely
733 flush any REG_EQUIV note.
735 This is (slight) overkill. We could keep track of the highest
736 argument we clobber and be more selective in removing notes, but it
737 does not seem to be worth the effort. */
738 purge_reg_equiv_notes ();
740 /* A sibling call sequence also may invalidate RTX_UNCHANGING_P
741 flag of some incoming arguments MEM RTLs, because it can write into
742 those slots. We clear all those bits now.
744 This is (slight) overkill, we could keep track of which arguments
745 we actually write into. */
746 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
749 purge_mem_unchanging_flag (PATTERN (insn
));
752 /* Similarly, invalidate RTX_UNCHANGING_P for any incoming
753 arguments passed in registers. */
754 for (arg
= DECL_ARGUMENTS (current_function_decl
);
756 arg
= TREE_CHAIN (arg
))
758 if (REG_P (DECL_RTL (arg
)))
759 RTX_UNCHANGING_P (DECL_RTL (arg
)) = false;
763 /* There may have been NOTE_INSN_BLOCK_{BEGIN,END} notes in the
764 CALL_PLACEHOLDER alternatives that we didn't emit. Rebuild the
765 lexical block tree to correspond to the notes that still exist. */
766 if (replaced_call_placeholder
)
769 /* This information will be invalid after inline expansion. Kill it now. */
770 free_basic_block_vars (0);
771 free_EXPR_LIST_list (&tail_recursion_label_list
);