1 /* Generic sibling call optimization support
2 Copyright (C) 1999, 2000, 2001 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));
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 call_ends_block_p PARAMS ((rtx, rtx));
42 static int uses_addressof PARAMS ((rtx));
43 static int sequence_uses_addressof PARAMS ((rtx));
44 static void purge_reg_equiv_notes PARAMS ((void));
45 static void purge_mem_unchanging_flag PARAMS ((rtx));
46 static rtx skip_unreturned_value PARAMS ((rtx));
48 /* Examine a CALL_PLACEHOLDER pattern and determine where the call's
49 return value is located. P_HARD_RETURN receives the hard register
50 that the function used; P_SOFT_RETURN receives the pseudo register
51 that the sequence used. Return non-zero if the values were located. */
54 identify_call_return_value (cp, p_hard_return, p_soft_return)
56 rtx *p_hard_return, *p_soft_return;
58 rtx insn, set, hard, soft;
61 /* Search backward through the "normal" call sequence to the CALL insn. */
62 while (NEXT_INSN (insn))
63 insn = NEXT_INSN (insn);
64 while (GET_CODE (insn) != CALL_INSN)
65 insn = PREV_INSN (insn);
67 /* Assume the pattern is (set (dest) (call ...)), or that the first
68 member of a parallel is. This is the hard return register used
70 if (GET_CODE (PATTERN (insn)) == SET
71 && GET_CODE (SET_SRC (PATTERN (insn))) == CALL)
72 hard = SET_DEST (PATTERN (insn));
73 else if (GET_CODE (PATTERN (insn)) == PARALLEL
74 && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
75 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == CALL)
76 hard = SET_DEST (XVECEXP (PATTERN (insn), 0, 0));
80 /* If we didn't get a single hard register (e.g. a parallel), give up. */
81 if (GET_CODE (hard) != REG)
84 /* Stack adjustment done after call may appear here. */
85 insn = skip_stack_adjustment (insn);
89 /* Restore of GP register may appear here. */
90 insn = skip_pic_restore (insn);
94 /* If there's nothing after, there's no soft return value. */
95 insn = NEXT_INSN (insn);
99 /* We're looking for a source of the hard return register. */
100 set = single_set (insn);
101 if (! set || SET_SRC (set) != hard)
104 soft = SET_DEST (set);
105 insn = NEXT_INSN (insn);
107 /* Allow this first destination to be copied to a second register,
108 as might happen if the first register wasn't the particular pseudo
109 we'd been expecting. */
111 && (set = single_set (insn)) != NULL_RTX
112 && SET_SRC (set) == soft)
114 soft = SET_DEST (set);
115 insn = NEXT_INSN (insn);
118 /* Don't fool with anything but pseudo registers. */
119 if (GET_CODE (soft) != REG || REGNO (soft) < FIRST_PSEUDO_REGISTER)
122 /* This value must not be modified before the end of the sequence. */
123 if (reg_set_between_p (soft, insn, NULL_RTX))
126 *p_hard_return = hard;
127 *p_soft_return = soft;
132 /* If the first real insn after ORIG_INSN copies to this function's
133 return value from RETVAL, then return the insn which performs the
134 copy. Otherwise return ORIG_INSN. */
137 skip_copy_to_return_value (orig_insn)
140 rtx insn, set = NULL_RTX;
141 rtx hardret, softret;
143 /* If there is no return value, we have nothing to do. */
144 if (! identify_call_return_value (PATTERN (orig_insn), &hardret, &softret))
147 insn = next_nonnote_insn (orig_insn);
151 set = single_set (insn);
155 /* The destination must be the same as the called function's return
156 value to ensure that any return value is put in the same place by the
157 current function and the function we're calling.
159 Further, the source must be the same as the pseudo into which the
160 called function's return value was copied. Otherwise we're returning
163 #ifndef OUTGOING_REGNO
164 #define OUTGOING_REGNO(N) (N)
167 if (SET_DEST (set) == current_function_return_rtx
168 && REG_P (SET_DEST (set))
169 && OUTGOING_REGNO (REGNO (SET_DEST (set))) == REGNO (hardret)
170 && SET_SRC (set) == softret)
173 /* Recognize the situation when the called function's return value
174 is copied in two steps: first into an intermediate pseudo, then
175 the into the calling functions return value register. */
177 if (REG_P (SET_DEST (set))
178 && SET_SRC (set) == softret)
180 rtx x = SET_DEST (set);
182 insn = next_nonnote_insn (insn);
186 set = single_set (insn);
190 if (SET_DEST (set) == current_function_return_rtx
191 && REG_P (SET_DEST (set))
192 && OUTGOING_REGNO (REGNO (SET_DEST (set))) == REGNO (hardret)
193 && SET_SRC (set) == x)
197 /* It did not look like a copy of the return value, so return the
198 same insn we were passed. */
202 /* If the first real insn after ORIG_INSN is a CODE of this function's return
203 value, return insn. Otherwise return ORIG_INSN. */
206 skip_use_of_return_value (orig_insn, code)
212 insn = next_nonnote_insn (orig_insn);
215 && GET_CODE (insn) == INSN
216 && GET_CODE (PATTERN (insn)) == code
217 && (XEXP (PATTERN (insn), 0) == current_function_return_rtx
218 || XEXP (PATTERN (insn), 0) == const0_rtx))
224 /* In case function does not return value, we get clobber of pseudo followed
225 by set to hard return value. */
227 skip_unreturned_value (orig_insn)
230 rtx insn = next_nonnote_insn (orig_insn);
232 /* Skip possible clobber of pseudo return register. */
234 && GET_CODE (insn) == INSN
235 && GET_CODE (PATTERN (insn)) == CLOBBER
236 && REG_P (XEXP (PATTERN (insn), 0))
237 && (REGNO (XEXP (PATTERN (insn), 0)) >= FIRST_PSEUDO_REGISTER))
239 rtx set_insn = next_nonnote_insn (insn);
243 set = single_set (set_insn);
245 || SET_SRC (set) != XEXP (PATTERN (insn), 0)
246 || SET_DEST (set) != current_function_return_rtx)
253 /* If the first real insn after ORIG_INSN adjusts the stack pointer
254 by a constant, return the insn with the stack pointer adjustment.
255 Otherwise return ORIG_INSN. */
258 skip_stack_adjustment (orig_insn)
261 rtx insn, set = NULL_RTX;
263 insn = next_nonnote_insn (orig_insn);
266 set = single_set (insn);
270 && GET_CODE (SET_SRC (set)) == PLUS
271 && XEXP (SET_SRC (set), 0) == stack_pointer_rtx
272 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
273 && SET_DEST (set) == stack_pointer_rtx)
279 /* If the first real insn after ORIG_INSN sets the pic register,
280 return it. Otherwise return ORIG_INSN. */
283 skip_pic_restore (orig_insn)
286 rtx insn, set = NULL_RTX;
288 insn = next_nonnote_insn (orig_insn);
291 set = single_set (insn);
293 if (insn && set && SET_DEST (set) == pic_offset_table_rtx)
299 /* If the first real insn after ORIG_INSN is a jump, return the JUMP_INSN.
300 Otherwise return ORIG_INSN. */
303 skip_jump_insn (orig_insn)
308 insn = next_nonnote_insn (orig_insn);
311 && GET_CODE (insn) == JUMP_INSN
312 && any_uncondjump_p (insn))
318 /* Using the above functions, see if INSN, skipping any of the above,
319 goes all the way to END, the end of a basic block. Return 1 if so. */
322 call_ends_block_p (insn, end)
326 /* END might be a note, so get the last nonnote insn of the block. */
327 end = next_nonnote_insn (PREV_INSN (end));
329 /* If the call was the end of the block, then we're OK. */
333 /* Skip over copying from the call's return value pseudo into
334 this function's hard return register and if that's the end
335 of the block, we're OK. */
336 insn = skip_copy_to_return_value (insn);
340 /* Skip any stack adjustment. */
341 insn = skip_stack_adjustment (insn);
345 /* Skip over a CLOBBER of the return value as a hard reg. */
346 insn = skip_use_of_return_value (insn, CLOBBER);
350 /* Skip over a CLOBBER of the return value as a hard reg. */
351 insn = skip_unreturned_value (insn);
355 /* Skip over a USE of the return value (as a hard reg). */
356 insn = skip_use_of_return_value (insn, USE);
360 /* Skip over a JUMP_INSN at the end of the block. If that doesn't end the
361 block, the original CALL_INSN didn't. */
362 insn = skip_jump_insn (insn);
366 /* Scan the rtx X for ADDRESSOF expressions or
367 current_function_internal_arg_pointer registers.
368 Return nonzero if an ADDRESSOF or current_function_internal_arg_pointer
369 is found outside of some MEM expression, else return zero. */
384 if (code == ADDRESSOF || x == current_function_internal_arg_pointer)
390 /* Scan all subexpressions. */
391 fmt = GET_RTX_FORMAT (code);
392 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
396 if (uses_addressof (XEXP (x, i)))
399 else if (*fmt == 'E')
401 for (j = 0; j < XVECLEN (x, i); j++)
402 if (uses_addressof (XVECEXP (x, i, j)))
409 /* Scan the sequence of insns in SEQ to see if any have an ADDRESSOF
410 rtl expression or current_function_internal_arg_pointer occurences
411 not enclosed within a MEM. If an ADDRESSOF expression or
412 current_function_internal_arg_pointer is found, return nonzero, otherwise
415 This function handles CALL_PLACEHOLDERs which contain multiple sequences
419 sequence_uses_addressof (seq)
424 for (insn = seq; insn; insn = NEXT_INSN (insn))
427 /* If this is a CALL_PLACEHOLDER, then recursively call ourselves
428 with each nonempty sequence attached to the CALL_PLACEHOLDER. */
429 if (GET_CODE (insn) == CALL_INSN
430 && GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
432 if (XEXP (PATTERN (insn), 0) != NULL_RTX
433 && sequence_uses_addressof (XEXP (PATTERN (insn), 0)))
435 if (XEXP (PATTERN (insn), 1) != NULL_RTX
436 && sequence_uses_addressof (XEXP (PATTERN (insn), 1)))
438 if (XEXP (PATTERN (insn), 2) != NULL_RTX
439 && sequence_uses_addressof (XEXP (PATTERN (insn), 2)))
442 else if (uses_addressof (PATTERN (insn))
443 || (REG_NOTES (insn) && uses_addressof (REG_NOTES (insn))))
449 /* Remove all REG_EQUIV notes found in the insn chain. */
452 purge_reg_equiv_notes ()
456 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
460 rtx note = find_reg_note (insn, REG_EQUIV, 0);
463 /* Remove the note and keep looking at the notes for
465 remove_note (insn, note);
473 /* Clear RTX_UNCHANGING_P flag of incoming argument MEMs. */
476 purge_mem_unchanging_flag (x)
490 if (RTX_UNCHANGING_P (x)
491 && (XEXP (x, 0) == current_function_internal_arg_pointer
492 || (GET_CODE (XEXP (x, 0)) == PLUS
493 && XEXP (XEXP (x, 0), 0) ==
494 current_function_internal_arg_pointer
495 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)))
496 RTX_UNCHANGING_P (x) = 0;
500 /* Scan all subexpressions. */
501 fmt = GET_RTX_FORMAT (code);
502 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
505 purge_mem_unchanging_flag (XEXP (x, i));
506 else if (*fmt == 'E')
507 for (j = 0; j < XVECLEN (x, i); j++)
508 purge_mem_unchanging_flag (XVECEXP (x, i, j));
512 /* Replace the CALL_PLACEHOLDER with one of its children. INSN should be
513 the CALL_PLACEHOLDER insn; USE tells which child to use. */
516 replace_call_placeholder (insn, use)
520 if (use == sibcall_use_tail_recursion)
521 emit_insns_before (XEXP (PATTERN (insn), 2), insn);
522 else if (use == sibcall_use_sibcall)
523 emit_insns_before (XEXP (PATTERN (insn), 1), insn);
524 else if (use == sibcall_use_normal)
525 emit_insns_before (XEXP (PATTERN (insn), 0), insn);
529 /* Turn off LABEL_PRESERVE_P for the tail recursion label if it
530 exists. We only had to set it long enough to keep the jump
531 pass above from deleting it as unused. */
532 if (XEXP (PATTERN (insn), 3))
533 LABEL_PRESERVE_P (XEXP (PATTERN (insn), 3)) = 0;
535 /* "Delete" the placeholder insn. */
536 PUT_CODE (insn, NOTE);
537 NOTE_SOURCE_FILE (insn) = 0;
538 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
541 /* Given a (possibly empty) set of potential sibling or tail recursion call
542 sites, determine if optimization is possible.
544 Potential sibling or tail recursion calls are marked with CALL_PLACEHOLDER
545 insns. The CALL_PLACEHOLDER insn holds chains of insns to implement a
546 normal call, sibling call or tail recursive call.
548 Replace the CALL_PLACEHOLDER with an appropriate insn chain. */
551 optimize_sibling_and_tail_recursive_calls ()
554 basic_block alternate_exit = EXIT_BLOCK_PTR;
555 int current_function_uses_addressof;
556 int successful_sibling_call = 0;
557 int replaced_call_placeholder = 0;
560 insns = get_insns ();
562 /* We do not perform these calls when flag_exceptions is true, so this
563 is probably a NOP at the current time. However, we may want to support
564 sibling and tail recursion optimizations in the future, so let's plan
565 ahead and find all the EH labels. */
566 find_exception_handler_labels ();
568 /* Run a jump optimization pass to clean up the CFG. We primarily want
569 this to thread jumps so that it is obvious which blocks jump to the
571 jump_optimize_minimal (insns);
573 /* We need cfg information to determine which blocks are succeeded
574 only by the epilogue. */
575 find_basic_blocks (insns, max_reg_num (), 0);
578 /* If there are no basic blocks, then there is nothing to do. */
579 if (n_basic_blocks == 0)
582 /* Find the exit block.
584 It is possible that we have blocks which can reach the exit block
585 directly. However, most of the time a block will jump (or fall into)
586 N_BASIC_BLOCKS - 1, which in turn falls into the exit block. */
587 for (e = EXIT_BLOCK_PTR->pred;
588 e && alternate_exit == EXIT_BLOCK_PTR;
593 if (e->dest != EXIT_BLOCK_PTR || e->succ_next != NULL)
596 /* Walk forwards through the last normal block and see if it
597 does nothing except fall into the exit block. */
598 for (insn = BLOCK_HEAD (n_basic_blocks - 1);
600 insn = NEXT_INSN (insn))
602 /* This should only happen once, at the start of this block. */
603 if (GET_CODE (insn) == CODE_LABEL)
606 if (GET_CODE (insn) == NOTE)
609 if (GET_CODE (insn) == INSN
610 && GET_CODE (PATTERN (insn)) == USE)
616 /* If INSN is zero, then the search walked all the way through the
617 block without hitting anything interesting. This block is a
618 valid alternate exit block. */
620 alternate_exit = e->src;
623 /* If the function uses ADDRESSOF, we can't (easily) determine
624 at this point if the value will end up on the stack. */
625 current_function_uses_addressof = sequence_uses_addressof (insns);
627 /* Walk the insn chain and find any CALL_PLACEHOLDER insns. We need to
628 select one of the insn sequences attached to each CALL_PLACEHOLDER.
630 The different sequences represent different ways to implement the call,
631 ie, tail recursion, sibling call or normal call.
633 Since we do not create nested CALL_PLACEHOLDERs, the scan
634 continues with the insn that was after a replaced CALL_PLACEHOLDER;
635 we don't rescan the replacement insns. */
636 for (insn = insns; insn; insn = NEXT_INSN (insn))
638 if (GET_CODE (insn) == CALL_INSN
639 && GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
641 int sibcall = (XEXP (PATTERN (insn), 1) != NULL_RTX);
642 int tailrecursion = (XEXP (PATTERN (insn), 2) != NULL_RTX);
643 basic_block call_block = BLOCK_FOR_INSN (insn);
645 /* alloca (until we have stack slot life analysis) inhibits
646 sibling call optimizations, but not tail recursion.
647 Similarly if we use varargs or stdarg since they implicitly
648 may take the address of an argument. */
649 if (current_function_calls_alloca
650 || current_function_varargs || current_function_stdarg)
653 /* See if there are any reasons we can't perform either sibling or
654 tail call optimizations. We must be careful with stack slots
655 which are live at potential optimization sites. ??? The first
656 test is overly conservative and should be replaced. */
658 /* Can't take address of local var if used by recursive call. */
659 || current_function_uses_addressof
660 /* Any function that calls setjmp might have longjmp called from
661 any called function. ??? We really should represent this
662 properly in the CFG so that this needn't be special cased. */
663 || current_function_calls_setjmp
664 /* Can't if more than one successor or single successor is not
665 exit block. These two tests prevent tail call optimization
666 in the presense of active exception handlers. */
667 || call_block->succ == NULL
668 || call_block->succ->succ_next != NULL
669 || (call_block->succ->dest != EXIT_BLOCK_PTR
670 && call_block->succ->dest != alternate_exit)
671 /* If this call doesn't end the block, there are operations at
672 the end of the block which we must execute after returning. */
673 || ! call_ends_block_p (insn, call_block->end))
674 sibcall = 0, tailrecursion = 0;
676 /* Select a set of insns to implement the call and emit them.
677 Tail recursion is the most efficient, so select it over
678 a tail/sibling call. */
680 successful_sibling_call = 1;
682 replaced_call_placeholder = 1;
683 replace_call_placeholder (insn,
685 ? sibcall_use_tail_recursion
687 ? sibcall_use_sibcall
688 : sibcall_use_normal);
692 if (successful_sibling_call)
696 /* A sibling call sequence invalidates any REG_EQUIV notes made for
697 this function's incoming arguments.
699 At the start of RTL generation we know the only REG_EQUIV notes
700 in the rtl chain are those for incoming arguments, so we can safely
701 flush any REG_EQUIV note.
703 This is (slight) overkill. We could keep track of the highest
704 argument we clobber and be more selective in removing notes, but it
705 does not seem to be worth the effort. */
706 purge_reg_equiv_notes ();
708 /* A sibling call sequence also may invalidate RTX_UNCHANGING_P
709 flag of some incoming arguments MEM RTLs, because it can write into
710 those slots. We clear all those bits now.
712 This is (slight) overkill, we could keep track of which arguments
713 we actually write into. */
714 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
716 if (GET_CODE (insn) == NOTE)
718 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
721 else if (INSN_P (insn))
722 purge_mem_unchanging_flag (PATTERN (insn));
726 /* There may have been NOTE_INSN_BLOCK_{BEGIN,END} notes in the
727 CALL_PLACEHOLDER alternatives that we didn't emit. Rebuild the
728 lexical block tree to correspond to the notes that still exist. */
729 if (replaced_call_placeholder)
732 /* This information will be invalid after inline expansion. Kill it now. */
733 free_basic_block_vars (0);