This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Tail call ellimination take II
- From: Jan Hubicka <jh at suse dot cz>
- To: gcc-patches at gcc dot gnu dot org, rth at cygnus dot com
- Date: Thu, 13 Nov 2003 02:52:35 +0100
- Subject: Tail call ellimination take II
Hi,
this patch is update of tail call ellimination.
Thanks to Zdenek's and Richard's changes it is now easy to preserve the CFG
after de_ssa pass so I can do tail call discovery afterwards.
The second tail call ellimination also enables more tail recursion
conversion. As next step I would like to get the pass working in SSA
form, but I don't want to do it all at once.
The changes to avoid killing of CFG are needed anyway for my expansion
changes.
Regtested/bootstrapped i386 together with the alloca changes.
OK?
/* { dg-do compile } */
/* { dg-options "-O1 -fdump-tree-tail1" } */
int
t(int a)
{
if (a)
return t(a-1);
else
return 0;
}
/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 0 "tail1"} } */
/* { dg-do compile } */
/* { dg-options "-O1 -fdump-tree-tail2" } */
int
t(int a)
{
int r;
if (a)
r = t(a-1);
else
return 0;
if (r)
r=r;
return r;
}
/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 0 "tail2"} } */
/* { 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"} } */
Sat Nov 8 19:46:15 CET 2003 Jan Hubicka <jh@suse.cz>
* 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.
* tree-flow.h (tree_optimize_tail_calls): Add new argument.
* tree-optimize.c (optimize_function_tree): Update call of
tree_optimize_tail_calls; add send call.
* tree-tailcall.c: Include except.h
(optimize_tail_call): New arguments; set CALL_EXPR_TAILCALL when
doing tail call.
(suitable_for_tail_call_opt_p): New.
(tree_optimize_tail_calls): New argument opt_tailcalls; check
suitable_for_tail_call_opt_p; pass it to optimize_tail_call;
do remove datastructures not killed by rewrite_out_of_ssa anymore;
remove useless stmts and variables.
* tree.h (CALL_EXPR_TAILCALL): New macro.
* toplev.c (rest_of_handle_sibling_calls): Kill.
(rest_of_compilation): Do not call rest_of_handle_sibling_calls.
* tree-dump.c (dump_files): Add tail2 pass, rename tail to tail1
* tree-ssa.c (rewrite_out_of_ssa): Do not kill datastructures unrelated
to SSA itself; don't remove useless_stmts.
Index: calls.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/calls.c,v
retrieving revision 1.229.2.33
diff -c -3 -p -r1.229.2.33 calls.c
*** calls.c 18 Oct 2003 23:59:36 -0000 1.229.2.33
--- calls.c 13 Nov 2003 01:32:20 -0000
*************** fix_unsafe_tree (tree t)
*** 2010,2015 ****
--- 2010,2078 ----
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
*** 2026,2036 ****
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;
--- 2089,2097 ----
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
*** 2038,2046 ****
/* 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,
--- 2099,2105 ----
/* 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
*** 2437,2449 ****
|| 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 (
--- 2496,2502 ----
|| 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
*** 2481,2487 ****
|| !(*lang_hooks.decls.ok_for_sibcall) (fndecl))
try_tail_call = 0;
! if (try_tail_call || try_tail_recursion)
{
int end, inc;
actparms = NULL_TREE;
--- 2534,2540 ----
|| !(*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
*** 2516,2526 ****
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)
--- 2569,2574 ----
*************** expand_call (tree exp, rtx target, int i
*** 2528,2577 ****
/* 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))
{
--- 2576,2584 ----
/* 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
*** 2606,2612 ****
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;
--- 2613,2619 ----
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
*** 3409,3456 ****
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);
--- 3416,3467 ----
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.73
diff -c -3 -p -r1.654.2.73 toplev.c
*** toplev.c 10 Nov 2003 20:11:38 -0000 1.654.2.73
--- toplev.c 13 Nov 2003 01:32:20 -0000
*************** rest_of_handle_addressof (tree decl, rtx
*** 2598,2631 ****
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)
--- 2598,2603 ----
*************** rest_of_compilation (tree decl)
*** 3290,3298 ****
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);
--- 3262,3267 ----
Index: tree-dump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dump.c,v
retrieving revision 1.6.2.49
diff -c -3 -p -r1.6.2.49 tree-dump.c
*** tree-dump.c 11 Nov 2003 18:04:46 -0000 1.6.2.49
--- tree-dump.c 13 Nov 2003 01:32:20 -0000
*************** static struct dump_file_info dump_files[
*** 657,663 ****
{".lower", "tree-lower", 0, 0},
{".cfg", "tree-cfg", 0, 0},
{".dot", "tree-dot", 0, 0},
! {".tail", "tree-tail", 0, 0},
{".pta", "tree-pta", 0, 0},
{".alias", "tree-alias", 0, 0},
{".ssa1", "tree-ssa1", 0, 0},
--- 657,663 ----
{".lower", "tree-lower", 0, 0},
{".cfg", "tree-cfg", 0, 0},
{".dot", "tree-dot", 0, 0},
! {".tail1", "tree-tail1", 0, 0},
{".pta", "tree-pta", 0, 0},
{".alias", "tree-alias", 0, 0},
{".ssa1", "tree-ssa1", 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.147
diff -c -3 -p -r1.1.4.147 tree-flow.h
*** tree-flow.h 12 Nov 2003 23:33:07 -0000 1.1.4.147
--- tree-flow.h 13 Nov 2003 01:32:20 -0000
*************** extern edge thread_edge (edge, basic_blo
*** 441,447 ****
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 *);
--- 441,447 ----
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.71
diff -c -3 -p -r1.1.4.71 tree-optimize.c
*** tree-optimize.c 12 Nov 2003 22:06:26 -0000 1.1.4.71
--- tree-optimize.c 13 Nov 2003 01:32:20 -0000
*************** optimize_function_tree (tree fndecl, tre
*** 79,85 ****
find_referenced_vars (fndecl);
/* Eliminate tail recursion calls. */
! tree_optimize_tail_calls ();
/* Compute aliasing information for all the variables referenced in
the function. */
--- 79,85 ----
find_referenced_vars (fndecl);
/* Eliminate tail recursion calls. */
! tree_optimize_tail_calls (false, TDI_tail1);
/* Compute aliasing information for all the variables referenced in
the function. */
*************** optimize_function_tree (tree fndecl, tre
*** 172,179 ****
--- 172,192 ----
/* Rewrite the function out of SSA form. */
rewrite_out_of_ssa (fndecl, TDI_optimized);
+ /* Eliminate newly introduced tail recursion calls and mark tail calls. */
+ tree_optimize_tail_calls (true, TDI_tail2);
+
+ /* Do some cleanups which reduce the amount of data the
+ tree->rtl expanders deal with. */
+ cfg_remove_useless_stmts ();
+
+ /* Remove unnecesary variables. */
+ remove_useless_vars ();
+
/* Flush out flow graph and SSA data. */
sbitmap_free (vars_to_rename);
+ referenced_vars = NULL;
+ global_var = NULL_TREE;
+ call_clobbered_vars = NULL;
}
/* Re-chain the statements from the blocks. */
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.151
diff -c -3 -p -r1.1.4.151 tree-ssa.c
*** tree-ssa.c 12 Nov 2003 23:33:07 -0000 1.1.4.151
--- tree-ssa.c 13 Nov 2003 01:32:20 -0000
*************** rewrite_out_of_ssa (tree fndecl, enum tr
*** 1886,1898 ****
if (dump_file && (dump_flags & TDF_DETAILS))
dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
- /* Do some cleanups which reduce the amount of data the
- tree->rtl expanders deal with. */
- cfg_remove_useless_stmts ();
-
- /* Remove unnecesary variables. */
- remove_useless_vars ();
-
/* Debugging dumps. */
if (dump_file)
{
--- 1886,1891 ----
*************** delete_tree_ssa (tree fndecl)
*** 2253,2262 ****
/* Remove annotations from every referenced variable. */
for (i = 0; i < num_referenced_vars; i++)
referenced_var (i)->common.ann = NULL;
-
- referenced_vars = NULL;
- global_var = NULL_TREE;
- call_clobbered_vars = NULL;
}
--- 2246,2251 ----
Index: tree-tailcall.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-tailcall.c,v
retrieving revision 1.1.2.6
diff -c -3 -p -r1.1.2.6 tree-tailcall.c
*** tree-tailcall.c 11 Nov 2003 18:04:47 -0000 1.1.2.6
--- tree-tailcall.c 13 Nov 2003 01:32:20 -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 *, tree *);
static void eliminate_tail_call (struct tailcall *, tree);
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 *, tree *, bool);
static void eliminate_tail_call (struct tailcall *, tree);
static void find_tail_calls (basic_block, struct tailcall *, struct tailcall **);
*************** suitable_for_tail_opt_p (void)
*** 86,91 ****
--- 87,119 ----
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,
*** 208,214 ****
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "Eliminated tail call in bb %d : ", bb->index);
print_generic_stmt (dump_file, stmt, TDF_SLIM);
fprintf (dump_file, "\n");
}
--- 236,242 ----
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "Eliminated tail recursion in bb %d : ", bb->index);
print_generic_stmt (dump_file, stmt, TDF_SLIM);
fprintf (dump_file, "\n");
}
*************** eliminate_tail_call (struct tailcall *t,
*** 267,303 ****
they are needed. Returns true if cfg is changed. */
static bool
! optimize_tail_call (struct tailcall *t, tree *tmp_vars)
{
tree tmp_var, param;
! /* Nothing to do unless it is tail recursion. */
! if (!t->tail_recursion)
! return false;
!
! if (!*tmp_vars)
{
! /* Prepare the temporary variables. */
! for (param = DECL_ARGUMENTS (current_function_decl);
! param;
! param = TREE_CHAIN (param))
{
! tmp_var = create_tmp_var (TREE_TYPE (param), "tailtmp");
! add_referenced_tmp_var (tmp_var);
! *tmp_vars = tree_cons (NULL_TREE, tmp_var, *tmp_vars);
}
! *tmp_vars = nreverse (*tmp_vars);
}
! eliminate_tail_call (t, *tmp_vars);
! return true;
}
/* Optimizes tail calls in the function, turning the tail recursion
into iteration. */
void
! tree_optimize_tail_calls (void)
{
edge e;
tree tmp_vars = NULL_TREE;
--- 295,346 ----
they are needed. Returns true if cfg is changed. */
static bool
! optimize_tail_call (struct tailcall *t, tree * tmp_vars, bool opt_tailcalls)
{
tree tmp_var, param;
! if (t->tail_recursion)
{
! if (!*tmp_vars)
{
! /* Prepare the temporary variables. */
! for (param = DECL_ARGUMENTS (current_function_decl);
! param; param = TREE_CHAIN (param))
! {
! tmp_var = create_tmp_var (TREE_TYPE (param), "tailtmp");
! add_referenced_tmp_var (tmp_var);
! *tmp_vars = tree_cons (NULL_TREE, tmp_var, *tmp_vars);
! }
! *tmp_vars = nreverse (*tmp_vars);
}
! eliminate_tail_call (t, *tmp_vars);
! 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 true;
! }
! return false;
}
/* Optimizes tail calls in the function, turning the tail recursion
into iteration. */
void
! tree_optimize_tail_calls (bool opt_tailcalls, enum tree_dump_index pass)
{
edge e;
tree tmp_vars = NULL_TREE;
*************** tree_optimize_tail_calls (void)
*** 306,313 ****
if (!suitable_for_tail_opt_p ())
return;
!
! dump_file = dump_begin (TDI_tail, &dump_flags);
common.return_block = NULL;
common.ret_variable = NULL_TREE;
--- 349,357 ----
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)
*** 323,329 ****
for (; tailcalls; tailcalls = next)
{
next = tailcalls->next;
! changed |= optimize_tail_call (tailcalls, &tmp_vars);
free (tailcalls);
}
--- 367,373 ----
for (; tailcalls; tailcalls = next)
{
next = tailcalls->next;
! changed |= optimize_tail_call (tailcalls, &tmp_vars, opt_tailcalls);
free (tailcalls);
}
*************** tree_optimize_tail_calls (void)
*** 333,338 ****
if (dump_file)
{
dump_function_to_file (current_function_decl, dump_file, dump_flags);
! dump_end (TDI_tail, dump_file);
}
}
--- 377,382 ----
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.123
diff -c -3 -p -r1.342.2.123 tree.h
*** tree.h 12 Nov 2003 22:06:27 -0000 1.342.2.123
--- tree.h 13 Nov 2003 01:32:20 -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
*** 3531,3537 ****
TDI_cfg, /* dump the flowgraph for each function. */
TDI_dot, /* create a dot graph file for each
function's flowgraph. */
! TDI_tail, /* dump after tail recursion elimination */
TDI_pta, /* dump points-to information for each
function. */
TDI_alias, /* dump aliasing information. */
--- 3534,3540 ----
TDI_cfg, /* dump the flowgraph for each function. */
TDI_dot, /* create a dot graph file for each
function's flowgraph. */
! TDI_tail1, /* dump after tail recursion elimination */
TDI_pta, /* dump points-to information for each
function. */
TDI_alias, /* dump aliasing information. */
*************** enum tree_dump_index
*** 3552,3557 ****
--- 3555,3561 ----
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. */