1 /* Tail call optimization on trees.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
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"
40 /* The file implements the tail recursion elimination. It is also used to
41 analyze the tail calls in general, passing the results to the rtl level
42 where they are used for sibcall optimization.
44 In addition to the standard tail recursion elimination, we handle the most
45 trivial cases of making the call tail recursive by creating accumulators.
46 For example the following function
51 return n + sum (n - 1);
68 To do this, we maintain two accumulators (a_acc and m_acc) that indicate
69 when we reach the return x statement, we should return a_acc + x * m_acc
70 instead. They are initially initialized to 0 and 1, respectively,
71 so the semantics of the function is obviously preserved. If we are
72 guaranteed that the value of the accumulator never change, we
75 There are three cases how the function may exit. The first one is
76 handled in adjust_return_value, the other two in adjust_accumulator_values
77 (the second case is actually a special case of the third one and we
78 present it separately just for clarity):
80 1) Just return x, where x is not in any of the remaining special shapes.
81 We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
83 2) return f (...), where f is the current function, is rewritten in a
84 classical tail-recursion elimination way, into assignment of arguments
85 and jump to the start of the function. Values of the accumulators
88 3) return a + m * f(...), where a and m do not depend on call to f.
89 To preserve the semantics described before we want this to be rewritten
90 in such a way that we finally return
92 a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
94 I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
95 eliminate the tail call to f. Special cases when the value is just
96 added or just multiplied are obtained by setting a = 0 or m = 1.
98 TODO -- it is possible to do similar tricks for other operations. */
100 /* A structure that describes the tailcall. */
104 /* The iterator pointing to the call statement. */
105 gimple_stmt_iterator call_gsi;
107 /* True if it is a call to the current function. */
110 /* The return value of the caller is mult * f + add, where f is the return
111 value of the call. */
114 /* Next tailcall in the chain. */
115 struct tailcall *next;
118 /* The variables holding the value of multiplicative and additive
120 static tree m_acc, a_acc;
122 static bool suitable_for_tail_opt_p (void);
123 static bool optimize_tail_call (struct tailcall *, bool);
124 static void eliminate_tail_call (struct tailcall *);
125 static void find_tail_calls (basic_block, struct tailcall **);
127 /* Returns false when the function is not suitable for tail call optimization
128 from some reason (e.g. if it takes variable number of arguments). */
131 suitable_for_tail_opt_p (void)
133 referenced_var_iterator rvi;
139 /* No local variable nor structure field should be call-used. We
140 ignore any kind of memory tag, as these are not real variables. */
142 FOR_EACH_REFERENCED_VAR (var, rvi)
144 if (!is_global_var (var)
146 && (gimple_aliases_computed_p (cfun)? is_call_used (var)
147 : TREE_ADDRESSABLE (var)))
153 /* Returns false when the function is not suitable for tail call optimization
154 from some reason (e.g. if it takes variable number of arguments).
155 This test must pass in addition to suitable_for_tail_opt_p in order to make
156 tail call discovery happen. */
159 suitable_for_tail_call_opt_p (void)
163 /* alloca (until we have stack slot life analysis) inhibits
164 sibling call optimizations, but not tail recursion. */
165 if (cfun->calls_alloca)
168 /* If we are using sjlj exceptions, we may need to add a call to
169 _Unwind_SjLj_Unregister at exit of the function. Which means
170 that we cannot do any sibcall transformations. */
171 if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ())
174 /* Any function that calls setjmp might have longjmp called from
175 any called function. ??? We really should represent this
176 properly in the CFG so that this needn't be special cased. */
177 if (cfun->calls_setjmp)
180 /* ??? It is OK if the argument of a function is taken in some cases,
181 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
182 for (param = DECL_ARGUMENTS (current_function_decl);
184 param = TREE_CHAIN (param))
185 if (TREE_ADDRESSABLE (param))
191 /* Checks whether the expression EXPR in stmt AT is independent of the
192 statement pointed to by GSI (in a sense that we already know EXPR's value
193 at GSI). We use the fact that we are only called from the chain of
194 basic blocks that have only single successor. Returns the expression
195 containing the value of EXPR at GSI. */
198 independent_of_stmt_p (tree expr, gimple at, gimple_stmt_iterator gsi)
200 basic_block bb, call_bb, at_bb;
204 if (is_gimple_min_invariant (expr))
207 if (TREE_CODE (expr) != SSA_NAME)
210 /* Mark the blocks in the chain leading to the end. */
211 at_bb = gimple_bb (at);
212 call_bb = gimple_bb (gsi_stmt (gsi));
213 for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
219 at = SSA_NAME_DEF_STMT (expr);
222 /* The default definition or defined before the chain. */
228 for (; !gsi_end_p (gsi); gsi_next (&gsi))
229 if (gsi_stmt (gsi) == at)
232 if (!gsi_end_p (gsi))
237 if (gimple_code (at) != GIMPLE_PHI)
243 FOR_EACH_EDGE (e, ei, bb->preds)
248 expr = PHI_ARG_DEF_FROM_EDGE (at, e);
249 if (TREE_CODE (expr) != SSA_NAME)
251 /* The value is a constant. */
256 /* Unmark the blocks. */
257 for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
264 /* Simulates the effect of an assignment STMT on the return value of the tail
265 recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
266 additive factor for the real return value. */
269 process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
270 tree *a, tree *ass_var)
272 tree op0, op1, non_ass_var;
273 tree dest = gimple_assign_lhs (stmt);
274 enum tree_code code = gimple_assign_rhs_code (stmt);
275 enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
276 tree src_var = gimple_assign_rhs1 (stmt);
278 /* See if this is a simple copy operation of an SSA name to the function
279 result. In that case we may have a simple tail call. Ignore type
280 conversions that can never produce extra code between the function
281 call and the function return. */
282 if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt))
283 && (TREE_CODE (src_var) == SSA_NAME))
285 /* Reject a tailcall if the type conversion might need
287 if (gimple_assign_cast_p (stmt)
288 && TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var)))
291 if (src_var != *ass_var)
298 if (rhs_class != GIMPLE_BINARY_RHS)
301 /* Accumulator optimizations will reverse the order of operations.
302 We can only do that for floating-point types if we're assuming
303 that addition and multiplication are associative. */
304 if (!flag_associative_math)
305 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
308 /* We only handle the code like
315 TODO -- Extend it for cases where the linear transformation of the output
316 is expressed in a more complicated way. */
318 op0 = gimple_assign_rhs1 (stmt);
319 op1 = gimple_assign_rhs2 (stmt);
322 && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
324 else if (op1 == *ass_var
325 && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
333 /* There should be no previous addition. TODO -- it should be fairly
334 straightforward to lift this restriction -- just allow storing
335 more complicated expressions in *A, and gimplify it in
336 adjust_accumulator_values. */
344 /* Similar remark applies here. Handling multiplication after addition
345 is just slightly more complicated -- we need to multiply both *A and
353 /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR,
354 POINTER_PLUS_EXPR). */
361 /* Propagate VAR through phis on edge E. */
364 propagate_through_phis (tree var, edge e)
366 basic_block dest = e->dest;
367 gimple_stmt_iterator gsi;
369 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
371 gimple phi = gsi_stmt (gsi);
372 if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
373 return PHI_RESULT (phi);
378 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
379 added to the start of RET. */
382 find_tail_calls (basic_block bb, struct tailcall **ret)
384 tree ass_var = NULL_TREE, ret_var, func, param;
385 gimple stmt, call = NULL;
386 gimple_stmt_iterator gsi, agsi;
394 if (!single_succ_p (bb))
397 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
399 stmt = gsi_stmt (gsi);
402 if (gimple_code (stmt) == GIMPLE_LABEL)
405 /* Check for a call. */
406 if (is_gimple_call (stmt))
409 ass_var = gimple_call_lhs (stmt);
413 /* If the statement has virtual or volatile operands, fail. */
414 if (!ZERO_SSA_OPERANDS (stmt, (SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS))
415 || gimple_has_volatile_ops (stmt)
416 || (!gimple_aliases_computed_p (cfun)
417 && gimple_references_memory_p (stmt)))
424 /* Recurse to the predecessors. */
425 FOR_EACH_EDGE (e, ei, bb->preds)
426 find_tail_calls (e->src, ret);
431 /* If the LHS of our call is not just a simple register, we can't
432 transform this into a tail or sibling call. This situation happens,
433 in (e.g.) "*p = foo()" where foo returns a struct. In this case
434 we won't have a temporary here, but we need to carry out the side
435 effect anyway, so tailcall is impossible.
437 ??? In some situations (when the struct is returned in memory via
438 invisible argument) we could deal with this, e.g. by passing 'p'
439 itself as that argument to foo, but it's too early to do this here,
440 and expand_call() will not handle it anyway. If it ever can, then
441 we need to revisit this here, to allow that situation. */
442 if (ass_var && !is_gimple_reg (ass_var))
445 /* We found the call, check whether it is suitable. */
446 tail_recursion = false;
447 func = gimple_call_fndecl (call);
448 if (func == current_function_decl)
451 for (param = DECL_ARGUMENTS (func), idx = 0;
452 param && idx < gimple_call_num_args (call);
453 param = TREE_CHAIN (param), idx ++)
455 arg = gimple_call_arg (call, idx);
458 /* Make sure there are no problems with copying. The parameter
459 have a copyable type and the two arguments must have reasonably
460 equivalent types. The latter requirement could be relaxed if
461 we emitted a suitable type conversion statement. */
462 if (!is_gimple_reg_type (TREE_TYPE (param))
463 || !useless_type_conversion_p (TREE_TYPE (param),
467 /* The parameter should be a real operand, so that phi node
468 created for it at the start of the function has the meaning
469 of copying the value. This test implies is_gimple_reg_type
470 from the previous condition, however this one could be
471 relaxed by being more careful with copying the new value
472 of the parameter (emitting appropriate GIMPLE_ASSIGN and
473 updating the virtual operands). */
474 if (!is_gimple_reg (param))
478 if (idx == gimple_call_num_args (call) && !param)
479 tail_recursion = true;
482 /* Now check the statements after the call. None of them has virtual
483 operands, so they may only depend on the call through its return
484 value. The return value should also be dependent on each of them,
485 since we are running after dce. */
495 while (gsi_end_p (agsi))
497 ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
498 abb = single_succ (abb);
499 agsi = gsi_start_bb (abb);
502 stmt = gsi_stmt (agsi);
504 if (gimple_code (stmt) == GIMPLE_LABEL)
507 if (gimple_code (stmt) == GIMPLE_RETURN)
510 if (gimple_code (stmt) != GIMPLE_ASSIGN)
513 /* This is a gimple assign. */
514 if (! process_assignment (stmt, gsi, &m, &a, &ass_var))
518 /* See if this is a tail call we can handle. */
519 ret_var = gimple_return_retval (stmt);
521 /* We may proceed if there either is no return value, or the return value
522 is identical to the call's return. */
524 && (ret_var != ass_var))
527 /* If this is not a tail recursive call, we cannot handle addends or
529 if (!tail_recursion && (m || a))
532 nw = XNEW (struct tailcall);
536 nw->tail_recursion = tail_recursion;
545 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
548 add_successor_phi_arg (edge e, tree var, tree phi_arg)
550 gimple_stmt_iterator gsi;
552 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
553 if (PHI_RESULT (gsi_stmt (gsi)) == var)
556 gcc_assert (!gsi_end_p (gsi));
557 add_phi_arg (gsi_stmt (gsi), phi_arg, e);
560 /* Creates a GIMPLE statement which computes the operation specified by
561 CODE, OP0 and OP1 to a new variable with name LABEL and inserts the
562 statement in the position specified by GSI and UPDATE. Returns the
563 tree node of the statement's result. */
566 adjust_return_value_with_ops (enum tree_code code, const char *label,
567 tree op0, tree op1, gimple_stmt_iterator gsi,
568 enum gsi_iterator_update update)
571 tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
572 tree tmp = create_tmp_var (ret_type, label);
573 gimple stmt = gimple_build_assign_with_ops (code, tmp, op0, op1);
576 add_referenced_var (tmp);
577 result = make_ssa_name (tmp, stmt);
578 gimple_assign_set_lhs (stmt, result);
580 gsi_insert_before (&gsi, stmt, update);
584 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
585 the computation specified by CODE and OP1 and insert the statement
586 at the position specified by GSI as a new statement. Returns new SSA name
587 of updated accumulator. */
590 update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
591 gimple_stmt_iterator gsi)
593 gimple stmt = gimple_build_assign_with_ops (code, SSA_NAME_VAR (acc), acc,
595 tree var = make_ssa_name (SSA_NAME_VAR (acc), stmt);
596 gimple_assign_set_lhs (stmt, var);
598 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
602 /* Adjust the accumulator values according to A and M after GSI, and update
603 the phi nodes on edge BACK. */
606 adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
608 tree var, a_acc_arg = a_acc, m_acc_arg = m_acc;
614 if (integer_onep (a))
617 var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
618 a, gsi, GSI_NEW_STMT);
623 a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
627 m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
630 add_successor_phi_arg (back, a_acc, a_acc_arg);
633 add_successor_phi_arg (back, m_acc, m_acc_arg);
636 /* Adjust value of the return at the end of BB according to M and A
640 adjust_return_value (basic_block bb, tree m, tree a)
643 gimple ret_stmt = gimple_seq_last_stmt (bb_seq (bb));
644 gimple_stmt_iterator gsi = gsi_last_bb (bb);
646 gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
648 retval = gimple_return_retval (ret_stmt);
649 if (!retval || retval == error_mark_node)
653 retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
656 retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
658 gimple_return_set_retval (ret_stmt, retval);
659 update_stmt (ret_stmt);
662 /* Subtract COUNT and FREQUENCY from the basic block and it's
665 decrease_profile (basic_block bb, gcov_type count, int frequency)
671 bb->frequency -= frequency;
672 if (bb->frequency < 0)
674 if (!single_succ_p (bb))
676 gcc_assert (!EDGE_COUNT (bb->succs));
679 e = single_succ_edge (bb);
685 /* Returns true if argument PARAM of the tail recursive call needs to be copied
686 when the call is eliminated. */
689 arg_needs_copy_p (tree param)
693 if (!is_gimple_reg (param) || !var_ann (param))
696 /* Parameters that are only defined but never used need not be copied. */
697 def = gimple_default_def (cfun, param);
704 /* Eliminates tail call described by T. TMP_VARS is a list of
705 temporary variables used to copy the function arguments. */
708 eliminate_tail_call (struct tailcall *t)
714 basic_block bb, first;
717 gimple_stmt_iterator gsi;
720 stmt = orig_stmt = gsi_stmt (t->call_gsi);
721 bb = gsi_bb (t->call_gsi);
723 if (dump_file && (dump_flags & TDF_DETAILS))
725 fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
727 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
728 fprintf (dump_file, "\n");
731 gcc_assert (is_gimple_call (stmt));
733 first = single_succ (ENTRY_BLOCK_PTR);
735 /* Remove the code after call_gsi that will become unreachable. The
736 possibly unreachable code in other blocks is removed later in
740 while (!gsi_end_p (gsi))
742 gimple t = gsi_stmt (gsi);
743 /* Do not remove the return statement, so that redirect_edge_and_branch
744 sees how the block ends. */
745 if (gimple_code (t) == GIMPLE_RETURN)
748 gsi_remove (&gsi, true);
752 /* Number of executions of function has reduced by the tailcall. */
753 e = single_succ_edge (gsi_bb (t->call_gsi));
754 decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
755 decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
756 if (e->dest != EXIT_BLOCK_PTR)
757 decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
759 /* Replace the call by a jump to the start of function. */
760 e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)),
763 PENDING_STMT (e) = NULL;
765 /* Add phi node entries for arguments. The ordering of the phi nodes should
766 be the same as the ordering of the arguments. */
767 for (param = DECL_ARGUMENTS (current_function_decl),
768 idx = 0, gsi = gsi_start_phis (first);
770 param = TREE_CHAIN (param), idx++)
772 if (!arg_needs_copy_p (param))
775 arg = gimple_call_arg (stmt, idx);
776 phi = gsi_stmt (gsi);
777 gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
779 add_phi_arg (phi, arg, e);
783 /* Update the values of accumulators. */
784 adjust_accumulator_values (t->call_gsi, t->mult, t->add, e);
786 call = gsi_stmt (t->call_gsi);
787 rslt = gimple_call_lhs (call);
788 if (rslt != NULL_TREE)
790 /* Result of the call will no longer be defined. So adjust the
791 SSA_NAME_DEF_STMT accordingly. */
792 SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
795 gsi_remove (&t->call_gsi, true);
799 /* Add phi nodes for the virtual operands defined in the function to the
800 header of the loop created by tail recursion elimination.
802 Originally, we used to add phi nodes only for call clobbered variables,
803 as the value of the non-call clobbered ones obviously cannot be used
804 or changed within the recursive call. However, the local variables
805 from multiple calls now share the same location, so the virtual ssa form
806 requires us to say that the location dies on further iterations of the loop,
807 which requires adding phi nodes.
810 add_virtual_phis (void)
812 referenced_var_iterator rvi;
815 /* The problematic part is that there is no way how to know what
816 to put into phi nodes (there in fact does not have to be such
817 ssa name available). A solution would be to have an artificial
818 use/kill for all virtual operands in EXIT node. Unless we have
819 this, we cannot do much better than to rebuild the ssa form for
820 possibly affected virtual ssa names from scratch. */
822 FOR_EACH_REFERENCED_VAR (var, rvi)
824 if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
825 mark_sym_for_renaming (var);
829 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
830 mark the tailcalls for the sibcall optimization. */
833 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
835 if (t->tail_recursion)
837 eliminate_tail_call (t);
843 gimple stmt = gsi_stmt (t->call_gsi);
845 gimple_call_set_tail (stmt, true);
846 if (dump_file && (dump_flags & TDF_DETAILS))
848 fprintf (dump_file, "Found tail call ");
849 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
850 fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
857 /* Creates a tail-call accumulator of the same type as the return type of the
858 current function. LABEL is the name used to creating the temporary
859 variable for the accumulator. The accumulator will be inserted in the
860 phis of a basic block BB with single predecessor with an initial value
861 INIT converted to the current function return type. */
864 create_tailcall_accumulator (const char *label, basic_block bb, tree init)
866 tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
867 tree tmp = create_tmp_var (ret_type, label);
870 add_referenced_var (tmp);
871 phi = create_phi_node (tmp, bb);
872 /* RET_TYPE can be a float when -ffast-maths is enabled. */
873 add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb));
874 return PHI_RESULT (phi);
877 /* Optimizes tail calls in the function, turning the tail recursion
881 tree_optimize_tail_calls_1 (bool opt_tailcalls)
884 bool phis_constructed = false;
885 struct tailcall *tailcalls = NULL, *act, *next;
886 bool changed = false;
887 basic_block first = single_succ (ENTRY_BLOCK_PTR);
892 if (!suitable_for_tail_opt_p ())
895 opt_tailcalls = suitable_for_tail_call_opt_p ();
897 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
899 /* Only traverse the normal exits, i.e. those that end with return
901 stmt = last_stmt (e->src);
904 && gimple_code (stmt) == GIMPLE_RETURN)
905 find_tail_calls (e->src, &tailcalls);
908 /* Construct the phi nodes and accumulators if necessary. */
909 a_acc = m_acc = NULL_TREE;
910 for (act = tailcalls; act; act = act->next)
912 if (!act->tail_recursion)
915 if (!phis_constructed)
917 /* Ensure that there is only one predecessor of the block. */
918 if (!single_pred_p (first))
919 first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
921 /* Copy the args if needed. */
922 for (param = DECL_ARGUMENTS (current_function_decl);
924 param = TREE_CHAIN (param))
925 if (arg_needs_copy_p (param))
927 tree name = gimple_default_def (cfun, param);
928 tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
931 set_default_def (param, new_name);
932 phi = create_phi_node (name, first);
933 SSA_NAME_DEF_STMT (name) = phi;
934 add_phi_arg (phi, new_name, single_pred_edge (first));
936 phis_constructed = true;
939 if (act->add && !a_acc)
940 a_acc = create_tailcall_accumulator ("add_acc", first,
943 if (act->mult && !m_acc)
944 m_acc = create_tailcall_accumulator ("mult_acc", first,
948 for (; tailcalls; tailcalls = next)
950 next = tailcalls->next;
951 changed |= optimize_tail_call (tailcalls, opt_tailcalls);
957 /* Modify the remaining return statements. */
958 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
960 stmt = last_stmt (e->src);
963 && gimple_code (stmt) == GIMPLE_RETURN)
964 adjust_return_value (e->src, m_acc, a_acc);
969 free_dominance_info (CDI_DOMINATORS);
971 if (phis_constructed)
974 return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
979 execute_tail_recursion (void)
981 return tree_optimize_tail_calls_1 (false);
985 gate_tail_calls (void)
987 return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
991 execute_tail_calls (void)
993 return tree_optimize_tail_calls_1 (true);
996 struct gimple_opt_pass pass_tail_recursion =
1001 gate_tail_calls, /* gate */
1002 execute_tail_recursion, /* execute */
1005 0, /* static_pass_number */
1007 PROP_cfg | PROP_ssa, /* 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 */
1015 struct gimple_opt_pass pass_tail_calls =
1020 gate_tail_calls, /* gate */
1021 execute_tail_calls, /* execute */
1024 0, /* static_pass_number */
1026 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1027 0, /* properties_provided */
1028 0, /* properties_destroyed */
1029 0, /* todo_flags_start */
1030 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */