1 /* Tail call optimization on trees.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
33 #include "diagnostic.h"
35 #include "tree-pass.h"
37 #include "langhooks.h"
39 /* The file implements the tail recursion elimination. It is also used to
40 analyze the tail calls in general, passing the results to the rtl level
41 where they are used for sibcall optimization.
43 In addition to the standard tail recursion elimination, we handle the most
44 trivial cases of making the call tail recursive by creating accumulators.
45 For example the following function
50 return n + sum (n - 1);
67 To do this, we maintain two accumulators (a_acc and m_acc) that indicate
68 when we reach the return x statement, we should return a_acc + x * m_acc
69 instead. They are initially initialized to 0 and 1, respectively,
70 so the semantics of the function is obviously preserved. If we are
71 guaranteed that the value of the accumulator never change, we
74 There are three cases how the function may exit. The first one is
75 handled in adjust_return_value, the other two in adjust_accumulator_values
76 (the second case is actually a special case of the third one and we
77 present it separately just for clarity):
79 1) Just return x, where x is not in any of the remaining special shapes.
80 We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
82 2) return f (...), where f is the current function, is rewritten in a
83 classical tail-recursion elimination way, into assignment of arguments
84 and jump to the start of the function. Values of the accumulators
87 3) return a + m * f(...), where a and m do not depend on call to f.
88 To preserve the semantics described before we want this to be rewritten
89 in such a way that we finally return
91 a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
93 I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
94 eliminate the tail call to f. Special cases when the value is just
95 added or just multiplied are obtained by setting a = 0 or m = 1.
97 TODO -- it is possible to do similar tricks for other operations. */
99 /* A structure that describes the tailcall. */
103 /* The block in that the call occur. */
104 basic_block call_block
;
106 /* The iterator pointing to the call statement. */
107 block_stmt_iterator call_bsi
;
109 /* True if it is a call to the current function. */
112 /* The return value of the caller is mult * f + add, where f is the return
113 value of the call. */
116 /* Next tailcall in the chain. */
117 struct tailcall
*next
;
120 /* The variables holding the value of multiplicative and additive
122 static tree m_acc
, a_acc
;
124 static bool suitable_for_tail_opt_p (void);
125 static bool optimize_tail_call (struct tailcall
*, bool);
126 static void eliminate_tail_call (struct tailcall
*);
127 static void find_tail_calls (basic_block
, struct tailcall
**);
129 /* Returns false when the function is not suitable for tail call optimization
130 from some reason (e.g. if it takes variable number of arguments). */
133 suitable_for_tail_opt_p (void)
137 if (current_function_stdarg
)
140 /* No local variable nor structure field should be call-clobbered. We
141 ignore any kind of memory tag, as these are not real variables. */
142 for (i
= 0; i
< (int) VARRAY_ACTIVE_SIZE (referenced_vars
); i
++)
144 tree var
= VARRAY_TREE (referenced_vars
, i
);
146 if (!(TREE_STATIC (var
) || DECL_EXTERNAL (var
))
147 && (var_ann (var
)->mem_tag_kind
== NOT_A_TAG
148 || var_ann (var
)->mem_tag_kind
== STRUCT_FIELD
)
149 && is_call_clobbered (var
))
155 /* Returns false when the function is not suitable for tail call optimization
156 from some reason (e.g. if it takes variable number of arguments).
157 This test must pass in addition to suitable_for_tail_opt_p in order to make
158 tail call discovery happen. */
161 suitable_for_tail_call_opt_p (void)
165 /* alloca (until we have stack slot life analysis) inhibits
166 sibling call optimizations, but not tail recursion. */
167 if (current_function_calls_alloca
)
170 /* If we are using sjlj exceptions, we may need to add a call to
171 _Unwind_SjLj_Unregister at exit of the function. Which means
172 that we cannot do any sibcall transformations. */
173 if (USING_SJLJ_EXCEPTIONS
&& current_function_has_exception_handlers ())
176 /* Any function that calls setjmp might have longjmp called from
177 any called function. ??? We really should represent this
178 properly in the CFG so that this needn't be special cased. */
179 if (current_function_calls_setjmp
)
182 /* ??? It is OK if the argument of a function is taken in some cases,
183 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
184 for (param
= DECL_ARGUMENTS (current_function_decl
);
186 param
= TREE_CHAIN (param
))
187 if (TREE_ADDRESSABLE (param
))
193 /* Checks whether the expression EXPR in stmt AT is independent of the
194 statement pointed by BSI (in a sense that we already know EXPR's value
195 at BSI). We use the fact that we are only called from the chain of
196 basic blocks that have only single successor. Returns the expression
197 containing the value of EXPR at BSI. */
200 independent_of_stmt_p (tree expr
, tree at
, block_stmt_iterator bsi
)
202 basic_block bb
, call_bb
, at_bb
;
206 if (is_gimple_min_invariant (expr
))
209 if (TREE_CODE (expr
) != SSA_NAME
)
212 /* Mark the blocks in the chain leading to the end. */
213 at_bb
= bb_for_stmt (at
);
214 call_bb
= bb_for_stmt (bsi_stmt (bsi
));
215 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
221 at
= SSA_NAME_DEF_STMT (expr
);
222 bb
= bb_for_stmt (at
);
224 /* The default definition or defined before the chain. */
230 for (; !bsi_end_p (bsi
); bsi_next (&bsi
))
231 if (bsi_stmt (bsi
) == at
)
234 if (!bsi_end_p (bsi
))
239 if (TREE_CODE (at
) != PHI_NODE
)
245 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
250 expr
= PHI_ARG_DEF_FROM_EDGE (at
, e
);
251 if (TREE_CODE (expr
) != SSA_NAME
)
253 /* The value is a constant. */
258 /* Unmark the blocks. */
259 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
266 /* Simulates the effect of an assignment of ASS in STMT on the return value
267 of the tail recursive CALL passed in ASS_VAR. M and A are the
268 multiplicative and the additive factor for the real return value. */
271 process_assignment (tree ass
, tree stmt
, block_stmt_iterator call
, tree
*m
,
272 tree
*a
, tree
*ass_var
)
274 tree op0
, op1
, non_ass_var
;
275 tree dest
= TREE_OPERAND (ass
, 0);
276 tree src
= TREE_OPERAND (ass
, 1);
277 enum tree_code code
= TREE_CODE (src
);
280 /* See if this is a simple copy operation of an SSA name to the function
281 result. In that case we may have a simple tail call. Ignore type
282 conversions that can never produce extra code between the function
283 call and the function return. */
284 STRIP_NOPS (src_var
);
285 if (TREE_CODE (src_var
) == SSA_NAME
)
287 if (src_var
!= *ass_var
)
294 if (TREE_CODE_CLASS (code
) != tcc_binary
)
297 /* Accumulator optimizations will reverse the order of operations.
298 We can only do that for floating-point types if we're assuming
299 that addition and multiplication are associative. */
300 if (!flag_unsafe_math_optimizations
)
301 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
304 /* We only handle the code like
311 TODO -- Extend it for cases where the linear transformation of the output
312 is expressed in a more complicated way. */
314 op0
= TREE_OPERAND (src
, 0);
315 op1
= TREE_OPERAND (src
, 1);
318 && (non_ass_var
= independent_of_stmt_p (op1
, stmt
, call
)))
320 else if (op1
== *ass_var
321 && (non_ass_var
= independent_of_stmt_p (op0
, stmt
, call
)))
329 /* There should be no previous addition. TODO -- it should be fairly
330 straightforward to lift this restriction -- just allow storing
331 more complicated expressions in *A, and gimplify it in
332 adjust_accumulator_values. */
340 /* Similar remark applies here. Handling multiplication after addition
341 is just slightly more complicated -- we need to multiply both *A and
349 /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR). */
356 /* Propagate VAR through phis on edge E. */
359 propagate_through_phis (tree var
, edge e
)
361 basic_block dest
= e
->dest
;
364 for (phi
= phi_nodes (dest
); phi
; phi
= PHI_CHAIN (phi
))
365 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
)
366 return PHI_RESULT (phi
);
371 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
372 added to the start of RET. */
375 find_tail_calls (basic_block bb
, struct tailcall
**ret
)
377 tree ass_var
, ret_var
, stmt
, func
, param
, args
, call
= NULL_TREE
;
378 block_stmt_iterator bsi
, absi
;
386 if (!single_succ_p (bb
))
389 for (bsi
= bsi_last (bb
); !bsi_end_p (bsi
); bsi_prev (&bsi
))
391 stmt
= bsi_stmt (bsi
);
394 if (TREE_CODE (stmt
) == LABEL_EXPR
)
397 get_stmt_operands (stmt
);
399 /* Check for a call. */
400 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
402 ass_var
= TREE_OPERAND (stmt
, 0);
403 call
= TREE_OPERAND (stmt
, 1);
404 if (TREE_CODE (call
) == WITH_SIZE_EXPR
)
405 call
= TREE_OPERAND (call
, 0);
413 if (TREE_CODE (call
) == CALL_EXPR
)
416 /* If the statement has virtual or volatile operands, fail. */
417 ann
= stmt_ann (stmt
);
418 if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann
))
419 || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann
))
420 || NUM_VUSES (VUSE_OPS (ann
))
421 || ann
->has_volatile_ops
)
428 /* Recurse to the predecessors. */
429 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
430 find_tail_calls (e
->src
, ret
);
435 /* We found the call, check whether it is suitable. */
436 tail_recursion
= false;
437 func
= get_callee_fndecl (call
);
438 if (func
== current_function_decl
)
440 for (param
= DECL_ARGUMENTS (func
), args
= TREE_OPERAND (call
, 1);
442 param
= TREE_CHAIN (param
), args
= TREE_CHAIN (args
))
444 tree arg
= TREE_VALUE (args
);
447 /* Make sure there are no problems with copying. The parameter
448 have a copyable type and the two arguments must have reasonably
449 equivalent types. The latter requirement could be relaxed if
450 we emitted a suitable type conversion statement. */
451 if (!is_gimple_reg_type (TREE_TYPE (param
))
452 || !lang_hooks
.types_compatible_p (TREE_TYPE (param
),
456 /* The parameter should be a real operand, so that phi node
457 created for it at the start of the function has the meaning
458 of copying the value. This test implies is_gimple_reg_type
459 from the previous condition, however this one could be
460 relaxed by being more careful with copying the new value
461 of the parameter (emitting appropriate MODIFY_EXPR and
462 updating the virtual operands). */
463 if (!is_gimple_reg (param
))
468 tail_recursion
= true;
471 /* Now check the statements after the call. None of them has virtual
472 operands, so they may only depend on the call through its return
473 value. The return value should also be dependent on each of them,
474 since we are running after dce. */
484 while (bsi_end_p (absi
))
486 ass_var
= propagate_through_phis (ass_var
, single_succ_edge (abb
));
487 abb
= single_succ (abb
);
488 absi
= bsi_start (abb
);
491 stmt
= bsi_stmt (absi
);
493 if (TREE_CODE (stmt
) == LABEL_EXPR
)
496 if (TREE_CODE (stmt
) == RETURN_EXPR
)
499 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
502 if (!process_assignment (stmt
, stmt
, bsi
, &m
, &a
, &ass_var
))
506 /* See if this is a tail call we can handle. */
507 ret_var
= TREE_OPERAND (stmt
, 0);
509 && TREE_CODE (ret_var
) == MODIFY_EXPR
)
511 tree ret_op
= TREE_OPERAND (ret_var
, 1);
514 && TREE_CODE (ret_op
) != SSA_NAME
)
517 if (!process_assignment (ret_var
, stmt
, bsi
, &m
, &a
, &ass_var
))
519 ret_var
= TREE_OPERAND (ret_var
, 0);
522 /* We may proceed if there either is no return value, or the return value
523 is identical to the call's return. */
525 && (ret_var
!= ass_var
))
528 /* If this is not a tail recursive call, we cannot handle addends or
530 if (!tail_recursion
&& (m
|| a
))
533 nw
= xmalloc (sizeof (struct tailcall
));
538 nw
->tail_recursion
= tail_recursion
;
547 /* Adjust the accumulator values according to A and M after BSI, and update
548 the phi nodes on edge BACK. */
551 adjust_accumulator_values (block_stmt_iterator bsi
, tree m
, tree a
, edge back
)
553 tree stmt
, var
, phi
, tmp
;
554 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
555 tree a_acc_arg
= a_acc
, m_acc_arg
= m_acc
;
561 if (integer_onep (a
))
565 stmt
= build (MODIFY_EXPR
, ret_type
, NULL_TREE
,
566 build (MULT_EXPR
, ret_type
, m_acc
, a
));
568 tmp
= create_tmp_var (ret_type
, "acc_tmp");
569 add_referenced_tmp_var (tmp
);
571 var
= make_ssa_name (tmp
, stmt
);
572 TREE_OPERAND (stmt
, 0) = var
;
573 bsi_insert_after (&bsi
, stmt
, BSI_NEW_STMT
);
579 stmt
= build (MODIFY_EXPR
, ret_type
, NULL_TREE
,
580 build (PLUS_EXPR
, ret_type
, a_acc
, var
));
581 var
= make_ssa_name (SSA_NAME_VAR (a_acc
), stmt
);
582 TREE_OPERAND (stmt
, 0) = var
;
583 bsi_insert_after (&bsi
, stmt
, BSI_NEW_STMT
);
589 stmt
= build (MODIFY_EXPR
, ret_type
, NULL_TREE
,
590 build (MULT_EXPR
, ret_type
, m_acc
, m
));
591 var
= make_ssa_name (SSA_NAME_VAR (m_acc
), stmt
);
592 TREE_OPERAND (stmt
, 0) = var
;
593 bsi_insert_after (&bsi
, stmt
, BSI_NEW_STMT
);
599 for (phi
= phi_nodes (back
->dest
); phi
; phi
= PHI_CHAIN (phi
))
600 if (PHI_RESULT (phi
) == a_acc
)
603 add_phi_arg (phi
, a_acc_arg
, back
);
608 for (phi
= phi_nodes (back
->dest
); phi
; phi
= PHI_CHAIN (phi
))
609 if (PHI_RESULT (phi
) == m_acc
)
612 add_phi_arg (phi
, m_acc_arg
, back
);
616 /* Adjust value of the return at the end of BB according to M and A
620 adjust_return_value (basic_block bb
, tree m
, tree a
)
622 tree ret_stmt
= last_stmt (bb
), ret_var
, var
, stmt
, tmp
;
623 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
624 block_stmt_iterator bsi
= bsi_last (bb
);
626 gcc_assert (TREE_CODE (ret_stmt
) == RETURN_EXPR
);
628 ret_var
= TREE_OPERAND (ret_stmt
, 0);
632 if (TREE_CODE (ret_var
) == MODIFY_EXPR
)
634 ret_var
->common
.ann
= (tree_ann_t
) stmt_ann (ret_stmt
);
635 bsi_replace (&bsi
, ret_var
, true);
636 SSA_NAME_DEF_STMT (TREE_OPERAND (ret_var
, 0)) = ret_var
;
637 ret_var
= TREE_OPERAND (ret_var
, 0);
638 ret_stmt
= build1 (RETURN_EXPR
, TREE_TYPE (ret_stmt
), ret_var
);
639 bsi_insert_after (&bsi
, ret_stmt
, BSI_NEW_STMT
);
644 stmt
= build (MODIFY_EXPR
, ret_type
, NULL_TREE
,
645 build (MULT_EXPR
, ret_type
, m_acc
, ret_var
));
647 tmp
= create_tmp_var (ret_type
, "acc_tmp");
648 add_referenced_tmp_var (tmp
);
650 var
= make_ssa_name (tmp
, stmt
);
651 TREE_OPERAND (stmt
, 0) = var
;
652 bsi_insert_before (&bsi
, stmt
, BSI_SAME_STMT
);
659 stmt
= build (MODIFY_EXPR
, ret_type
, NULL_TREE
,
660 build (PLUS_EXPR
, ret_type
, a_acc
, var
));
662 tmp
= create_tmp_var (ret_type
, "acc_tmp");
663 add_referenced_tmp_var (tmp
);
665 var
= make_ssa_name (tmp
, stmt
);
666 TREE_OPERAND (stmt
, 0) = var
;
667 bsi_insert_before (&bsi
, stmt
, BSI_SAME_STMT
);
670 TREE_OPERAND (ret_stmt
, 0) = var
;
671 update_stmt (ret_stmt
);
674 /* Eliminates tail call described by T. TMP_VARS is a list of
675 temporary variables used to copy the function arguments. */
678 eliminate_tail_call (struct tailcall
*t
)
680 tree param
, stmt
, args
, rslt
, call
;
681 basic_block bb
, first
;
685 v_may_def_optype v_may_defs
;
687 block_stmt_iterator bsi
;
689 stmt
= bsi_stmt (t
->call_bsi
);
690 get_stmt_operands (stmt
);
691 ann
= stmt_ann (stmt
);
694 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
696 fprintf (dump_file
, "Eliminated tail recursion in bb %d : ",
698 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
699 fprintf (dump_file
, "\n");
702 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
703 stmt
= TREE_OPERAND (stmt
, 1);
705 first
= single_succ (ENTRY_BLOCK_PTR
);
707 /* Remove the code after call_bsi that will become unreachable. The
708 possibly unreachable code in other blocks is removed later in
712 while (!bsi_end_p (bsi
))
714 tree t
= bsi_stmt (bsi
);
715 /* Do not remove the return statement, so that redirect_edge_and_branch
716 sees how the block ends. */
717 if (TREE_CODE (t
) == RETURN_EXPR
)
724 /* Replace the call by a jump to the start of function. */
725 e
= redirect_edge_and_branch (single_succ_edge (t
->call_block
), first
);
727 PENDING_STMT (e
) = NULL_TREE
;
729 /* Add phi node entries for arguments. Not every PHI node corresponds to
730 a function argument (there may be PHI nodes for virtual definitions of the
731 eliminated calls), so we search for a PHI corresponding to each argument
732 rather than searching for which argument a PHI node corresponds to. */
734 for (param
= DECL_ARGUMENTS (current_function_decl
),
735 args
= TREE_OPERAND (stmt
, 1);
737 param
= TREE_CHAIN (param
),
738 args
= TREE_CHAIN (args
))
741 for (phi
= phi_nodes (first
); phi
; phi
= PHI_CHAIN (phi
))
742 if (param
== SSA_NAME_VAR (PHI_RESULT (phi
)))
745 /* The phi node indeed does not have to be there, in case the operand is
746 invariant in the function. */
750 add_phi_arg (phi
, TREE_VALUE (args
), e
);
753 /* Add phi nodes for the call clobbered variables. */
754 v_may_defs
= V_MAY_DEF_OPS (ann
);
755 for (i
= 0; i
< NUM_V_MAY_DEFS (v_may_defs
); i
++)
757 param
= SSA_NAME_VAR (V_MAY_DEF_RESULT (v_may_defs
, i
));
758 for (phi
= phi_nodes (first
); phi
; phi
= PHI_CHAIN (phi
))
759 if (param
== SSA_NAME_VAR (PHI_RESULT (phi
)))
764 tree name
= var_ann (param
)->default_def
;
769 /* It may happen that the tag does not have a default_def in case
770 when all uses of it are dominated by a MUST_DEF. This however
771 means that it is not necessary to add a phi node for this
775 new_name
= make_ssa_name (param
, SSA_NAME_DEF_STMT (name
));
777 var_ann (param
)->default_def
= new_name
;
778 phi
= create_phi_node (name
, first
);
779 SSA_NAME_DEF_STMT (name
) = phi
;
780 add_phi_arg (phi
, new_name
, single_succ_edge (ENTRY_BLOCK_PTR
));
782 /* For all calls the same set of variables should be clobbered. This
783 means that there always should be the appropriate phi node except
784 for the first time we eliminate the call. */
785 gcc_assert (EDGE_COUNT (first
->preds
) <= 2);
788 add_phi_arg (phi
, V_MAY_DEF_OP (v_may_defs
, i
), e
);
791 /* Update the values of accumulators. */
792 adjust_accumulator_values (t
->call_bsi
, t
->mult
, t
->add
, e
);
794 call
= bsi_stmt (t
->call_bsi
);
795 if (TREE_CODE (call
) == MODIFY_EXPR
)
797 rslt
= TREE_OPERAND (call
, 0);
799 /* Result of the call will no longer be defined. So adjust the
800 SSA_NAME_DEF_STMT accordingly. */
801 SSA_NAME_DEF_STMT (rslt
) = build_empty_stmt ();
804 bsi_remove (&t
->call_bsi
);
808 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
809 mark the tailcalls for the sibcall optimization. */
812 optimize_tail_call (struct tailcall
*t
, bool opt_tailcalls
)
814 if (t
->tail_recursion
)
816 eliminate_tail_call (t
);
822 tree stmt
= bsi_stmt (t
->call_bsi
);
824 stmt
= get_call_expr_in (stmt
);
825 CALL_EXPR_TAILCALL (stmt
) = 1;
826 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
828 fprintf (dump_file
, "Found tail call ");
829 print_generic_expr (dump_file
, stmt
, dump_flags
);
830 fprintf (dump_file
, " in bb %i\n", t
->call_block
->index
);
837 /* Optimizes tail calls in the function, turning the tail recursion
841 tree_optimize_tail_calls_1 (bool opt_tailcalls
)
844 bool phis_constructed
= false;
845 struct tailcall
*tailcalls
= NULL
, *act
, *next
;
846 bool changed
= false;
847 basic_block first
= single_succ (ENTRY_BLOCK_PTR
);
848 tree stmt
, param
, ret_type
, tmp
, phi
;
851 if (!suitable_for_tail_opt_p ())
854 opt_tailcalls
= suitable_for_tail_call_opt_p ();
856 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
858 /* Only traverse the normal exits, i.e. those that end with return
860 stmt
= last_stmt (e
->src
);
863 && TREE_CODE (stmt
) == RETURN_EXPR
)
864 find_tail_calls (e
->src
, &tailcalls
);
867 /* Construct the phi nodes and accumulators if necessary. */
868 a_acc
= m_acc
= NULL_TREE
;
869 for (act
= tailcalls
; act
; act
= act
->next
)
871 if (!act
->tail_recursion
)
874 if (!phis_constructed
)
876 /* Ensure that there is only one predecessor of the block. */
877 if (!single_pred_p (first
))
878 first
= split_edge (single_succ_edge (ENTRY_BLOCK_PTR
));
880 /* Copy the args if needed. */
881 for (param
= DECL_ARGUMENTS (current_function_decl
);
883 param
= TREE_CHAIN (param
))
884 if (is_gimple_reg (param
)
886 /* Also parameters that are only defined but never used need not
888 && (var_ann (param
)->default_def
889 && TREE_CODE (var_ann (param
)->default_def
) == SSA_NAME
))
891 tree name
= var_ann (param
)->default_def
;
892 tree new_name
= make_ssa_name (param
, SSA_NAME_DEF_STMT (name
));
895 var_ann (param
)->default_def
= new_name
;
896 phi
= create_phi_node (name
, first
);
897 SSA_NAME_DEF_STMT (name
) = phi
;
898 add_phi_arg (phi
, new_name
, single_pred_edge (first
));
900 phis_constructed
= true;
903 if (act
->add
&& !a_acc
)
905 ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
907 tmp
= create_tmp_var (ret_type
, "add_acc");
908 add_referenced_tmp_var (tmp
);
910 phi
= create_phi_node (tmp
, first
);
912 /* RET_TYPE can be a float when -ffast-maths is
914 fold_convert (ret_type
, integer_zero_node
),
915 single_pred_edge (first
));
916 a_acc
= PHI_RESULT (phi
);
919 if (act
->mult
&& !m_acc
)
921 ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
923 tmp
= create_tmp_var (ret_type
, "mult_acc");
924 add_referenced_tmp_var (tmp
);
926 phi
= create_phi_node (tmp
, first
);
928 /* RET_TYPE can be a float when -ffast-maths is
930 fold_convert (ret_type
, integer_one_node
),
931 single_pred_edge (first
));
932 m_acc
= PHI_RESULT (phi
);
936 for (; tailcalls
; tailcalls
= next
)
938 next
= tailcalls
->next
;
939 changed
|= optimize_tail_call (tailcalls
, opt_tailcalls
);
945 /* Modify the remaining return statements. */
946 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
948 stmt
= last_stmt (e
->src
);
951 && TREE_CODE (stmt
) == RETURN_EXPR
)
952 adjust_return_value (e
->src
, m_acc
, a_acc
);
958 free_dominance_info (CDI_DOMINATORS
);
964 execute_tail_recursion (void)
966 tree_optimize_tail_calls_1 (false);
970 gate_tail_calls (void)
972 return flag_optimize_sibling_calls
!= 0;
976 execute_tail_calls (void)
978 tree_optimize_tail_calls_1 (true);
981 struct tree_opt_pass pass_tail_recursion
=
985 execute_tail_recursion
, /* execute */
988 0, /* static_pass_number */
990 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
991 0, /* properties_provided */
992 0, /* properties_destroyed */
993 0, /* todo_flags_start */
994 TODO_dump_func
| TODO_verify_ssa
, /* todo_flags_finish */
998 struct tree_opt_pass pass_tail_calls
=
1001 gate_tail_calls
, /* gate */
1002 execute_tail_calls
, /* execute */
1005 0, /* static_pass_number */
1007 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1008 0, /* properties_provided */
1009 0, /* properties_destroyed */
1010 0, /* todo_flags_start */
1011 TODO_dump_func
| TODO_verify_ssa
, /* todo_flags_finish */