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
));
47 /* Examine a CALL_PLACEHOLDER pattern and determine where the call's
48 return value is located. P_HARD_RETURN receives the hard register
49 that the function used; P_SOFT_RETURN receives the pseudo register
50 that the sequence used. Return non-zero if the values were located. */
53 identify_call_return_value (cp
, p_hard_return
, p_soft_return
)
55 rtx
*p_hard_return
, *p_soft_return
;
57 rtx insn
, set
, hard
, soft
;
60 /* Search backward through the "normal" call sequence to the CALL insn. */
61 while (NEXT_INSN (insn
))
62 insn
= NEXT_INSN (insn
);
63 while (GET_CODE (insn
) != CALL_INSN
)
64 insn
= PREV_INSN (insn
);
66 /* Assume the pattern is (set (dest) (call ...)), or that the first
67 member of a parallel is. This is the hard return register used
69 if (GET_CODE (PATTERN (insn
)) == SET
70 && GET_CODE (SET_SRC (PATTERN (insn
))) == CALL
)
71 hard
= SET_DEST (PATTERN (insn
));
72 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
73 && GET_CODE (XVECEXP (PATTERN (insn
), 0, 0)) == SET
74 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn
), 0, 0))) == CALL
)
75 hard
= SET_DEST (XVECEXP (PATTERN (insn
), 0, 0));
79 /* If we didn't get a single hard register (e.g. a parallel), give up. */
80 if (GET_CODE (hard
) != REG
)
83 /* Stack adjustment done after call may appear here. */
84 insn
= skip_stack_adjustment (insn
);
88 /* Restore of GP register may appear here. */
89 insn
= skip_pic_restore (insn
);
93 /* If there's nothing after, there's no soft return value. */
94 insn
= NEXT_INSN (insn
);
98 /* We're looking for a source of the hard return register. */
99 set
= single_set (insn
);
100 if (! set
|| SET_SRC (set
) != hard
)
103 soft
= SET_DEST (set
);
104 insn
= NEXT_INSN (insn
);
106 /* Allow this first destination to be copied to a second register,
107 as might happen if the first register wasn't the particular pseudo
108 we'd been expecting. */
110 && (set
= single_set (insn
)) != NULL_RTX
111 && SET_SRC (set
) == soft
)
113 soft
= SET_DEST (set
);
114 insn
= NEXT_INSN (insn
);
117 /* Don't fool with anything but pseudo registers. */
118 if (GET_CODE (soft
) != REG
|| REGNO (soft
) < FIRST_PSEUDO_REGISTER
)
121 /* This value must not be modified before the end of the sequence. */
122 if (reg_set_between_p (soft
, insn
, NULL_RTX
))
125 *p_hard_return
= hard
;
126 *p_soft_return
= soft
;
131 /* If the first real insn after ORIG_INSN copies to this function's
132 return value from RETVAL, then return the insn which performs the
133 copy. Otherwise return ORIG_INSN. */
136 skip_copy_to_return_value (orig_insn
)
139 rtx insn
, set
= NULL_RTX
;
140 rtx hardret
, softret
;
142 /* If there is no return value, we have nothing to do. */
143 if (! identify_call_return_value (PATTERN (orig_insn
), &hardret
, &softret
))
146 insn
= next_nonnote_insn (orig_insn
);
150 set
= single_set (insn
);
154 /* The destination must be the same as the called function's return
155 value to ensure that any return value is put in the same place by the
156 current function and the function we're calling.
158 Further, the source must be the same as the pseudo into which the
159 called function's return value was copied. Otherwise we're returning
162 #ifndef OUTGOING_REGNO
163 #define OUTGOING_REGNO(N) (N)
166 if (SET_DEST (set
) == current_function_return_rtx
167 && REG_P (SET_DEST (set
))
168 && OUTGOING_REGNO (REGNO (SET_DEST (set
))) == REGNO (hardret
)
169 && SET_SRC (set
) == softret
)
172 /* It did not look like a copy of the return value, so return the
173 same insn we were passed. */
177 /* If the first real insn after ORIG_INSN is a CODE of this function's return
178 value, return insn. Otherwise return ORIG_INSN. */
181 skip_use_of_return_value (orig_insn
, code
)
187 insn
= next_nonnote_insn (orig_insn
);
190 && GET_CODE (insn
) == INSN
191 && GET_CODE (PATTERN (insn
)) == code
192 && (XEXP (PATTERN (insn
), 0) == current_function_return_rtx
193 || XEXP (PATTERN (insn
), 0) == const0_rtx
))
199 /* If the first real insn after ORIG_INSN adjusts the stack pointer
200 by a constant, return the insn with the stack pointer adjustment.
201 Otherwise return ORIG_INSN. */
204 skip_stack_adjustment (orig_insn
)
207 rtx insn
, set
= NULL_RTX
;
209 insn
= next_nonnote_insn (orig_insn
);
212 set
= single_set (insn
);
216 && GET_CODE (SET_SRC (set
)) == PLUS
217 && XEXP (SET_SRC (set
), 0) == stack_pointer_rtx
218 && GET_CODE (XEXP (SET_SRC (set
), 1)) == CONST_INT
219 && SET_DEST (set
) == stack_pointer_rtx
)
225 /* If the first real insn after ORIG_INSN sets the pic register,
226 return it. Otherwise return ORIG_INSN. */
229 skip_pic_restore (orig_insn
)
232 rtx insn
, set
= NULL_RTX
;
234 insn
= next_nonnote_insn (orig_insn
);
237 set
= single_set (insn
);
239 if (insn
&& set
&& SET_DEST (set
) == pic_offset_table_rtx
)
245 /* If the first real insn after ORIG_INSN is a jump, return the JUMP_INSN.
246 Otherwise return ORIG_INSN. */
249 skip_jump_insn (orig_insn
)
254 insn
= next_nonnote_insn (orig_insn
);
257 && GET_CODE (insn
) == JUMP_INSN
258 && any_uncondjump_p (insn
))
264 /* Using the above functions, see if INSN, skipping any of the above,
265 goes all the way to END, the end of a basic block. Return 1 if so. */
268 call_ends_block_p (insn
, end
)
272 /* END might be a note, so get the last nonnote insn of the block. */
273 end
= next_nonnote_insn (PREV_INSN (end
));
275 /* If the call was the end of the block, then we're OK. */
279 /* Skip over copying from the call's return value pseudo into
280 this function's hard return register and if that's the end
281 of the block, we're OK. */
282 insn
= skip_copy_to_return_value (insn
);
286 /* Skip any stack adjustment. */
287 insn
= skip_stack_adjustment (insn
);
291 /* Skip over a CLOBBER of the return value as a hard reg. */
292 insn
= skip_use_of_return_value (insn
, CLOBBER
);
296 /* Skip over a USE of the return value (as a hard reg). */
297 insn
= skip_use_of_return_value (insn
, USE
);
301 /* Skip over a JUMP_INSN at the end of the block. If that doesn't end the
302 block, the original CALL_INSN didn't. */
303 insn
= skip_jump_insn (insn
);
307 /* Scan the rtx X for ADDRESSOF expressions or
308 current_function_internal_arg_pointer registers.
309 Return nonzero if an ADDRESSOF or current_function_internal_arg_pointer
310 is found outside of some MEM expression, else return zero. */
325 if (code
== ADDRESSOF
|| x
== current_function_internal_arg_pointer
)
331 /* Scan all subexpressions. */
332 fmt
= GET_RTX_FORMAT (code
);
333 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++, fmt
++)
337 if (uses_addressof (XEXP (x
, i
)))
340 else if (*fmt
== 'E')
342 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
343 if (uses_addressof (XVECEXP (x
, i
, j
)))
350 /* Scan the sequence of insns in SEQ to see if any have an ADDRESSOF
351 rtl expression or current_function_internal_arg_pointer occurences
352 not enclosed within a MEM. If an ADDRESSOF expression or
353 current_function_internal_arg_pointer is found, return nonzero, otherwise
356 This function handles CALL_PLACEHOLDERs which contain multiple sequences
360 sequence_uses_addressof (seq
)
365 for (insn
= seq
; insn
; insn
= NEXT_INSN (insn
))
368 /* If this is a CALL_PLACEHOLDER, then recursively call ourselves
369 with each nonempty sequence attached to the CALL_PLACEHOLDER. */
370 if (GET_CODE (insn
) == CALL_INSN
371 && GET_CODE (PATTERN (insn
)) == CALL_PLACEHOLDER
)
373 if (XEXP (PATTERN (insn
), 0) != NULL_RTX
374 && sequence_uses_addressof (XEXP (PATTERN (insn
), 0)))
376 if (XEXP (PATTERN (insn
), 1) != NULL_RTX
377 && sequence_uses_addressof (XEXP (PATTERN (insn
), 1)))
379 if (XEXP (PATTERN (insn
), 2) != NULL_RTX
380 && sequence_uses_addressof (XEXP (PATTERN (insn
), 2)))
383 else if (uses_addressof (PATTERN (insn
))
384 || (REG_NOTES (insn
) && uses_addressof (REG_NOTES (insn
))))
390 /* Remove all REG_EQUIV notes found in the insn chain. */
393 purge_reg_equiv_notes ()
397 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
401 rtx note
= find_reg_note (insn
, REG_EQUIV
, 0);
404 /* Remove the note and keep looking at the notes for
406 remove_note (insn
, note
);
414 /* Clear RTX_UNCHANGING_P flag of incoming argument MEMs. */
417 purge_mem_unchanging_flag (x
)
431 if (RTX_UNCHANGING_P (x
)
432 && (XEXP (x
, 0) == current_function_internal_arg_pointer
433 || (GET_CODE (XEXP (x
, 0)) == PLUS
434 && XEXP (XEXP (x
, 0), 0) ==
435 current_function_internal_arg_pointer
436 && GET_CODE (XEXP (XEXP (x
, 0), 1)) == CONST_INT
)))
437 RTX_UNCHANGING_P (x
) = 0;
441 /* Scan all subexpressions. */
442 fmt
= GET_RTX_FORMAT (code
);
443 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++, fmt
++)
446 purge_mem_unchanging_flag (XEXP (x
, i
));
447 else if (*fmt
== 'E')
448 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
449 purge_mem_unchanging_flag (XVECEXP (x
, i
, j
));
453 /* Replace the CALL_PLACEHOLDER with one of its children. INSN should be
454 the CALL_PLACEHOLDER insn; USE tells which child to use. */
457 replace_call_placeholder (insn
, use
)
461 if (use
== sibcall_use_tail_recursion
)
462 emit_insns_before (XEXP (PATTERN (insn
), 2), insn
);
463 else if (use
== sibcall_use_sibcall
)
464 emit_insns_before (XEXP (PATTERN (insn
), 1), insn
);
465 else if (use
== sibcall_use_normal
)
466 emit_insns_before (XEXP (PATTERN (insn
), 0), insn
);
470 /* Turn off LABEL_PRESERVE_P for the tail recursion label if it
471 exists. We only had to set it long enough to keep the jump
472 pass above from deleting it as unused. */
473 if (XEXP (PATTERN (insn
), 3))
474 LABEL_PRESERVE_P (XEXP (PATTERN (insn
), 3)) = 0;
476 /* "Delete" the placeholder insn. */
477 PUT_CODE (insn
, NOTE
);
478 NOTE_SOURCE_FILE (insn
) = 0;
479 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
482 /* Given a (possibly empty) set of potential sibling or tail recursion call
483 sites, determine if optimization is possible.
485 Potential sibling or tail recursion calls are marked with CALL_PLACEHOLDER
486 insns. The CALL_PLACEHOLDER insn holds chains of insns to implement a
487 normal call, sibling call or tail recursive call.
489 Replace the CALL_PLACEHOLDER with an appropriate insn chain. */
492 optimize_sibling_and_tail_recursive_calls ()
495 basic_block alternate_exit
= EXIT_BLOCK_PTR
;
496 int current_function_uses_addressof
;
497 int successful_sibling_call
= 0;
498 int replaced_call_placeholder
= 0;
501 insns
= get_insns ();
503 /* We do not perform these calls when flag_exceptions is true, so this
504 is probably a NOP at the current time. However, we may want to support
505 sibling and tail recursion optimizations in the future, so let's plan
506 ahead and find all the EH labels. */
507 find_exception_handler_labels ();
509 /* Run a jump optimization pass to clean up the CFG. We primarily want
510 this to thread jumps so that it is obvious which blocks jump to the
512 jump_optimize_minimal (insns
);
514 /* We need cfg information to determine which blocks are succeeded
515 only by the epilogue. */
516 find_basic_blocks (insns
, max_reg_num (), 0);
519 /* If there are no basic blocks, then there is nothing to do. */
520 if (n_basic_blocks
== 0)
523 /* Find the exit block.
525 It is possible that we have blocks which can reach the exit block
526 directly. However, most of the time a block will jump (or fall into)
527 N_BASIC_BLOCKS - 1, which in turn falls into the exit block. */
528 for (e
= EXIT_BLOCK_PTR
->pred
;
529 e
&& alternate_exit
== EXIT_BLOCK_PTR
;
534 if (e
->dest
!= EXIT_BLOCK_PTR
|| e
->succ_next
!= NULL
)
537 /* Walk forwards through the last normal block and see if it
538 does nothing except fall into the exit block. */
539 for (insn
= BLOCK_HEAD (n_basic_blocks
- 1);
541 insn
= NEXT_INSN (insn
))
543 /* This should only happen once, at the start of this block. */
544 if (GET_CODE (insn
) == CODE_LABEL
)
547 if (GET_CODE (insn
) == NOTE
)
550 if (GET_CODE (insn
) == INSN
551 && GET_CODE (PATTERN (insn
)) == USE
)
557 /* If INSN is zero, then the search walked all the way through the
558 block without hitting anything interesting. This block is a
559 valid alternate exit block. */
561 alternate_exit
= e
->src
;
564 /* If the function uses ADDRESSOF, we can't (easily) determine
565 at this point if the value will end up on the stack. */
566 current_function_uses_addressof
= sequence_uses_addressof (insns
);
568 /* Walk the insn chain and find any CALL_PLACEHOLDER insns. We need to
569 select one of the insn sequences attached to each CALL_PLACEHOLDER.
571 The different sequences represent different ways to implement the call,
572 ie, tail recursion, sibling call or normal call.
574 Since we do not create nested CALL_PLACEHOLDERs, the scan
575 continues with the insn that was after a replaced CALL_PLACEHOLDER;
576 we don't rescan the replacement insns. */
577 for (insn
= insns
; insn
; insn
= NEXT_INSN (insn
))
579 if (GET_CODE (insn
) == CALL_INSN
580 && GET_CODE (PATTERN (insn
)) == CALL_PLACEHOLDER
)
582 int sibcall
= (XEXP (PATTERN (insn
), 1) != NULL_RTX
);
583 int tailrecursion
= (XEXP (PATTERN (insn
), 2) != NULL_RTX
);
584 basic_block call_block
= BLOCK_FOR_INSN (insn
);
586 /* alloca (until we have stack slot life analysis) inhibits
587 sibling call optimizations, but not tail recursion.
588 Similarly if we use varargs or stdarg since they implicitly
589 may take the address of an argument. */
590 if (current_function_calls_alloca
591 || current_function_varargs
|| current_function_stdarg
)
594 /* See if there are any reasons we can't perform either sibling or
595 tail call optimizations. We must be careful with stack slots
596 which are live at potential optimization sites. ?!? The first
597 test is overly conservative and should be replaced. */
599 /* Can't take address of local var if used by recursive call. */
600 || current_function_uses_addressof
601 /* Can't if more than one successor or single successor is not
602 exit block. These two tests prevent tail call optimization
603 in the presense of active exception handlers. */
604 || call_block
->succ
== NULL
605 || call_block
->succ
->succ_next
!= NULL
606 || (call_block
->succ
->dest
!= EXIT_BLOCK_PTR
607 && call_block
->succ
->dest
!= alternate_exit
)
608 /* If this call doesn't end the block, there are operations at
609 the end of the block which we must execute after returning. */
610 || ! call_ends_block_p (insn
, call_block
->end
))
611 sibcall
= 0, tailrecursion
= 0;
613 /* Select a set of insns to implement the call and emit them.
614 Tail recursion is the most efficient, so select it over
615 a tail/sibling call. */
617 successful_sibling_call
= 1;
619 replaced_call_placeholder
= 1;
620 replace_call_placeholder (insn
,
622 ? sibcall_use_tail_recursion
624 ? sibcall_use_sibcall
625 : sibcall_use_normal
);
629 if (successful_sibling_call
)
633 /* A sibling call sequence invalidates any REG_EQUIV notes made for
634 this function's incoming arguments.
636 At the start of RTL generation we know the only REG_EQUIV notes
637 in the rtl chain are those for incoming arguments, so we can safely
638 flush any REG_EQUIV note.
640 This is (slight) overkill. We could keep track of the highest
641 argument we clobber and be more selective in removing notes, but it
642 does not seem to be worth the effort. */
643 purge_reg_equiv_notes ();
645 /* A sibling call sequence also may invalidate RTX_UNCHANGING_P
646 flag of some incoming arguments MEM RTLs, because it can write into
647 those slots. We clear all those bits now.
649 This is (slight) overkill, we could keep track of which arguments
650 we actually write into. */
651 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
653 if (GET_CODE (insn
) == NOTE
)
655 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_FUNCTION_BEG
)
658 else if (INSN_P (insn
))
659 purge_mem_unchanging_flag (PATTERN (insn
));
663 /* There may have been NOTE_INSN_BLOCK_{BEGIN,END} notes in the
664 CALL_PLACEHOLDER alternatives that we didn't emit. Rebuild the
665 lexical block tree to correspond to the notes that still exist. */
666 if (replaced_call_placeholder
)
669 /* This information will be invalid after inline expansion. Kill it now. */
670 free_basic_block_vars (0);