re-apply sibcall replacement

Jan Hubicka jh@suse.cz
Wed Dec 17 18:59:00 GMT 2003


Hi,
as requesed by Diego, here is updated version of the tail call
ellimination patch.  It passed enable/disable checking bootstrap &
regtest on i686-pc-gnu-linux.  The previous version was tested on i386,
x86_64 and ia64 too and the change is really trivial (update of conflict
tree-dump.c and tree.h).  Literarly same version of the patch has been
tested on Alpha a week ago to.  I will give it testing on other
platforms tonight too.

2003-11-18  Jan Hubicka  <jh@suse.cz>
	* Makefile.in (sibcall.o): Kill.
	(tree-tailcall.o): Add except.h dependency
	* sibcall.c: Kill.
	(purge_reg_equiv_notes, purge_mem_unchanging_flag): Move to ...
	* calls.c (purge_reg_equiv_notes, purge_mem_unchanging_flag) ... here.
	(expand_call): Do not produce placeholders; do not deal with tail
	recursion; set tail_call_emit.
	(fixup_tail_calls): New.
	* expr.h (fixup_tail_calls): Declare.
	* toplev.c (rest_of_handle_sibling_calls): Kill.
	(rest_of_compialtion): Do not use rest_of_handle_sibling_calls;
	call fixup_tail_calls.
	* tree-dump.c (dump_files): Add tail2
	* tree-flow.h (tree_optimize_tail_calls): Update prototype.
	* tree-optimize.c (optimize_function_tree): Do tail optimization twice.
	* tree-tailcall.c: Inlucde except.h
	(suitable_for_tail_call_opt_p): New.
	(optimize_tail_call): Add opt_tailcalls argument; optimize tailcalls.
	(tree_optimize_tail_calls): Add opt_tailcalls/pass arguments.
	* tree.h (CALL_EXPR_TAILCALL): New.
	(tree_dump_index): Add tail2
	* function.h (struct function): Add tail_call_emit field.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.157
diff -c -3 -p -r1.903.2.157 Makefile.in
*** Makefile.in	15 Dec 2003 22:58:33 -0000	1.903.2.157
--- Makefile.in	16 Dec 2003 22:50:53 -0000
*************** OBJS-common = \
*** 896,902 ****
   real.o recog.o reg-stack.o regclass.o regmove.o regrename.o		   \
   reload.o reload1.o reorg.o resource.o rtl.o rtlanal.o rtl-error.o	   \
   sbitmap.o sched-deps.o sched-ebb.o sched-rgn.o sched-vis.o sdbout.o	   \
!  sibcall.o simplify-rtx.o sreal.o stmt.o stor-layout.o stringpool.o 	   \
   targhooks.o timevar.o toplev.o tracer.o tree.o tree-dump.o unroll.o	   \
   varasm.o varray.o version.o vmsdbgout.o xcoffout.o alloc-pool.o	   \
   et-forest.o cfghooks.o bt-load.o pretty-print.o $(GGC) web.o
--- 896,902 ----
   real.o recog.o reg-stack.o regclass.o regmove.o regrename.o		   \
   reload.o reload1.o reorg.o resource.o rtl.o rtlanal.o rtl-error.o	   \
   sbitmap.o sched-deps.o sched-ebb.o sched-rgn.o sched-vis.o sdbout.o	   \
!  simplify-rtx.o sreal.o stmt.o stor-layout.o stringpool.o 	 	  \
   targhooks.o timevar.o toplev.o tracer.o tree.o tree-dump.o unroll.o	   \
   varasm.o varray.o version.o vmsdbgout.o xcoffout.o alloc-pool.o	   \
   et-forest.o cfghooks.o bt-load.o pretty-print.o $(GGC) web.o
*************** tree-cfg.o : tree-cfg.c $(TREE_FLOW_H) $
*** 1578,1584 ****
     $(TREE_DUMP_H) except.h langhooks.h cfgloop.h gt-tree-cfg.h
  tree-tailcall.o : tree-tailcall.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
     $(RTL_H) $(TREE_H) $(TM_P_H) function.h $(TM_H) coretypes.h \
!    $(TREE_DUMP_H) diagnostic.h
  tree-iterator.o : tree-iterator.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \
     coretypes.h $(GGC_H) tree-iterator.h tree-simple.h gt-tree-iterator.h
  tree-dfa.o : tree-dfa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
--- 1578,1584 ----
     $(TREE_DUMP_H) except.h langhooks.h cfgloop.h gt-tree-cfg.h
  tree-tailcall.o : tree-tailcall.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
     $(RTL_H) $(TREE_H) $(TM_P_H) function.h $(TM_H) coretypes.h \
