[tree-ssa] replace sibcall.c take 3
Jan Hubicka
hubicka@ucw.cz
Tue Nov 18 00:20:00 GMT 2003
Hi,
this patch replaces sibcall.c. While testing the patch I noticed that
it still does catch all cases sibcall.c does. The reason is test:
/* No local variable should have its address taken, as otherwise it might
be passed to the recursive call. This of course is overly
conservative and should be replaced by a dataflow analysis later. */
for (i = 0; i < (int) VARRAY_ACTIVE_SIZE (referenced_vars); i++)
{
tree var = VARRAY_TREE (referenced_vars, i);
if (decl_function_context (var) == current_function_decl
&& !TREE_STATIC (var)
&& TREE_ADDRESSABLE (var))
return false;
}
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?
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?
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.
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 17 Nov 2003 23:52:40 -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 17 Nov 2003 23:52:40 -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,3486 ----
zero out the sequence. */
if (sibcall_failure)
tail_call_insns = NULL_RTX;
+ else
+ break;
}
! /* 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. */
! 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 17 Nov 2003 23:52:40 -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 17 Nov 2003 23:52:41 -0000
*************** 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 17 Nov 2003 23:52:41 -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 17 Nov 2003 23:52:41 -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_tail);
/* 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 17 Nov 2003 23:52:41 -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 17 Nov 2003 23:52:42 -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
*** 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 17 Nov 2003 23:52:44 -0000
***************
*** 0 ****
--- 1,18 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O1 -fdump-tree-tail2" } */
+ 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" 0 "tail2"} } */
More information about the Gcc-patches
mailing list