This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: tail call optimizations
- To: gcc-patches at gcc dot gnu dot org
- Subject: Re: tail call optimizations
- From: Richard Henderson <rth at cygnus dot com>
- Date: Mon, 13 Mar 2000 14:27:44 -0800
- References: <20000312185224.A5710@cygnus.com>
On Sun, Mar 12, 2000 at 06:52:24PM -0800, Richard Henderson wrote:
> There is much room for improvement. Jeff did the original work for
> PA and MIPS; code generation for Alpha must be slightly different,
> because functions returning a value are not identified as possible
> tail-call sites. The code that should have noticed is diked out
> with a "needs bullet-proofing" comment. But calls to void functions
> are properly transformed, so one can at least experiment.
Here's an incremental patch to get tail calls with a return
value properly optimized.
Still working on getting x86 to bootstrap...
r~
* sibcall.c (skip_copy_from_return_value): Remove.
(identify_call_return_value): New.
(skip_copy_to_return_value): New args hardret, softret. Validate
a copy into the return register.
(optimize_sibling_and_tail_recursive_call): Use them.
*** sibcall.c.orig Mon Mar 13 11:36:55 2000
--- sibcall.c Mon Mar 13 12:26:04 2000
*************** Boston, MA 02111-1307, USA. */
*** 32,41 ****
#include "output.h"
#include "except.h"
! #if 0
! static rtx skip_copy_from_return_value PARAMS ((rtx));
! static rtx skip_copy_to_return_value PARAMS ((rtx));
! #endif
static rtx skip_use_of_return_value PARAMS ((rtx, enum rtx_code));
static rtx skip_stack_adjustment PARAMS ((rtx));
static rtx skip_jump_insn PARAMS ((rtx));
--- 32,39 ----
#include "output.h"
#include "except.h"
! static int identify_call_return_value PARAMS ((rtx, rtx *, rtx *));
! static rtx skip_copy_to_return_value PARAMS ((rtx, rtx, rtx));
static rtx skip_use_of_return_value PARAMS ((rtx, enum rtx_code));
static rtx skip_stack_adjustment PARAMS ((rtx));
static rtx skip_jump_insn PARAMS ((rtx));
*************** static int uses_addressof PARAMS ((rtx)
*** 43,113 ****
static int sequence_uses_addressof PARAMS ((rtx));
static void purge_reg_equiv_notes PARAMS ((void));
! #if 0
! /* If the first real insn after ORIG_INSN copies from this function's
! return value, then return the insn which performs the copy. Otherwise
! return ORIG_INSN. */
! static rtx
! skip_copy_from_return_value (orig_insn)
! rtx orig_insn;
! {
! rtx insn, set = NULL_RTX;
! insn = next_nonnote_insn (orig_insn);
! if (insn)
! set = single_set (insn);
! /* The source must be the same as the current function's return value to
! ensure that any return value is put in the same place by the current
! function and the function we're calling. The destination register
! must be a pseudo. */
if (insn
! && set
! && SET_SRC (set) == current_function_return_rtx
! && REG_P (SET_DEST (set))
! && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
! return insn;
! /* It did not look like a copy of the return value, so return the
! same insn we were passed. */
! return orig_insn;
!
}
/* If the first real insn after ORIG_INSN copies to this function's
! return value, then return the insn which performs the copy. Otherwise
! return ORIG_INSN. */
static rtx
! skip_copy_to_return_value (orig_insn)
rtx orig_insn;
{
rtx insn, set = NULL_RTX;
insn = next_nonnote_insn (orig_insn);
! if (insn)
! set = single_set (insn);
! /* The source must be the same as the current function's return value to
! ensure that any return value is put in the same place by the current
! function and the function we're calling. The destination register
! must be a pseudo. */
! if (insn
! && set
! && SET_DEST (set) == current_function_return_rtx
! && REG_P (SET_SRC (set))
! && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
return insn;
/* It did not look like a copy of the return value, so return the
same insn we were passed. */
return orig_insn;
-
}
- #endif
/* If the first real insn after ORIG_INSN is a CODE of this function's return
value, return insn. Otherwise return ORIG_INSN. */
--- 41,155 ----
static int sequence_uses_addressof PARAMS ((rtx));
static void purge_reg_equiv_notes PARAMS ((void));
! /* Examine a CALL_PLACEHOLDER pattern and determine where the call's
! return value is located. P_HARD_RETURN receives the hard register
! that the function used; P_SOFT_RETURN receives the pseudo register
! that the sequence used. Return non-zero if the values were located. */
! static int
! identify_call_return_value (cp, p_hard_return, p_soft_return)
! rtx cp;
! rtx *p_hard_return, *p_soft_return;
! {
! rtx insn, set, hard, soft;
!
! /* Search forward through the "normal" call sequence to the CALL insn. */
! insn = XEXP (cp, 0);
! while (GET_CODE (insn) != CALL_INSN)
! insn = NEXT_INSN (insn);
!
! /* Assume the pattern is (set (dest) (call ...)), or that the first
! member of a parallel is. This is the hard return register used
! by the function. */
! if (GET_CODE (PATTERN (insn)) == SET
! && GET_CODE (SET_SRC (PATTERN (insn))) == CALL)
! hard = SET_DEST (PATTERN (insn));
! else if (GET_CODE (PATTERN (insn)) == PARALLEL
! && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
! && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == CALL)
! hard = SET_DEST (XVECEXP (PATTERN (insn), 0, 0));
! else
! return 0;
! /* If we didn't get a single hard register (e.g. a parallel), give up. */
! if (GET_CODE (hard) != REG)
! return 0;
!
! /* If there's nothing after, there's no soft return value. */
! insn = NEXT_INSN (insn);
! if (! insn)
! return 0;
!
! /* We're looking for a source of the hard return register. */
! set = single_set (insn);
! if (! set || SET_SRC (set) != hard)
! return 0;
! soft = SET_DEST (set);
! insn = NEXT_INSN (insn);
! /* Allow this first destination to be copied to a second register,
! as might happen if the first register wasn't the particular pseudo
! we'd been expecting. */
if (insn
! && (set = single_set (insn)) != NULL_RTX
! && SET_SRC (set) == soft)
! {
! soft = SET_DEST (set);
! insn = NEXT_INSN (insn);
! }
! /* Don't fool with anything but pseudo registers. */
! if (GET_CODE (soft) != REG || REGNO (soft) < FIRST_PSEUDO_REGISTER)
! return 0;
!
! /* This value must not be modified before the end of the sequence. */
! if (reg_set_between_p (soft, insn, NULL_RTX))
! return 0;
!
! *p_hard_return = hard;
! *p_soft_return = soft;
!
! return 1;
}
/* If the first real insn after ORIG_INSN copies to this function's
! return value from RETVAL, then return the insn which performs the
! copy. Otherwise return ORIG_INSN. */
static rtx
! skip_copy_to_return_value (orig_insn, hardret, softret)
rtx orig_insn;
+ rtx hardret, softret;
{
rtx insn, set = NULL_RTX;
insn = next_nonnote_insn (orig_insn);
+ if (! insn)
+ return orig_insn;
! set = single_set (insn);
! if (! set)
! return orig_insn;
!
! /* The destination must be the same as the called function's return
! value to ensure that any return value is put in the same place by the
! current function and the function we're calling.
!
! Further, the source must be the same as the pseudo into which the
! called function's return value was copied. Otherwise we're returning
! some other value. */
! if (SET_DEST (set) == current_function_return_rtx
! && REG_P (SET_DEST (set))
! && REGNO (SET_DEST (set)) == REGNO (hardret)
! && SET_SRC (set) == softret)
return insn;
/* It did not look like a copy of the return value, so return the
same insn we were passed. */
return orig_insn;
}
/* If the first real insn after ORIG_INSN is a CODE of this function's return
value, return insn. Otherwise return ORIG_INSN. */
*************** skip_stack_adjustment (orig_insn)
*** 161,167 ****
/* It did not look like a copy of the return value, so return the
same insn we were passed. */
return orig_insn;
-
}
/* Search SEQ for any block notes and emit-emit them before WHERE.
--- 203,208 ----
*************** optimize_sibling_and_tail_recursive_call
*** 440,446 ****
int sibcall = (XEXP (PATTERN (insn), 1) != NULL_RTX);
int tailrecursion = (XEXP (PATTERN (insn), 2) != NULL_RTX);
basic_block succ_block, call_block;
! rtx temp;
/* We must be careful with stack slots which are live at
potential optimization sites.
--- 481,487 ----
int sibcall = (XEXP (PATTERN (insn), 1) != NULL_RTX);
int tailrecursion = (XEXP (PATTERN (insn), 2) != NULL_RTX);
basic_block succ_block, call_block;
! rtx temp, hardret, softret;
/* We must be careful with stack slots which are live at
potential optimization sites.
*************** optimize_sibling_and_tail_recursive_call
*** 479,507 ****
goto failure;
/* If the call was the end of the block, then we're OK. */
! if (insn == call_block->end)
! goto success;
!
! #if 0
! /* Skip over copying the return value from a hard reg into a
! pseudo.
!
! ??? Need to bullet proof this more. This is only valid if we
! return with no value (pseudo was dead), or we immediately copy
! the pseudo back to the return register, then return. */
! temp = skip_copy_from_return_value (insn);
if (temp == call_block->end)
goto success;
! /* ??? Need to bullet proof this more. This is only valid if the
! source register is the return value from this call. */
! temp = skip_copy_to_return_value (insn);
! if (temp == call_block->end)
! goto success;
! #endif
!
/* Skip over a CLOBBER of the return value (as a hard reg). */
! temp = skip_use_of_return_value (insn, CLOBBER);
if (temp == call_block->end)
goto success;
--- 520,540 ----
goto failure;
/* If the call was the end of the block, then we're OK. */
! temp = insn;
if (temp == call_block->end)
goto success;
! /* Skip over copying from the call's return value pseudo into
! this function's hard return register. */
! if (identify_call_return_value (PATTERN (insn), &hardret, &softret))
! {
! temp = skip_copy_to_return_value (temp, hardret, softret);
! if (temp == call_block->end)
! goto success;
! }
!
/* Skip over a CLOBBER of the return value (as a hard reg). */
! temp = skip_use_of_return_value (temp, CLOBBER);
if (temp == call_block->end)
goto success;