!    $(TREE_DUMP_H) diagnostic.h except.h
  tree-iterator.o : tree-iterator.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \
     coretypes.h $(GGC_H) tree-iterator.h tree-simple.h gt-tree-iterator.h
  tree-dfa.o : tree-dfa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
*************** web.o : web.c $(CONFIG_H) $(SYSTEM_H) co
*** 1780,1787 ****
  gcse.o : gcse.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(REGS_H) \
     hard-reg-set.h flags.h real.h insn-config.h $(GGC_H) $(RECOG_H) $(EXPR_H) \
     $(BASIC_BLOCK_H) function.h output.h toplev.h $(TM_P_H) $(PARAMS_H) except.h gt-gcse.h
- sibcall.o : sibcall.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(REGS_H) \
-    function.h hard-reg-set.h flags.h insn-config.h $(RECOG_H) $(BASIC_BLOCK_H)
  resource.o : resource.c $(CONFIG_H) $(RTL_H) hard-reg-set.h $(SYSTEM_H) coretypes.h \
     $(TM_H) $(BASIC_BLOCK_H) $(REGS_H) flags.h output.h resource.h function.h toplev.h \
     $(INSN_ATTR_H) except.h $(PARAMS_H) $(TM_P_H)
--- 1780,1785 ----
Index: calls.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/calls.c,v
retrieving revision 1.229.2.38
diff -c -3 -p -r1.229.2.38 calls.c
*** calls.c	25 Nov 2003 02:09:33 -0000	1.229.2.38
--- calls.c	16 Dec 2003 22:50:54 -0000
*************** shift_returned_value (tree type, rtx *va
*** 2062,2067 ****
--- 2062,2130 ----
    return false;
  }
  
+ /* Remove all REG_EQUIV notes found in the insn chain.  */
+ 
+ static void
+ purge_reg_equiv_notes (void)
+ {
+   rtx insn;
+ 
+   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+     {
+       while (1)
+ 	{
+ 	  rtx note = find_reg_note (insn, REG_EQUIV, 0);
+ 	  if (note)
+ 	    {
+ 	      /* Remove the note and keep looking at the notes for
+ 		 this insn.  */
+ 	      remove_note (insn, note);
+ 	      continue;
+ 	    }
+ 	  break;
+ 	}
+     }
+ }
+ 
+ /* Clear RTX_UNCHANGING_P flag of incoming argument MEMs.  */
+ 
+ static void
+ purge_mem_unchanging_flag (rtx x)
+ {
+   RTX_CODE code;
+   int i, j;
+   const char *fmt;
+ 
+   if (x == NULL_RTX)
+     return;
+ 
+   code = GET_CODE (x);
+ 
+   if (code == MEM)
+     {
+       if (RTX_UNCHANGING_P (x)
+ 	  && (XEXP (x, 0) == current_function_internal_arg_pointer
+ 	      || (GET_CODE (XEXP (x, 0)) == PLUS
+ 		  && XEXP (XEXP (x, 0), 0) ==
+ 		     current_function_internal_arg_pointer
+ 		  && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)))
+ 	RTX_UNCHANGING_P (x) = 0;
+       return;
+     }
+ 
+   /* Scan all subexpressions.  */
+   fmt = GET_RTX_FORMAT (code);
+   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
+     {
+       if (*fmt == 'e')
+ 	purge_mem_unchanging_flag (XEXP (x, i));
+       else if (*fmt == 'E')
+ 	for (j = 0; j < XVECLEN (x, i); j++)
+ 	  purge_mem_unchanging_flag (XVECEXP (x, i, j));
+     }
+ }
+ 
+ 
  /* Generate all the code for a function call
     and return an rtx for its value.
     Store the value in TARGET (specified as an rtx) if convenient.
*************** expand_call (tree exp, rtx target, int i
*** 2078,2088 ****
    tree actparms = TREE_OPERAND (exp, 1);
    /* RTX for the function to be called.  */
    rtx funexp;
-   /* Sequence of insns to perform a tail recursive "call".  */
-   rtx tail_recursion_insns = NULL_RTX;
    /* Sequence of insns to perform a normal "call".  */
    rtx normal_call_insns = NULL_RTX;
!   /* Sequence of insns to perform a tail recursive "call".  */
    rtx tail_call_insns = NULL_RTX;
    /* Data type of the function.  */
    tree funtype;
--- 2141,2149 ----
    tree actparms = TREE_OPERAND (exp, 1);
    /* RTX for the function to be called.  */
    rtx funexp;
    /* Sequence of insns to perform a normal "call".  */
    rtx normal_call_insns = NULL_RTX;
!   /* Sequence of insns to perform a tail "call".  */
    rtx tail_call_insns = NULL_RTX;
    /* Data type of the function.  */
    tree funtype;
