1 /* Tail call optimization on trees.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 #include "tree-flow.h"
31 #include "tree-dump.h"
32 #include "diagnostic.h"
34 #include "tree-pass.h"
36 #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)
135 referenced_var_iterator rvi;
141 /* No local variable nor structure field should be call-used. We
142 ignore any kind of memory tag, as these are not real variables. */
144 FOR_EACH_REFERENCED_VAR (var, rvi)
146 if (!is_global_var (var)
148 && (gimple_aliases_computed_p (cfun)? is_call_used (var)
149 : TREE_ADDRESSABLE (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 (cfun->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 (cfun->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 to 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 = GIMPLE_STMT_OPERAND (ass, 0);
276 tree src = GIMPLE_STMT_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_associative_math)
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, POINTER_PLUS_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, 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 /* Check for a call. */
398 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
400 ass_var = GIMPLE_STMT_OPERAND (stmt, 0);
401 call = GIMPLE_STMT_OPERAND (stmt, 1);
402 if (TREE_CODE (call) == WITH_SIZE_EXPR)
403 call = TREE_OPERAND (call, 0);
411 if (TREE_CODE (call) == CALL_EXPR)
414 /* If the statement has virtual or volatile operands, fail. */
415 ann = stmt_ann (stmt);
416 if (!ZERO_SSA_OPERANDS (stmt, (SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS))
417 || ann->has_volatile_ops
418 || (!gimple_aliases_computed_p (cfun) && ann->references_memory))
425 /* Recurse to the predecessors. */
426 FOR_EACH_EDGE (e, ei, bb->preds)
427 find_tail_calls (e->src, ret);
432 /* If the LHS of our call is not just a simple register, we can't
433 transform this into a tail or sibling call. This situation happens,
434 in (e.g.) "*p = foo()" where foo returns a struct. In this case
435 we won't have a temporary here, but we need to carry out the side
436 effect anyway, so tailcall is impossible.
438 ??? In some situations (when the struct is returned in memory via
439 invisible argument) we could deal with this, e.g. by passing 'p'
440 itself as that argument to foo, but it's too early to do this here,
441 and expand_call() will not handle it anyway. If it ever can, then
442 we need to revisit this here, to allow that situation. */
443 if (ass_var && !is_gimple_reg (ass_var))
446 /* We found the call, check whether it is suitable. */
447 tail_recursion = false;
448 func = get_callee_fndecl (call);
449 if (func == current_function_decl)
451 call_expr_arg_iterator iter;
453 for (param = DECL_ARGUMENTS (func),
454 arg = first_call_expr_arg (call, &iter);
456 param = TREE_CHAIN (param), arg = next_call_expr_arg (&iter))
460 /* Make sure there are no problems with copying. The parameter
461 have a copyable type and the two arguments must have reasonably
462 equivalent types. The latter requirement could be relaxed if
463 we emitted a suitable type conversion statement. */
464 if (!is_gimple_reg_type (TREE_TYPE (param))
465 || !useless_type_conversion_p (TREE_TYPE (param),
469 /* The parameter should be a real operand, so that phi node
470 created for it at the start of the function has the meaning
471 of copying the value. This test implies is_gimple_reg_type
472 from the previous condition, however this one could be
473 relaxed by being more careful with copying the new value
474 of the parameter (emitting appropriate GIMPLE_MODIFY_STMT and
475 updating the virtual operands). */
476 if (!is_gimple_reg (param))
481 tail_recursion = true;
484 /* Now check the statements after the call. None of them has virtual
485 operands, so they may only depend on the call through its return
486 value. The return value should also be dependent on each of them,
487 since we are running after dce. */
497 while (bsi_end_p (absi))
499 ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
500 abb = single_succ (abb);
501 absi = bsi_start (abb);
504 stmt = bsi_stmt (absi);
506 if (TREE_CODE (stmt) == LABEL_EXPR)
509 if (TREE_CODE (stmt) == RETURN_EXPR)
512 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
515 if (!process_assignment (stmt, stmt, bsi, &m, &a, &ass_var))
519 /* See if this is a tail call we can handle. */
520 ret_var = TREE_OPERAND (stmt, 0);
522 && TREE_CODE (ret_var) == GIMPLE_MODIFY_STMT)
524 tree ret_op = GIMPLE_STMT_OPERAND (ret_var, 1);
527 && TREE_CODE (ret_op) != SSA_NAME)
530 if (!process_assignment (ret_var, stmt, bsi, &m, &a, &ass_var))
532 ret_var = GIMPLE_STMT_OPERAND (ret_var, 0);
535 /* We may proceed if there either is no return value, or the return value
536 is identical to the call's return. */
538 && (ret_var != ass_var))
541 /* If this is not a tail recursive call, we cannot handle addends or
543 if (!tail_recursion && (m || a))
546 nw = XNEW (struct tailcall);
551 nw->tail_recursion = tail_recursion;
560 /* Adjust the accumulator values according to A and M after BSI, and update
561 the phi nodes on edge BACK. */
564 adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back)
566 tree stmt, var, phi, tmp;
567 tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
568 tree a_acc_arg = a_acc, m_acc_arg = m_acc;
574 if (integer_onep (a))
578 stmt = build_gimple_modify_stmt (NULL_TREE,
579 build2 (MULT_EXPR, ret_type,
582 tmp = create_tmp_var (ret_type, "acc_tmp");
583 add_referenced_var (tmp);
585 var = make_ssa_name (tmp, stmt);
586 GIMPLE_STMT_OPERAND (stmt, 0) = var;
587 bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
593 stmt = build_gimple_modify_stmt (NULL_TREE, build2 (PLUS_EXPR, ret_type,
595 var = make_ssa_name (SSA_NAME_VAR (a_acc), stmt);
596 GIMPLE_STMT_OPERAND (stmt, 0) = var;
597 bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
603 stmt = build_gimple_modify_stmt (NULL_TREE,
604 build2 (MULT_EXPR, ret_type,
606 var = make_ssa_name (SSA_NAME_VAR (m_acc), stmt);
607 GIMPLE_STMT_OPERAND (stmt, 0) = var;
608 bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
614 for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
615 if (PHI_RESULT (phi) == a_acc)
618 add_phi_arg (phi, a_acc_arg, back);
623 for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
624 if (PHI_RESULT (phi) == m_acc)
627 add_phi_arg (phi, m_acc_arg, back);
631 /* Adjust value of the return at the end of BB according to M and A
635 adjust_return_value (basic_block bb, tree m, tree a)
637 tree ret_stmt = last_stmt (bb), ret_var, var, stmt, tmp;
638 tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
640 block_stmt_iterator bsi = bsi_last (bb);
642 gcc_assert (TREE_CODE (ret_stmt) == RETURN_EXPR);
644 ret_var = TREE_OPERAND (ret_stmt, 0);
648 if (TREE_CODE (ret_var) == GIMPLE_MODIFY_STMT)
650 ret_op = &GIMPLE_STMT_OPERAND (ret_var, 1);
654 ret_op = &TREE_OPERAND (ret_stmt, 0);
658 stmt = build_gimple_modify_stmt (NULL_TREE,
659 build2 (MULT_EXPR, ret_type,
662 tmp = create_tmp_var (ret_type, "acc_tmp");
663 add_referenced_var (tmp);
665 var = make_ssa_name (tmp, stmt);
666 GIMPLE_STMT_OPERAND (stmt, 0) = var;
667 bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
674 stmt = build_gimple_modify_stmt (NULL_TREE,
675 build2 (PLUS_EXPR, ret_type,
678 tmp = create_tmp_var (ret_type, "acc_tmp");
679 add_referenced_var (tmp);
681 var = make_ssa_name (tmp, stmt);
682 GIMPLE_STMT_OPERAND (stmt, 0) = var;
683 bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
687 update_stmt (ret_stmt);
690 /* Subtract COUNT and FREQUENCY from the basic block and it's
693 decrease_profile (basic_block bb, gcov_type count, int frequency)
699 bb->frequency -= frequency;
700 if (bb->frequency < 0)
702 if (!single_succ_p (bb))
704 gcc_assert (!EDGE_COUNT (bb->succs));
707 e = single_succ_edge (bb);
713 /* Returns true if argument PARAM of the tail recursive call needs to be copied
714 when the call is eliminated. */
717 arg_needs_copy_p (tree param)
721 if (!is_gimple_reg (param) || !var_ann (param))
724 /* Parameters that are only defined but never used need not be copied. */
725 def = gimple_default_def (cfun, param);
732 /* Eliminates tail call described by T. TMP_VARS is a list of
733 temporary variables used to copy the function arguments. */
736 eliminate_tail_call (struct tailcall *t)
738 tree param, stmt, rslt, call;
740 call_expr_arg_iterator iter;
741 basic_block bb, first;
744 block_stmt_iterator bsi;
747 stmt = orig_stmt = bsi_stmt (t->call_bsi);
750 if (dump_file && (dump_flags & TDF_DETAILS))
752 fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
754 print_generic_stmt (dump_file, stmt, TDF_SLIM);
755 fprintf (dump_file, "\n");
758 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
759 stmt = GIMPLE_STMT_OPERAND (stmt, 1);
761 first = single_succ (ENTRY_BLOCK_PTR);
763 /* Remove the code after call_bsi that will become unreachable. The
764 possibly unreachable code in other blocks is removed later in
768 while (!bsi_end_p (bsi))
770 tree t = bsi_stmt (bsi);
771 /* Do not remove the return statement, so that redirect_edge_and_branch
772 sees how the block ends. */
773 if (TREE_CODE (t) == RETURN_EXPR)
776 bsi_remove (&bsi, true);
780 /* Number of executions of function has reduced by the tailcall. */
781 e = single_succ_edge (t->call_block);
782 decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
783 decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
784 if (e->dest != EXIT_BLOCK_PTR)
785 decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
787 /* Replace the call by a jump to the start of function. */
788 e = redirect_edge_and_branch (single_succ_edge (t->call_block), first);
790 PENDING_STMT (e) = NULL_TREE;
792 /* Add phi node entries for arguments. The ordering of the phi nodes should
793 be the same as the ordering of the arguments. */
794 for (param = DECL_ARGUMENTS (current_function_decl),
795 arg = first_call_expr_arg (stmt, &iter),
796 phi = phi_nodes (first);
798 param = TREE_CHAIN (param), arg = next_call_expr_arg (&iter))
800 if (!arg_needs_copy_p (param))
802 gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
804 add_phi_arg (phi, arg, e);
805 phi = PHI_CHAIN (phi);
808 /* Update the values of accumulators. */
809 adjust_accumulator_values (t->call_bsi, t->mult, t->add, e);
811 call = bsi_stmt (t->call_bsi);
812 if (TREE_CODE (call) == GIMPLE_MODIFY_STMT)
814 rslt = GIMPLE_STMT_OPERAND (call, 0);
816 /* Result of the call will no longer be defined. So adjust the
817 SSA_NAME_DEF_STMT accordingly. */
818 SSA_NAME_DEF_STMT (rslt) = build_empty_stmt ();
821 bsi_remove (&t->call_bsi, true);
825 /* Add phi nodes for the virtual operands defined in the function to the
826 header of the loop created by tail recursion elimination.
828 Originally, we used to add phi nodes only for call clobbered variables,
829 as the value of the non-call clobbered ones obviously cannot be used
830 or changed within the recursive call. However, the local variables
831 from multiple calls now share the same location, so the virtual ssa form
832 requires us to say that the location dies on further iterations of the loop,
833 which requires adding phi nodes.
836 add_virtual_phis (void)
838 referenced_var_iterator rvi;
841 /* The problematic part is that there is no way how to know what
842 to put into phi nodes (there in fact does not have to be such
843 ssa name available). A solution would be to have an artificial
844 use/kill for all virtual operands in EXIT node. Unless we have
845 this, we cannot do much better than to rebuild the ssa form for
846 possibly affected virtual ssa names from scratch. */
848 FOR_EACH_REFERENCED_VAR (var, rvi)
850 if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
851 mark_sym_for_renaming (var);
855 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
856 mark the tailcalls for the sibcall optimization. */
859 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
861 if (t->tail_recursion)
863 eliminate_tail_call (t);
869 tree stmt = bsi_stmt (t->call_bsi);
871 stmt = get_call_expr_in (stmt);
872 CALL_EXPR_TAILCALL (stmt) = 1;
873 if (dump_file && (dump_flags & TDF_DETAILS))
875 fprintf (dump_file, "Found tail call ");
876 print_generic_expr (dump_file, stmt, dump_flags);
877 fprintf (dump_file, " in bb %i\n", t->call_block->index);
884 /* Optimizes tail calls in the function, turning the tail recursion
888 tree_optimize_tail_calls_1 (bool opt_tailcalls)
891 bool phis_constructed = false;
892 struct tailcall *tailcalls = NULL, *act, *next;
893 bool changed = false;
894 basic_block first = single_succ (ENTRY_BLOCK_PTR);
895 tree stmt, param, ret_type, tmp, phi;
898 if (!suitable_for_tail_opt_p ())
901 opt_tailcalls = suitable_for_tail_call_opt_p ();
903 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
905 /* Only traverse the normal exits, i.e. those that end with return
907 stmt = last_stmt (e->src);
910 && TREE_CODE (stmt) == RETURN_EXPR)
911 find_tail_calls (e->src, &tailcalls);
914 /* Construct the phi nodes and accumulators if necessary. */
915 a_acc = m_acc = NULL_TREE;
916 for (act = tailcalls; act; act = act->next)
918 if (!act->tail_recursion)
921 if (!phis_constructed)
923 /* Ensure that there is only one predecessor of the block. */
924 if (!single_pred_p (first))
925 first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
927 /* Copy the args if needed. */
928 for (param = DECL_ARGUMENTS (current_function_decl);
930 param = TREE_CHAIN (param))
931 if (arg_needs_copy_p (param))
933 tree name = gimple_default_def (cfun, param);
934 tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
937 set_default_def (param, new_name);
938 phi = create_phi_node (name, first);
939 SSA_NAME_DEF_STMT (name) = phi;
940 add_phi_arg (phi, new_name, single_pred_edge (first));
942 phis_constructed = true;
945 if (act->add && !a_acc)
947 ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
949 tmp = create_tmp_var (ret_type, "add_acc");
950 add_referenced_var (tmp);
952 phi = create_phi_node (tmp, first);
954 /* RET_TYPE can be a float when -ffast-maths is
956 fold_convert (ret_type, integer_zero_node),
957 single_pred_edge (first));
958 a_acc = PHI_RESULT (phi);
961 if (act->mult && !m_acc)
963 ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
965 tmp = create_tmp_var (ret_type, "mult_acc");
966 add_referenced_var (tmp);
968 phi = create_phi_node (tmp, first);
970 /* RET_TYPE can be a float when -ffast-maths is
972 fold_convert (ret_type, integer_one_node),
973 single_pred_edge (first));
974 m_acc = PHI_RESULT (phi);
979 if (phis_constructed)
981 /* Reverse the order of the phi nodes, so that it matches the order
982 of operands of the function, as assumed by eliminate_tail_call. */
983 set_phi_nodes (first, phi_reverse (phi_nodes (first)));
986 for (; tailcalls; tailcalls = next)
988 next = tailcalls->next;
989 changed |= optimize_tail_call (tailcalls, opt_tailcalls);
995 /* Modify the remaining return statements. */
996 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
998 stmt = last_stmt (e->src);
1001 && TREE_CODE (stmt) == RETURN_EXPR)
1002 adjust_return_value (e->src, m_acc, a_acc);
1007 free_dominance_info (CDI_DOMINATORS);
1009 if (phis_constructed)
1010 add_virtual_phis ();
1012 return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
1017 execute_tail_recursion (void)
1019 return tree_optimize_tail_calls_1 (false);
1023 gate_tail_calls (void)
1025 return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
1029 execute_tail_calls (void)
1031 return tree_optimize_tail_calls_1 (true);
1034 struct gimple_opt_pass pass_tail_recursion =
1039 gate_tail_calls, /* gate */
1040 execute_tail_recursion, /* execute */
1043 0, /* static_pass_number */
1045 PROP_cfg | PROP_ssa, /* properties_required */
1046 0, /* properties_provided */
1047 0, /* properties_destroyed */
1048 0, /* todo_flags_start */
1049 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
1053 struct gimple_opt_pass pass_tail_calls =
1058 gate_tail_calls, /* gate */
1059 execute_tail_calls, /* execute */
1062 0, /* static_pass_number */
1064 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1065 0, /* properties_provided */
1066 0, /* properties_destroyed */
1067 0, /* todo_flags_start */
1068 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */