This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: tail call optimizations


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;
  

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]