*************** expand_call (tree exp, rtx target, int i
*** 2090,2098 ****
    /* Declaration of the function being called,
       or 0 if the function is computed (not known by name).  */
    tree fndecl = 0;
!   rtx insn;
!   int try_tail_call = 1;
!   int try_tail_recursion = 1;
    int pass;
  
    /* Register in which non-BLKmode value will be returned,
--- 2151,2157 ----
    /* Declaration of the function being called,
       or 0 if the function is computed (not known by name).  */
    tree fndecl = 0;
!   int try_tail_call = CALL_EXPR_TAILCALL (exp);
    int pass;
  
    /* Register in which non-BLKmode value will be returned,
*************** expand_call (tree exp, rtx target, int i
*** 2163,2169 ****
  #endif
  
    int initial_highest_arg_in_use = highest_outgoing_arg_in_use;
-   rtx temp_target = 0;
    char *initial_stack_usage_map = stack_usage_map;
  
    int old_stack_allocated;
--- 2222,2227 ----
*************** expand_call (tree exp, rtx target, int i
*** 2486,2498 ****
        || any_pending_cleanups ()
        || args_size.var
        || lookup_stmt_eh_region (exp) >= 0)
!     try_tail_call = try_tail_recursion = 0;
! 
!   /* Tail recursion fails, when we are not dealing with recursive calls.  */
!   if (!try_tail_recursion
!       || TREE_CODE (addr) != ADDR_EXPR
!       || TREE_OPERAND (addr, 0) != current_function_decl)
!     try_tail_recursion = 0;
  
    /*  Rest of purposes for tail call optimizations to fail.  */
    if (
--- 2544,2550 ----
        || any_pending_cleanups ()
        || args_size.var
        || lookup_stmt_eh_region (exp) >= 0)
!     try_tail_call = 0;
  
    /*  Rest of purposes for tail call optimizations to fail.  */
    if (
*************** expand_call (tree exp, rtx target, int i
*** 2530,2536 ****
        || !(*lang_hooks.decls.ok_for_sibcall) (fndecl))
      try_tail_call = 0;
  
!   if (try_tail_call || try_tail_recursion)
      {
        int end, inc;
        actparms = NULL_TREE;
--- 2582,2588 ----
        || !(*lang_hooks.decls.ok_for_sibcall) (fndecl))
      try_tail_call = 0;
  
!   if (try_tail_call)
      {
        int end, inc;
        actparms = NULL_TREE;
*************** expand_call (tree exp, rtx target, int i
*** 2565,2575 ****
        for (; i != end; i += inc)
  	{
            args[i].tree_value = fix_unsafe_tree (args[i].tree_value);
- 	  /* We need to build actparms for optimize_tail_recursion.  We can
- 	     safely trash away TREE_PURPOSE, since it is unused by this
- 	     function.  */
- 	  if (try_tail_recursion)
- 	    actparms = tree_cons (NULL_TREE, args[i].tree_value, actparms);
  	}
        /* Do the same for the function address if it is an expression.  */
        if (!fndecl)
--- 2617,2622 ----
*************** expand_call (tree exp, rtx target, int i
*** 2577,2626 ****
        /* Expanding one of those dangerous arguments could have added
  	 cleanups, but otherwise give it a whirl.  */
        if (any_pending_cleanups ())
! 	try_tail_call = try_tail_recursion = 0;
      }
  
-   /* Generate a tail recursion sequence when calling ourselves.  */
- 
-   if (try_tail_recursion)
-     {
-       /* We want to emit any pending stack adjustments before the tail
- 	 recursion "call".  That way we know any adjustment after the tail
- 	 recursion call can be ignored if we indeed use the tail recursion
- 	 call expansion.  */
-       int save_pending_stack_adjust = pending_stack_adjust;
-       int save_stack_pointer_delta = stack_pointer_delta;
- 
-       /* Emit any queued insns now; otherwise they would end up in
- 	 only one of the alternates.  */
-       emit_queue ();
- 
-       /* Use a new sequence to hold any RTL we generate.  We do not even
- 	 know if we will use this RTL yet.  The final decision can not be
- 	 made until after RTL generation for the entire function is
- 	 complete.  */
-       start_sequence ();
-       /* If expanding any of the arguments creates cleanups, we can't
- 	 do a tailcall.  So, we'll need to pop the pending cleanups
- 	 list.  If, however, all goes well, and there are no cleanups
- 	 then the call to expand_start_target_temps will have no
- 	 effect.  */
-       expand_start_target_temps ();
-       if (optimize_tail_recursion (actparms, get_last_insn ()))
- 	{
- 	  if (any_pending_cleanups ())
- 	    try_tail_call = try_tail_recursion = 0;
- 	  else
- 	    tail_recursion_insns = get_insns ();
- 	}
-       expand_end_target_temps ();
-       end_sequence ();
- 
-       /* Restore the original pending stack adjustment for the sibling and
- 	 normal call cases below.  */
-       pending_stack_adjust = save_pending_stack_adjust;
-       stack_pointer_delta = save_stack_pointer_delta;
-     }
  
    if (profile_arc_flag && (flags & ECF_FORK_OR_EXEC))
      {
--- 2624,2632 ----
        /* Expanding one of those dangerous arguments could have added
  	 cleanups, but otherwise give it a whirl.  */
        if (any_pending_cleanups ())
! 	try_tail_call = 0;
      }
  
  
    if (profile_arc_flag && (flags & ECF_FORK_OR_EXEC))
      {
*************** expand_call (tree exp, rtx target, int i
*** 2655,2661 ****
        int sibcall_failure = 0;
        /* We want to emit any pending stack adjustments before the tail
  	 recursion "call".  That way we know any adjustment after the tail
! 	 recursion call can be ignored if we indeed use the tail recursion
  	 call expansion.  */
        int save_pending_stack_adjust = 0;
        int save_stack_pointer_delta = 0;
--- 2661,2667 ----
        int sibcall_failure = 0;
        /* We want to emit any pending stack adjustments before the tail
  	 recursion "call".  That way we know any adjustment after the tail
! 	 recursion call can be ignored if we indeed use the tail 
  	 call expansion.  */
        int save_pending_stack_adjust = 0;
        int save_stack_pointer_delta = 0;
*************** expand_call (tree exp, rtx target, int i
*** 3261,3271 ****
  	 The Irix 6 ABI has examples of this.  */
        else if (GET_CODE (valreg) == PARALLEL)
  	{
! 	  /* Second condition is added because "target" is freed at the
! 	     the end of "pass0" for -O2 when call is made to
! 	     expand_end_target_temps ().  Its "in_use" flag has been set
! 	     to false, so allocate a new temp.  */
! 	  if (target == 0 || (pass == 1 && target == temp_target))
  	    {
  	      /* This will only be assigned once, so it can be readonly.  */
  	      tree nt = build_qualified_type (TREE_TYPE (exp),
--- 3267,3273 ----
  	 The Irix 6 ABI has examples of this.  */
        else if (GET_CODE (valreg) == PARALLEL)
  	{
! 	  if (target == 0)
  	    {
  	      /* This will only be assigned once, so it can be readonly.  */
  	      tree nt = build_qualified_type (TREE_TYPE (exp),
*************** expand_call (tree exp, rtx target, int i
*** 3273,3279 ****
  					       | TYPE_QUAL_CONST));
  
  	      target = assign_temp (nt, 0, 1, 1);
- 	      temp_target = target;
  	      preserve_temp_slots (target);
  	    }
  
--- 3275,3280 ----
*************** expand_call (tree exp, rtx target, int i
*** 3468,3515 ****
  	 zero out the sequence.  */
        if (sibcall_failure)
  	tail_call_insns = NULL_RTX;
      }
  
!   /* The function optimize_sibling_and_tail_recursive_calls doesn't
!      handle CALL_PLACEHOLDERs inside other CALL_PLACEHOLDERs.  This
!      can happen if the arguments to this function call an inline
!      function who's expansion contains another CALL_PLACEHOLDER.
! 
!      If there are any C_Ps in any of these sequences, replace them
!      with their normal call.  */
! 
!   for (insn = normal_call_insns; insn; insn = NEXT_INSN (insn))
!     if (GET_CODE (insn) == CALL_INSN
! 	&& GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
!       replace_call_placeholder (insn, sibcall_use_normal);
! 
!   for (insn = tail_call_insns; insn; insn = NEXT_INSN (insn))
!     if (GET_CODE (insn) == CALL_INSN
! 	&& GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
!       replace_call_placeholder (insn, sibcall_use_normal);
! 
!   for (insn = tail_recursion_insns; insn; insn = NEXT_INSN (insn))
!     if (GET_CODE (insn) == CALL_INSN
! 	&& GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
!       replace_call_placeholder (insn, sibcall_use_normal);
! 
!   /* If this was a potential tail recursion site, then emit a
!      CALL_PLACEHOLDER with the normal and the tail recursion streams.
!      One of them will be selected later.  */
!   if (tail_recursion_insns || tail_call_insns)
      {
!       /* The tail recursion label must be kept around.  We could expose
! 	 its use in the CALL_PLACEHOLDER, but that creates unwanted edges
! 	 and makes determining true tail recursion sites difficult.
! 
! 	 So we set LABEL_PRESERVE_P here, then clear it when we select
! 	 one of the call sequences after rtl generation is complete.  */
!       if (tail_recursion_insns)
! 	LABEL_PRESERVE_P (tail_recursion_label) = 1;
!       emit_call_insn (gen_rtx_CALL_PLACEHOLDER (VOIDmode, normal_call_insns,
! 						tail_call_insns,
! 						tail_recursion_insns,
! 						tail_recursion_label));
      }
    else
      emit_insn (normal_call_insns);
--- 3469,3484 ----
  	 zero out the sequence.  */
        if (sibcall_failure)
  	tail_call_insns = NULL_RTX;
+       else
+ 	break;
      }
  
!   /* If tail call production suceeded, we need to remove REG_EQUIV notes on
!      arguments too, as argument area is now clobbered by the call.  */
!   if (tail_call_insns)
      {
!       emit_insn (tail_call_insns);
!       cfun->tail_call_emit = true;
      }
    else
      emit_insn (normal_call_insns);
*************** expand_call (tree exp, rtx target, int i
*** 3528,3533 ****
--- 3497,3543 ----
      }
  
    return target;
+ }
+ 
+ /* A sibling call sequence invalidates any REG_EQUIV notes made for
+    this function's incoming arguments.
+ 
+    At the start of RTL generation we know the only REG_EQUIV notes
+    in the rtl chain are those for incoming arguments, so we can safely
+    flush any REG_EQUIV note.
+ 
+    This is (slight) overkill.  We could keep track of the highest
+    argument we clobber and be more selective in removing notes, but it
+    does not seem to be worth the effort.  */
+ void
+ fixup_tail_calls (void)
+ {
+   rtx insn;
+   tree arg;
+ 
+   purge_reg_equiv_notes ();
+ 
+   /* A sibling call sequence also may invalidate RTX_UNCHANGING_P
+      flag of some incoming arguments MEM RTLs, because it can write into
+      those slots.  We clear all those bits now.
+ 
+      This is (slight) overkill, we could keep track of which arguments
+      we actually write into.  */
+   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+     {
+       if (INSN_P (insn))
+ 	purge_mem_unchanging_flag (PATTERN (insn));
+     }
+ 
+   /* Similarly, invalidate RTX_UNCHANGING_P for any incoming
+      arguments passed in registers.  */
+   for (arg = DECL_ARGUMENTS (current_function_decl);
+        arg;
+        arg = TREE_CHAIN (arg))
+     {
+       if (REG_P (DECL_RTL (arg)))
+ 	RTX_UNCHANGING_P (DECL_RTL (arg)) = false;
+     }
  }
  
  /* Traverse an argument list in VALUES and expand all complex
Index: expr.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/expr.h,v
retrieving revision 1.117.2.21
diff -c -3 -p -r1.117.2.21 expr.h
*** expr.h	13 Nov 2003 02:37:52 -0000	1.117.2.21
--- expr.h	16 Dec 2003 22:50:54 -0000
*************** extern rtx prepare_call_address (rtx, tr
*** 568,573 ****
--- 568,575 ----
  
  extern rtx expand_call (tree, rtx, int);
  
+ extern void fixup_tail_calls (void);
+ 
  #ifdef TREE_CODE
  extern rtx expand_shift (enum tree_code, enum machine_mode, rtx, tree, rtx,
  			 int);
Index: function.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/function.h,v
retrieving revision 1.83.2.21
diff -c -3 -p -r1.83.2.21 function.h
*** function.h	7 Dec 2003 10:07:44 -0000	1.83.2.21
--- function.h	16 Dec 2003 22:50:54 -0000
*************** struct function GTY(())
*** 389,394 ****
--- 389,396 ----
    int preferred_stack_boundary;
    /* Set when the call to function itself has been emit.  */
    bool recursive_call_emit;
+   /* Set when the tail call has been produced.  */
+   bool tail_call_emit;
  
    /* Language-specific code can use this to store whatever it likes.  */
    struct language_function * language;
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.654.2.82
diff -c -3 -p -r1.654.2.82 toplev.c
*** toplev.c	6 Dec 2003 12:31:27 -0000	1.654.2.82
--- toplev.c	16 Dec 2003 22:50:54 -0000
*************** static void rest_of_handle_life (tree, r
*** 132,138 ****
  static void rest_of_handle_loop_optimize (tree, rtx);
  static void rest_of_handle_loop2 (tree, rtx);
  static void rest_of_handle_jump_bypass (tree, rtx);
- static void rest_of_handle_sibling_calls (rtx);
  static void rest_of_handle_null_pointer (tree, rtx);
  static void rest_of_handle_addressof (tree, rtx);
  static void rest_of_handle_cfg (tree, rtx);
--- 132,137 ----
*************** rest_of_handle_addressof (tree decl, rtx
*** 2587,2620 ****
    close_dump_file (DFI_addressof, print_rtl, insns);
  }
  
- /* We may have potential sibling or tail recursion sites.  Select one
-    (of possibly multiple) methods of performing the call.  */
- static void
- rest_of_handle_sibling_calls (rtx insns)
- {
-   rtx insn;
-   optimize_sibling_and_tail_recursive_calls ();
- 
-   /* Recompute the CFG as sibling optimization clobbers it randomly.  */
-   free_bb_for_insn ();
-   find_exception_handler_labels ();
-   rebuild_jump_labels (insns);
-   find_basic_blocks (insns, max_reg_num (), rtl_dump_file);
- 
-   /* There is pass ordering problem - we must lower NOTE_INSN_PREDICTION
-      notes before simplifying cfg and we must do lowering after sibcall
-      that unhides parts of RTL chain and cleans up the CFG.
- 
-      Until sibcall is replaced by tree-level optimizer, lets just
-      sweep away the NOTE_INSN_PREDICTION notes that leaked out.  */
-   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
-     if (GET_CODE (insn) == NOTE
- 	&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_PREDICTION)
-       delete_insn (insn);
- 
-   close_dump_file (DFI_sibling, print_rtl, get_insns ());
- }
- 
  /* Perform jump bypassing and control flow optimizations.  */
  static void
  rest_of_handle_jump_bypass (tree decl, rtx insns)
--- 2586,2591 ----
*************** rest_of_compilation (tree decl)
*** 3215,3224 ****
        timevar_pop (TV_BRANCH_PROB);
      }
  
-   if (flag_optimize_sibling_calls)
-     rest_of_handle_sibling_calls (insns);
- 
    timevar_pop (TV_JUMP);
  
    insn_locators_initialize ();
    /* Complete generation of exception handling code.  */
--- 3186,3195 ----
        timevar_pop (TV_BRANCH_PROB);
      }
  
    timevar_pop (TV_JUMP);
+ 
+   if (cfun->tail_call_emit)
+     fixup_tail_calls ();
  
    insn_locators_initialize ();
    /* Complete generation of exception handling code.  */
Index: tree-dump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dump.c,v
retrieving revision 1.6.2.60
diff -c -3 -p -r1.6.2.60 tree-dump.c
*** tree-dump.c	13 Dec 2003 07:20:36 -0000	1.6.2.60
--- tree-dump.c	16 Dec 2003 22:50:54 -0000
*************** static struct dump_file_info dump_files[
*** 667,673 ****
    {".loop", "tree-loop", 0, 0},
    {".mustalias", "tree-mustalias", 0, 0},
    {".ssa3", "tree-ssa3", 0, 0},
!   {".tail", "tree-tail", 0, 0},
    {".sra", "tree-sra", 0, 0},
    {".ssa4", "tree-ssa4", 0, 0},
    {".ccp", "tree-ccp", 0, 0},
--- 667,673 ----
    {".loop", "tree-loop", 0, 0},
    {".mustalias", "tree-mustalias", 0, 0},
    {".ssa3", "tree-ssa3", 0, 0},
!   {".tail1", "tree-tail1", 0, 0},
    {".sra", "tree-sra", 0, 0},
    {".ssa4", "tree-ssa4", 0, 0},
    {".ccp", "tree-ccp", 0, 0},
*************** static struct dump_file_info dump_files[
*** 676,681 ****
--- 676,682 ----
    {".dom2", "tree-dom2", 0, 0},
    {".ssa6", "tree-ssa6", 0, 0},
    {".dce2", "tree-dce2", 0, 0},
+   {".tail2", "tree-tail2", 0, 0},
    {".optimized", "tree-optimized", 0, 0},
    {".mudflap2", "tree-mudflap2", 0, 0},
    {".xml", "call-graph", 0, 0},
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.172
diff -c -3 -p -r1.1.4.172 tree-flow.h
*** tree-flow.h	16 Dec 2003 21:42:31 -0000	1.1.4.172
--- tree-flow.h	16 Dec 2003 22:50:54 -0000
*************** extern basic_block tree_split_edge (edge
*** 418,424 ****
  extern edge thread_edge (edge, basic_block);
  extern basic_block label_to_block (tree);
  extern bool cleanup_control_expr_graph (basic_block, block_stmt_iterator);
! extern void tree_optimize_tail_calls (void);
  extern basic_block tree_block_forwards_to (basic_block bb);
  extern void bsi_insert_on_edge (edge, tree);
  extern void bsi_commit_edge_inserts (bool, int *);
--- 418,424 ----
  extern edge thread_edge (edge, basic_block);
  extern basic_block label_to_block (tree);
  extern bool cleanup_control_expr_graph (basic_block, block_stmt_iterator);
! extern void tree_optimize_tail_calls (bool, enum tree_dump_index);
  extern basic_block tree_block_forwards_to (basic_block bb);
  extern void bsi_insert_on_edge (edge, tree);
  extern void bsi_commit_edge_inserts (bool, int *);
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.95
diff -c -3 -p -r1.1.4.95 tree-optimize.c
*** tree-optimize.c	15 Dec 2003 15:55:34 -0000	1.1.4.95
--- tree-optimize.c	16 Dec 2003 22:50:54 -0000
*************** optimize_function_tree (tree fndecl, tre
*** 163,169 ****
  	}
  
        /* Eliminate tail recursion calls.  */
!       tree_optimize_tail_calls ();
  
  #ifdef ENABLE_CHECKING
        verify_ssa ();
--- 163,169 ----
  	}
  
        /* Eliminate tail recursion calls.  */
!       tree_optimize_tail_calls (false, TDI_tail1);
  
  #ifdef ENABLE_CHECKING
        verify_ssa ();
*************** optimize_function_tree (tree fndecl, tre
*** 238,246 ****
  #endif
  	}
  
- #if 0
        /* Eliminate tail recursion calls and discover sibling calls.  */
        tree_optimize_tail_calls (true, TDI_tail2);
  #endif
  
  #ifdef ENABLE_CHECKING
--- 238,248 ----
  #endif
  	}
  
        /* Eliminate tail recursion calls and discover sibling calls.  */
        tree_optimize_tail_calls (true, TDI_tail2);
+ 
+ #ifdef ENABLE_CHECKING
+       verify_ssa ();
  #endif
  
  #ifdef ENABLE_CHECKING
Index: tree-tailcall.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-tailcall.c,v
retrieving revision 1.1.2.9
diff -c -3 -p -r1.1.2.9 tree-tailcall.c
*** tree-tailcall.c	18 Nov 2003 23:06:36 -0000	1.1.2.9
--- tree-tailcall.c	16 Dec 2003 22:50:55 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 31,36 ****
--- 31,37 ----
  #include "tree-flow.h"
  #include "tree-dump.h"
  #include "diagnostic.h"
+ #include "except.h"
  
  /* Dump files and flags.  */
  static FILE *dump_file;		/* CFG dump file. */
*************** struct tailcall
*** 57,63 ****
  };
  
  static bool suitable_for_tail_opt_p (void);
! static bool optimize_tail_call (struct tailcall *, bool *);
  static void eliminate_tail_call (struct tailcall *);
  static void find_tail_calls (basic_block, struct tailcall *, struct tailcall **);
  
--- 58,64 ----
  };
  
  static bool suitable_for_tail_opt_p (void);
! static bool optimize_tail_call (struct tailcall *, bool *, bool);
  static void eliminate_tail_call (struct tailcall *);
  static void find_tail_calls (basic_block, struct tailcall *, struct tailcall **);
  
*************** suitable_for_tail_opt_p (void)
*** 87,92 ****
--- 88,120 ----
  
    return true;
  }
+ /* Returns false when the function is not suitable for tail call optimization
+    from some reason (e.g. if it takes variable number of arguments).
+    This test must pass in addition to suitable_for_tail_opt_p in order to make
+    tail call discovery happen.  */
+ 
+ static bool
+ suitable_for_tail_call_opt_p (void)
+ {
+   /* alloca (until we have stack slot life analysis) inhibits
+      sibling call optimizations, but not tail recursion.  */
+   if (current_function_calls_alloca)
+     return false;
+ 
+   /* If we are using sjlj exceptions, we may need to add a call to
+      _Unwind_SjLj_Unregister at exit of the function.  Which means
+      that we cannot do any sibcall transformations.  */
+   if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ())
+     return false;
+ 
+   /* Any function that calls setjmp might have longjmp called from
+      any called function.  ??? We really should represent this
+      properly in the CFG so that this needn't be special cased.  */
+   if (current_function_calls_setjmp)
+     return false;
+ 
+   return true;
+ }
  
  /* Finds tailcalls falling into basic block BB.  The current state of the
     recursive search is stored inside ACT, the list of found tailcalls is
*************** eliminate_tail_call (struct tailcall *t)
*** 273,279 ****
     by PHIS_CONSTRUCTED.  */
  
  static bool
! optimize_tail_call (struct tailcall *t, bool *phis_constructed)
  {
    if (t->tail_recursion)
      {
--- 301,308 ----
     by PHIS_CONSTRUCTED.  */
  
  static bool
! optimize_tail_call (struct tailcall *t, bool *phis_constructed,
! 		    bool opt_tailcalls)
  {
    if (t->tail_recursion)
      {
*************** optimize_tail_call (struct tailcall *t, 
*** 310,315 ****
--- 339,360 ----
        eliminate_tail_call (t);
        return true;
      }
+   else if (opt_tailcalls)
+     {
+       tree stmt = bsi_stmt (t->call_bsi);
+ 
+       if (TREE_CODE (stmt) == MODIFY_EXPR)
+ 	stmt = TREE_OPERAND (stmt, 1);
+       if (TREE_CODE (stmt) != CALL_EXPR)
+ 	abort ();
+       CALL_EXPR_TAILCALL (stmt) = 1;
+       if (dump_file && (dump_flags & TDF_DETAILS))
+         {
+ 	  fprintf (dump_file, "Found tail call ");
+ 	  print_generic_expr (dump_file, stmt, 0);
+ 	  fprintf (dump_file, " in bb %i", t->call_block->index);
+ 	}
+     }
    return false;
  }
  
*************** optimize_tail_call (struct tailcall *t, 
*** 317,323 ****
     into iteration.  */
  
  void
! tree_optimize_tail_calls (void)
  {
    edge e;
    bool phis_constructed = false;
--- 362,368 ----
     into iteration.  */
  
  void
! tree_optimize_tail_calls (bool opt_tailcalls, enum tree_dump_index pass)
  {
    edge e;
    bool phis_constructed = false;
*************** tree_optimize_tail_calls (void)
*** 326,333 ****
  
    if (!suitable_for_tail_opt_p ())
      return;
! 
!   dump_file = dump_begin (TDI_tail, &dump_flags);
  
    common.return_block = NULL;
    common.ret_variable = NULL_TREE;
--- 371,379 ----
  
    if (!suitable_for_tail_opt_p ())
      return;
!   if (opt_tailcalls)
!     opt_tailcalls = suitable_for_tail_call_opt_p ();
!   dump_file = dump_begin (pass, &dump_flags);
  
    common.return_block = NULL;
    common.ret_variable = NULL_TREE;
*************** tree_optimize_tail_calls (void)
*** 343,349 ****
    for (; tailcalls; tailcalls = next)
      {
        next = tailcalls->next;
!       changed |= optimize_tail_call (tailcalls, &phis_constructed);
        free (tailcalls);
      }
  
--- 389,396 ----
    for (; tailcalls; tailcalls = next)
      {
        next = tailcalls->next;
!       changed |= optimize_tail_call (tailcalls, &phis_constructed, 
! 		      		     opt_tailcalls);
        free (tailcalls);
      }
  
*************** tree_optimize_tail_calls (void)
*** 353,358 ****
    if (dump_file)
      {
        dump_function_to_file (current_function_decl, dump_file, dump_flags);
!       dump_end (TDI_tail, dump_file);
      }
  }
--- 400,405 ----
    if (dump_file)
      {
        dump_function_to_file (current_function_decl, dump_file, dump_flags);
!       dump_end (pass, dump_file);
      }
  }
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.152
diff -c -3 -p -r1.342.2.152 tree.h
*** tree.h	15 Dec 2003 22:58:37 -0000	1.342.2.152
--- tree.h	16 Dec 2003 22:50:55 -0000
*************** struct tree_common GTY(())
*** 174,179 ****
--- 174,180 ----
  	   ..._TYPE, IDENTIFIER_NODE.
  	   In a STMT_EXPR, it means we want the result of the enclosed
  	   expression.
+        CALL_EXPR_TAILCALL in CALL_EXPR
  
     static_flag:
  
*************** extern void tree_operand_check_failed (i
*** 590,595 ****
--- 591,598 ----
     had its address taken.  That matters for inline functions.  */
  #define TREE_ADDRESSABLE(NODE) ((NODE)->common.addressable_flag)
  
+ #define CALL_EXPR_TAILCALL(NODE) (CALL_EXPR_CHECK(NODE)->common.addressable_flag)
+ 
  /* In a VAR_DECL, nonzero means allocate static storage.
     In a FUNCTION_DECL, nonzero if function has been defined.
     In a CONSTRUCTOR, nonzero means allocate static storage.  */
*************** enum tree_dump_index
*** 3588,3594 ****
    TDI_loop,
    TDI_mustalias,
    TDI_ssa_3,
!   TDI_tail,			/* dump after tail recursion elimination  */
    TDI_sra,
    TDI_ssa_4,
    TDI_ccp,
--- 3591,3597 ----
    TDI_loop,
    TDI_mustalias,
    TDI_ssa_3,
!   TDI_tail1,			/* dump after tail recursion elimination  */
    TDI_sra,
    TDI_ssa_4,
    TDI_ccp,
*************** enum tree_dump_index
*** 3597,3602 ****
--- 3600,3606 ----
    TDI_dom_2,
    TDI_ssa_6,
    TDI_dce_2,
+   TDI_tail2,			/* dump after tail recursion/tail call */
    TDI_optimized,
    TDI_mudflap2,
  



More information about the Gcc-patches mailing list