This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [tree-ssa] replace sibcall.c take 3
> On Tue, Nov 18, 2003 at 01:05:22AM +0100, Jan Hubicka wrote:
> > The problem is that referenced_vars is not updated when we remove all
> > references of variable. Since this is common with inlining, perhaps we
> > want to recompute the list?
>
> That seems reasonable.
OK, I think I can hook it into dce pass same way as I do for alloca
discovery.
>
> > Also it would be nice to allow conversions where promoting rules ensure
> > that the true return types will be same and noop conversions. What is
> > the most convenient way to deal with this?
>
> Dunno. We ignore it for now, I think.
Yes, we ignore it, but I received several "bugreports" about this. It
seems to be common to get types different on 64bit arch.
>
> > ! /* If this was a potential tail site, then emit a
> > ! CALL_PLACEHOLDER with the normal and the tail streams.
> > One of them will be selected later. */
>
> Where does this happen now? Or is the comment out of date?
We always emit one sequence, but because we may notice that tailcall
fails during emitting tailcall, I had to keep the loop. It simply
terminates when tailcall sequence suceeded, when not, we loop and
produce normal call.
This is subject of followup cleanup patch :)
(I need to sort out what sibcall failures still can happen with gimple
and try to catch them all before expanding).
I would like to get rid of LIBCALL blocks for function calls first so
the calls.c gets somewhat more readable.
>
> Where tested?
i386-linux.
I am attaching updated patch. It has the comment fixed and I also
noticed in meantime that I have to rename .tail dumps into .tail1, otherwise the
trailing '2' gets interpreted as option by argument passing.
OK now?
Honza
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; update equivalencies after sibcall production.
* toplev.c (rest_of_handle_sibling_calls): Kill.
(rest_of_compialtion): Do not use rest_of_handle_sibling_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
* gcc.dg/tree-ssa/tailcall-1.c: New.
* gcc.dg/tree-ssa/tailrecursion-?.c: Rename dump
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.130
diff -c -3 -p -r1.903.2.130 Makefile.in
*** Makefile.in 13 Nov 2003 02:37:33 -0000 1.903.2.130
--- Makefile.in 18 Nov 2003 02:10:05 -0000
*************** OBJS-common = \
*** 911,917 ****
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 ssa.o ssa-ccp.o ssa-dce.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
--- 911,917 ----
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 ssa.o ssa-ccp.o ssa-dce.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) $
*** 1587,1593 ****
$(TREE_DUMP_H) except.h langhooks.h cfgloop.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) \
--- 1587,1593 ----
$(TREE_DUMP_H) except.h langhooks.h cfgloop.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
*** 1786,1793 ****
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)
--- 1786,1791 ----
Index: calls.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/calls.c,v
retrieving revision 1.229.2.35
diff -c -3 -p -r1.229.2.35 calls.c
*** calls.c 14 Nov 2003 08:16:55 -0000 1.229.2.35
--- calls.c 18 Nov 2003 02:10:05 -0000
*************** fix_unsafe_tree (tree t)
*** 2033,2038 ****
--- 2033,2101 ----
return t;
}
+ /* 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
*** 2049,2059 ****
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;
--- 2112,2120 ----
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
*** 2061,2069 ****
/* 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,
--- 2122,2128 ----
/* 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
*** 2456,2468 ****
|| 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 (
--- 2515,2521 ----
|| 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
*** 2500,2506 ****
|| !(*lang_hooks.decls.ok_for_sibcall) (fndecl))
try_tail_call = 0;
! if (try_tail_call || try_tail_recursion)
{
int end, inc;
actparms = NULL_TREE;
--- 2553,2559 ----
|| !(*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
*** 2535,2545 ****
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)
--- 2588,2593 ----
*************** expand_call (tree exp, rtx target, int i
*** 2547,2596 ****
/* 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))
{
--- 2595,2603 ----
/* 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
*** 2625,2631 ****
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;
--- 2632,2638 ----
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
*** 3428,3475 ****
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);
--- 3435,3485 ----
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)
{
! rtx insn;
! tree arg;
!
! emit_insn (tail_call_insns);
! /* 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. */
! 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;
! }
}
else
emit_insn (normal_call_insns);
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.654.2.75
diff -c -3 -p -r1.654.2.75 toplev.c
*** toplev.c 14 Nov 2003 16:50:01 -0000 1.654.2.75
--- toplev.c 18 Nov 2003 02:10:06 -0000
*************** static void rest_of_handle_life (tree, r
*** 134,140 ****
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);
--- 134,139 ----
*************** rest_of_handle_addressof (tree decl, rtx
*** 2602,2635 ****
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)
--- 2601,2606 ----
*************** rest_of_compilation (tree decl)
*** 3294,3302 ****
note_prediction_to_br_prob ();
timevar_pop (TV_BRANCH_PROB);
}
-
- if (flag_optimize_sibling_calls)
- rest_of_handle_sibling_calls (insns);
timevar_pop (TV_JUMP);
--- 3265,3270 ----
Index: tree-dump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dump.c,v
retrieving revision 1.6.2.51
diff -c -3 -p -r1.6.2.51 tree-dump.c
*** tree-dump.c 17 Nov 2003 23:39:19 -0000 1.6.2.51
--- tree-dump.c 18 Nov 2003 02:10:06 -0000
*************** static struct dump_file_info dump_files[
*** 664,670 ****
{".dom1", "tree-dom1", 0, 0},
{".ssa2", "tree-ssa2", 0, 0},
{".dce1", "tree-dce1", 0, 0},
! {".tail", "tree-tail", 0, 0},
{".mustalias", "tree-mustalias", 0, 0},
{".ssa3", "tree-ssa3", 0, 0},
{".ccp", "tree-ccp", 0, 0},
--- 664,670 ----
{".dom1", "tree-dom1", 0, 0},
{".ssa2", "tree-ssa2", 0, 0},
{".dce1", "tree-dce1", 0, 0},
! {".tail1", "tree-tail1", 0, 0},
{".mustalias", "tree-mustalias", 0, 0},
{".ssa3", "tree-ssa3", 0, 0},
{".ccp", "tree-ccp", 0, 0},
*************** static struct dump_file_info dump_files[
*** 674,679 ****
--- 674,680 ----
{".ssa5", "tree-ssa5", 0, 0},
{".copyprop", "tree-copyprop", 0, 0},
{".dce2", "tree-dce2", 0, 0},
+ {".tail2", "tree-tail2", 0, 0},
{".optimized", "tree-optimized", 0, 0},
{".mudflap", "tree-mudflap", 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.153
diff -c -3 -p -r1.1.4.153 tree-flow.h
*** tree-flow.h 17 Nov 2003 23:18:13 -0000 1.1.4.153
--- tree-flow.h 18 Nov 2003 02:10:06 -0000
*************** extern edge thread_edge (edge, basic_blo
*** 436,442 ****
extern basic_block label_to_block (tree);
extern bool cleanup_cond_expr_graph (basic_block, block_stmt_iterator);
extern bool cleanup_switch_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 *);
--- 436,442 ----
extern basic_block label_to_block (tree);
extern bool cleanup_cond_expr_graph (basic_block, block_stmt_iterator);
extern bool cleanup_switch_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.73
diff -c -3 -p -r1.1.4.73 tree-optimize.c
*** tree-optimize.c 17 Nov 2003 23:39:20 -0000 1.1.4.73
--- tree-optimize.c 18 Nov 2003 02:10:06 -0000
*************** optimize_function_tree (tree fndecl, tre
*** 118,124 ****
tree_ssa_dce (fndecl, TDI_dce_1);
/* Eliminate tail recursion calls. */
! tree_optimize_tail_calls ();
/* The must-alias pass removes the aliasing and addressability bits
from variables that used to have their address taken. */
--- 118,124 ----
tree_ssa_dce (fndecl, TDI_dce_1);
/* Eliminate tail recursion calls. */
! tree_optimize_tail_calls (false, TDI_tail1);
/* The must-alias pass removes the aliasing and addressability bits
from variables that used to have their address taken. */
*************** optimize_function_tree (tree fndecl, tre
*** 165,170 ****
--- 165,173 ----
/* Do a second DCE pass. */
if (flag_tree_dce)
tree_ssa_dce (fndecl, TDI_dce_2);
+
+ /* Eliminate tail recursion calls and discover sibling calls. */
+ tree_optimize_tail_calls (true, TDI_tail2);
#ifdef ENABLE_CHECKING
verify_flow_info ();
Index: tree-tailcall.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-tailcall.c,v
retrieving revision 1.1.2.7
diff -c -3 -p -r1.1.2.7 tree-tailcall.c
*** tree-tailcall.c 17 Nov 2003 23:39:20 -0000 1.1.2.7
--- tree-tailcall.c 18 Nov 2003 02:10:06 -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.129
diff -c -3 -p -r1.342.2.129 tree.h
*** tree.h 17 Nov 2003 23:39:20 -0000 1.342.2.129
--- tree.h 18 Nov 2003 02:10:07 -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
*** 584,589 ****
--- 585,592 ----
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
*** 3548,3554 ****
TDI_dom_1,
TDI_ssa_2,
TDI_dce_1,
! TDI_tail, /* dump after tail recursion elimination */
TDI_mustalias,
TDI_ssa_3,
TDI_ccp,
--- 3551,3557 ----
TDI_dom_1,
TDI_ssa_2,
TDI_dce_1,
! TDI_tail1, /* dump after tail recursion elimination */
TDI_mustalias,
TDI_ssa_3,
TDI_ccp,
*************** enum tree_dump_index
*** 3558,3563 ****
--- 3561,3567 ----
TDI_ssa_5,
TDI_copyprop,
TDI_dce_2,
+ TDI_tail2, /* dump after tail recursion/tail call */
TDI_optimized,
TDI_mudflap, /* dump each function after mudflap. */
Index: testsuite/gcc.dg/tree-ssa/tailcall-1.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/tailcall-1.c
diff -N testsuite/gcc.dg/tree-ssa/tailcall-1.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- testsuite/gcc.dg/tree-ssa/tailcall-1.c 18 Nov 2003 02:10:12 -0000
***************
*** 0 ****
--- 1,18 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O1 -fdump-tree-tail2-details" } */
+ int q(int a);
+ int *v;
+ int
+ t(int a)
+ {
+ int r,r1;
+ if (a)
+ r1=r = q(a-1);
+ else
+ return 0;
+ /* Dead alloca should not disturb us. */
+ if (r!=r1)
+ v=alloca(r);
+ return r;
+ }
+ /* { dg-final { scan-tree-dump-times "Found tail call" 1 "tail2"} } */
Index: testsuite/gcc.dg/tree-ssa/tailrecursion-1.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/Attic/tailrecursion-1.c,v
retrieving revision 1.1.2.1
diff -c -3 -p -r1.1.2.1 tailrecursion-1.c
*** testsuite/gcc.dg/tree-ssa/tailrecursion-1.c 17 Nov 2003 23:39:20 -0000 1.1.2.1
--- testsuite/gcc.dg/tree-ssa/tailrecursion-1.c 18 Nov 2003 02:10:12 -0000
***************
*** 1,5 ****
/* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-tail-details" } */
int
t(int a)
{
--- 1,5 ----
/* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-tail1-details" } */
int
t(int a)
{
*************** t(int a)
*** 8,11 ****
else
return 0;
}
! /* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tail"} } */
--- 8,11 ----
else
return 0;
}
! /* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tail1"} } */
Index: testsuite/gcc.dg/tree-ssa/tailrecursion-2.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/Attic/tailrecursion-2.c,v
retrieving revision 1.1.2.1
diff -c -3 -p -r1.1.2.1 tailrecursion-2.c
*** testsuite/gcc.dg/tree-ssa/tailrecursion-2.c 17 Nov 2003 23:39:20 -0000 1.1.2.1
--- testsuite/gcc.dg/tree-ssa/tailrecursion-2.c 18 Nov 2003 02:10:12 -0000
***************
*** 1,5 ****
/* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-tail-details" } */
int
t(char *a)
{
--- 1,5 ----
/* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-tail1-details" } */
int
t(char *a)
{
*************** t(char *a)
*** 9,12 ****
else
return 0;
}
! /* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tail"} } */
--- 9,12 ----
else
return 0;
}
! /* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tail1"} } */
Index: testsuite/gcc.dg/tree-ssa/tailrecursion-3.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/Attic/tailrecursion-3.c,v
retrieving revision 1.1.2.1
diff -c -3 -p -r1.1.2.1 tailrecursion-3.c
*** testsuite/gcc.dg/tree-ssa/tailrecursion-3.c 17 Nov 2003 23:39:20 -0000 1.1.2.1
--- testsuite/gcc.dg/tree-ssa/tailrecursion-3.c 18 Nov 2003 02:10:12 -0000
***************
*** 1,5 ****
/* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-tail-details" } */
int
t(int a)
{
--- 1,5 ----
/* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-tail1-details" } */
int
t(int a)
{
*************** t(int a)
*** 12,15 ****
r=r;
return r;
}
! /* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tail"} } */
--- 12,15 ----
r=r;
return r;
}
! /* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tail1"} } */
Index: testsuite/gcc.dg/tree-ssa/tailrecursion-4.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/Attic/tailrecursion-4.c,v
retrieving revision 1.1.2.1
diff -c -3 -p -r1.1.2.1 tailrecursion-4.c
*** testsuite/gcc.dg/tree-ssa/tailrecursion-4.c 17 Nov 2003 23:39:21 -0000 1.1.2.1
--- testsuite/gcc.dg/tree-ssa/tailrecursion-4.c 18 Nov 2003 02:10:12 -0000
***************
*** 1,5 ****
/* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-tail-details" } */
int
t(int a)
{
--- 1,5 ----
/* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-tail1-details" } */
int
t(int a)
{
*************** t(int a)
*** 14,17 ****
r=r;
return r;
}
! /* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 2 "tail"} } */
--- 14,17 ----
r=r;
return r;
}
! /* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 2 "tail1"} } */