1 /* Tail call optimization on trees.
2 Copyright (C) 2003-2013 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"
26 #include "basic-block.h"
29 #include "gimple-iterator.h"
30 #include "gimple-ssa.h"
32 #include "tree-phinodes.h"
33 #include "tree-ssanames.h"
34 #include "tree-into-ssa.h"
36 #include "gimple-pretty-print.h"
38 #include "tree-pass.h"
40 #include "langhooks.h"
44 #include "common/common-target.h"
45 #include "ipa-utils.h"
47 /* The file implements the tail recursion elimination. It is also used to
48 analyze the tail calls in general, passing the results to the rtl level
49 where they are used for sibcall optimization.
51 In addition to the standard tail recursion elimination, we handle the most
52 trivial cases of making the call tail recursive by creating accumulators.
53 For example the following function
58 return n + sum (n - 1);
75 To do this, we maintain two accumulators (a_acc and m_acc) that indicate
76 when we reach the return x statement, we should return a_acc + x * m_acc
77 instead. They are initially initialized to 0 and 1, respectively,
78 so the semantics of the function is obviously preserved. If we are
79 guaranteed that the value of the accumulator never change, we
82 There are three cases how the function may exit. The first one is
83 handled in adjust_return_value, the other two in adjust_accumulator_values
84 (the second case is actually a special case of the third one and we
85 present it separately just for clarity):
87 1) Just return x, where x is not in any of the remaining special shapes.
88 We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
90 2) return f (...), where f is the current function, is rewritten in a
91 classical tail-recursion elimination way, into assignment of arguments
92 and jump to the start of the function. Values of the accumulators
95 3) return a + m * f(...), where a and m do not depend on call to f.
96 To preserve the semantics described before we want this to be rewritten
97 in such a way that we finally return
99 a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
101 I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
102 eliminate the tail call to f. Special cases when the value is just
103 added or just multiplied are obtained by setting a = 0 or m = 1.
105 TODO -- it is possible to do similar tricks for other operations. */
107 /* A structure that describes the tailcall. */
111 /* The iterator pointing to the call statement. */
112 gimple_stmt_iterator call_gsi
;
114 /* True if it is a call to the current function. */
117 /* The return value of the caller is mult * f + add, where f is the return
118 value of the call. */
121 /* Next tailcall in the chain. */
122 struct tailcall
*next
;
125 /* The variables holding the value of multiplicative and additive
127 static tree m_acc
, a_acc
;
129 static bool suitable_for_tail_opt_p (void);
130 static bool optimize_tail_call (struct tailcall
*, bool);
131 static void eliminate_tail_call (struct tailcall
*);
132 static void find_tail_calls (basic_block
, struct tailcall
**);
134 /* Returns false when the function is not suitable for tail call optimization
135 from some reason (e.g. if it takes variable number of arguments). */
138 suitable_for_tail_opt_p (void)
145 /* Returns false when the function is not suitable for tail call optimization
146 from some reason (e.g. if it takes variable number of arguments).
147 This test must pass in addition to suitable_for_tail_opt_p in order to make
148 tail call discovery happen. */
151 suitable_for_tail_call_opt_p (void)
155 /* alloca (until we have stack slot life analysis) inhibits
156 sibling call optimizations, but not tail recursion. */
157 if (cfun
->calls_alloca
)
160 /* If we are using sjlj exceptions, we may need to add a call to
161 _Unwind_SjLj_Unregister at exit of the function. Which means
162 that we cannot do any sibcall transformations. */
163 if (targetm_common
.except_unwind_info (&global_options
) == UI_SJLJ
164 && current_function_has_exception_handlers ())
167 /* Any function that calls setjmp might have longjmp called from
168 any called function. ??? We really should represent this
169 properly in the CFG so that this needn't be special cased. */
170 if (cfun
->calls_setjmp
)
173 /* ??? It is OK if the argument of a function is taken in some cases,
174 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
175 for (param
= DECL_ARGUMENTS (current_function_decl
);
177 param
= DECL_CHAIN (param
))
178 if (TREE_ADDRESSABLE (param
))
184 /* Checks whether the expression EXPR in stmt AT is independent of the
185 statement pointed to by GSI (in a sense that we already know EXPR's value
186 at GSI). We use the fact that we are only called from the chain of
187 basic blocks that have only single successor. Returns the expression
188 containing the value of EXPR at GSI. */
191 independent_of_stmt_p (tree expr
, gimple at
, gimple_stmt_iterator gsi
)
193 basic_block bb
, call_bb
, at_bb
;
197 if (is_gimple_min_invariant (expr
))
200 if (TREE_CODE (expr
) != SSA_NAME
)
203 /* Mark the blocks in the chain leading to the end. */
204 at_bb
= gimple_bb (at
);
205 call_bb
= gimple_bb (gsi_stmt (gsi
));
206 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
212 at
= SSA_NAME_DEF_STMT (expr
);
215 /* The default definition or defined before the chain. */
221 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
222 if (gsi_stmt (gsi
) == at
)
225 if (!gsi_end_p (gsi
))
230 if (gimple_code (at
) != GIMPLE_PHI
)
236 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
241 expr
= PHI_ARG_DEF_FROM_EDGE (at
, e
);
242 if (TREE_CODE (expr
) != SSA_NAME
)
244 /* The value is a constant. */
249 /* Unmark the blocks. */
250 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
257 /* Simulates the effect of an assignment STMT on the return value of the tail
258 recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
259 additive factor for the real return value. */
262 process_assignment (gimple stmt
, gimple_stmt_iterator call
, tree
*m
,
263 tree
*a
, tree
*ass_var
)
265 tree op0
, op1
= NULL_TREE
, non_ass_var
= NULL_TREE
;
266 tree dest
= gimple_assign_lhs (stmt
);
267 enum tree_code code
= gimple_assign_rhs_code (stmt
);
268 enum gimple_rhs_class rhs_class
= get_gimple_rhs_class (code
);
269 tree src_var
= gimple_assign_rhs1 (stmt
);
271 /* See if this is a simple copy operation of an SSA name to the function
272 result. In that case we may have a simple tail call. Ignore type
273 conversions that can never produce extra code between the function
274 call and the function return. */
275 if ((rhs_class
== GIMPLE_SINGLE_RHS
|| gimple_assign_cast_p (stmt
))
276 && (TREE_CODE (src_var
) == SSA_NAME
))
278 /* Reject a tailcall if the type conversion might need
280 if (gimple_assign_cast_p (stmt
)
281 && TYPE_MODE (TREE_TYPE (dest
)) != TYPE_MODE (TREE_TYPE (src_var
)))
284 if (src_var
!= *ass_var
)
293 case GIMPLE_BINARY_RHS
:
294 op1
= gimple_assign_rhs2 (stmt
);
298 case GIMPLE_UNARY_RHS
:
299 op0
= gimple_assign_rhs1 (stmt
);
306 /* Accumulator optimizations will reverse the order of operations.
307 We can only do that for floating-point types if we're assuming
308 that addition and multiplication are associative. */
309 if (!flag_associative_math
)
310 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
313 if (rhs_class
== GIMPLE_UNARY_RHS
)
315 else if (op0
== *ass_var
316 && (non_ass_var
= independent_of_stmt_p (op1
, stmt
, call
)))
318 else if (op1
== *ass_var
319 && (non_ass_var
= independent_of_stmt_p (op0
, stmt
, call
)))
331 case POINTER_PLUS_EXPR
:
344 *m
= build_minus_one_cst (TREE_TYPE (op0
));
350 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
353 *m
= build_minus_one_cst (TREE_TYPE (non_ass_var
));
354 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
360 /* TODO -- Handle POINTER_PLUS_EXPR. */
367 /* Propagate VAR through phis on edge E. */
370 propagate_through_phis (tree var
, edge e
)
372 basic_block dest
= e
->dest
;
373 gimple_stmt_iterator gsi
;
375 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
377 gimple phi
= gsi_stmt (gsi
);
378 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
)
379 return PHI_RESULT (phi
);
384 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
385 added to the start of RET. */
388 find_tail_calls (basic_block bb
, struct tailcall
**ret
)
390 tree ass_var
= NULL_TREE
, ret_var
, func
, param
;
391 gimple stmt
, call
= NULL
;
392 gimple_stmt_iterator gsi
, agsi
;
401 if (!single_succ_p (bb
))
404 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
406 stmt
= gsi_stmt (gsi
);
408 /* Ignore labels, returns, clobbers and debug stmts. */
409 if (gimple_code (stmt
) == GIMPLE_LABEL
410 || gimple_code (stmt
) == GIMPLE_RETURN
411 || gimple_clobber_p (stmt
)
412 || is_gimple_debug (stmt
))
415 /* Check for a call. */
416 if (is_gimple_call (stmt
))
419 ass_var
= gimple_call_lhs (stmt
);
423 /* If the statement references memory or volatile operands, fail. */
424 if (gimple_references_memory_p (stmt
)
425 || gimple_has_volatile_ops (stmt
))
432 /* Recurse to the predecessors. */
433 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
434 find_tail_calls (e
->src
, ret
);
439 /* If the LHS of our call is not just a simple register, we can't
440 transform this into a tail or sibling call. This situation happens,
441 in (e.g.) "*p = foo()" where foo returns a struct. In this case
442 we won't have a temporary here, but we need to carry out the side
443 effect anyway, so tailcall is impossible.
445 ??? In some situations (when the struct is returned in memory via
446 invisible argument) we could deal with this, e.g. by passing 'p'
447 itself as that argument to foo, but it's too early to do this here,
448 and expand_call() will not handle it anyway. If it ever can, then
449 we need to revisit this here, to allow that situation. */
450 if (ass_var
&& !is_gimple_reg (ass_var
))
453 /* We found the call, check whether it is suitable. */
454 tail_recursion
= false;
455 func
= gimple_call_fndecl (call
);
457 && !DECL_BUILT_IN (func
)
458 && recursive_call_p (current_function_decl
, func
))
462 for (param
= DECL_ARGUMENTS (func
), idx
= 0;
463 param
&& idx
< gimple_call_num_args (call
);
464 param
= DECL_CHAIN (param
), idx
++)
466 arg
= gimple_call_arg (call
, idx
);
469 /* Make sure there are no problems with copying. The parameter
470 have a copyable type and the two arguments must have reasonably
471 equivalent types. The latter requirement could be relaxed if
472 we emitted a suitable type conversion statement. */
473 if (!is_gimple_reg_type (TREE_TYPE (param
))
474 || !useless_type_conversion_p (TREE_TYPE (param
),
478 /* The parameter should be a real operand, so that phi node
479 created for it at the start of the function has the meaning
480 of copying the value. This test implies is_gimple_reg_type
481 from the previous condition, however this one could be
482 relaxed by being more careful with copying the new value
483 of the parameter (emitting appropriate GIMPLE_ASSIGN and
484 updating the virtual operands). */
485 if (!is_gimple_reg (param
))
489 if (idx
== gimple_call_num_args (call
) && !param
)
490 tail_recursion
= true;
493 /* Make sure the tail invocation of this function does not refer
494 to local variables. */
495 FOR_EACH_LOCAL_DECL (cfun
, idx
, var
)
497 if (TREE_CODE (var
) != PARM_DECL
498 && auto_var_in_fn_p (var
, cfun
->decl
)
499 && (ref_maybe_used_by_stmt_p (call
, var
)
500 || call_may_clobber_ref_p (call
, var
)))
504 /* Now check the statements after the call. None of them has virtual
505 operands, so they may only depend on the call through its return
506 value. The return value should also be dependent on each of them,
507 since we are running after dce. */
515 tree tmp_a
= NULL_TREE
;
516 tree tmp_m
= NULL_TREE
;
519 while (gsi_end_p (agsi
))
521 ass_var
= propagate_through_phis (ass_var
, single_succ_edge (abb
));
522 abb
= single_succ (abb
);
523 agsi
= gsi_start_bb (abb
);
526 stmt
= gsi_stmt (agsi
);
528 if (gimple_code (stmt
) == GIMPLE_LABEL
)
531 if (gimple_code (stmt
) == GIMPLE_RETURN
)
534 if (gimple_clobber_p (stmt
))
537 if (is_gimple_debug (stmt
))
540 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
543 /* This is a gimple assign. */
544 if (! process_assignment (stmt
, gsi
, &tmp_m
, &tmp_a
, &ass_var
))
549 tree type
= TREE_TYPE (tmp_a
);
551 a
= fold_build2 (PLUS_EXPR
, type
, fold_convert (type
, a
), tmp_a
);
557 tree type
= TREE_TYPE (tmp_m
);
559 m
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, m
), tmp_m
);
564 a
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, a
), tmp_m
);
568 /* See if this is a tail call we can handle. */
569 ret_var
= gimple_return_retval (stmt
);
571 /* We may proceed if there either is no return value, or the return value
572 is identical to the call's return. */
574 && (ret_var
!= ass_var
))
577 /* If this is not a tail recursive call, we cannot handle addends or
579 if (!tail_recursion
&& (m
|| a
))
582 /* For pointers only allow additions. */
583 if (m
&& POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
586 nw
= XNEW (struct tailcall
);
590 nw
->tail_recursion
= tail_recursion
;
599 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
602 add_successor_phi_arg (edge e
, tree var
, tree phi_arg
)
604 gimple_stmt_iterator gsi
;
606 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
607 if (PHI_RESULT (gsi_stmt (gsi
)) == var
)
610 gcc_assert (!gsi_end_p (gsi
));
611 add_phi_arg (gsi_stmt (gsi
), phi_arg
, e
, UNKNOWN_LOCATION
);
614 /* Creates a GIMPLE statement which computes the operation specified by
615 CODE, ACC and OP1 to a new variable with name LABEL and inserts the
616 statement in the position specified by GSI. Returns the
617 tree node of the statement's result. */
620 adjust_return_value_with_ops (enum tree_code code
, const char *label
,
621 tree acc
, tree op1
, gimple_stmt_iterator gsi
)
624 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
625 tree result
= make_temp_ssa_name (ret_type
, NULL
, label
);
628 if (POINTER_TYPE_P (ret_type
))
630 gcc_assert (code
== PLUS_EXPR
&& TREE_TYPE (acc
) == sizetype
);
631 code
= POINTER_PLUS_EXPR
;
633 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
))
634 && code
!= POINTER_PLUS_EXPR
)
635 stmt
= gimple_build_assign_with_ops (code
, result
, acc
, op1
);
639 if (code
== POINTER_PLUS_EXPR
)
640 tem
= fold_build2 (code
, TREE_TYPE (op1
), op1
, acc
);
642 tem
= fold_build2 (code
, TREE_TYPE (op1
),
643 fold_convert (TREE_TYPE (op1
), acc
), op1
);
644 tree rhs
= fold_convert (ret_type
, tem
);
645 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
646 false, NULL
, true, GSI_SAME_STMT
);
647 stmt
= gimple_build_assign (result
, rhs
);
650 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
654 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
655 the computation specified by CODE and OP1 and insert the statement
656 at the position specified by GSI as a new statement. Returns new SSA name
657 of updated accumulator. */
660 update_accumulator_with_ops (enum tree_code code
, tree acc
, tree op1
,
661 gimple_stmt_iterator gsi
)
664 tree var
= copy_ssa_name (acc
, NULL
);
665 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
)))
666 stmt
= gimple_build_assign_with_ops (code
, var
, acc
, op1
);
669 tree rhs
= fold_convert (TREE_TYPE (acc
),
672 fold_convert (TREE_TYPE (op1
), acc
),
674 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
675 false, NULL
, false, GSI_CONTINUE_LINKING
);
676 stmt
= gimple_build_assign (var
, rhs
);
678 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
682 /* Adjust the accumulator values according to A and M after GSI, and update
683 the phi nodes on edge BACK. */
686 adjust_accumulator_values (gimple_stmt_iterator gsi
, tree m
, tree a
, edge back
)
688 tree var
, a_acc_arg
, m_acc_arg
;
691 m
= force_gimple_operand_gsi (&gsi
, m
, true, NULL
, true, GSI_SAME_STMT
);
693 a
= force_gimple_operand_gsi (&gsi
, a
, true, NULL
, true, GSI_SAME_STMT
);
701 if (integer_onep (a
))
704 var
= adjust_return_value_with_ops (MULT_EXPR
, "acc_tmp", m_acc
,
710 a_acc_arg
= update_accumulator_with_ops (PLUS_EXPR
, a_acc
, var
, gsi
);
714 m_acc_arg
= update_accumulator_with_ops (MULT_EXPR
, m_acc
, m
, gsi
);
717 add_successor_phi_arg (back
, a_acc
, a_acc_arg
);
720 add_successor_phi_arg (back
, m_acc
, m_acc_arg
);
723 /* Adjust value of the return at the end of BB according to M and A
727 adjust_return_value (basic_block bb
, tree m
, tree a
)
730 gimple ret_stmt
= gimple_seq_last_stmt (bb_seq (bb
));
731 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
733 gcc_assert (gimple_code (ret_stmt
) == GIMPLE_RETURN
);
735 retval
= gimple_return_retval (ret_stmt
);
736 if (!retval
|| retval
== error_mark_node
)
740 retval
= adjust_return_value_with_ops (MULT_EXPR
, "mul_tmp", m_acc
, retval
,
743 retval
= adjust_return_value_with_ops (PLUS_EXPR
, "acc_tmp", a_acc
, retval
,
745 gimple_return_set_retval (ret_stmt
, retval
);
746 update_stmt (ret_stmt
);
749 /* Subtract COUNT and FREQUENCY from the basic block and it's
752 decrease_profile (basic_block bb
, gcov_type count
, int frequency
)
758 bb
->frequency
-= frequency
;
759 if (bb
->frequency
< 0)
761 if (!single_succ_p (bb
))
763 gcc_assert (!EDGE_COUNT (bb
->succs
));
766 e
= single_succ_edge (bb
);
772 /* Returns true if argument PARAM of the tail recursive call needs to be copied
773 when the call is eliminated. */
776 arg_needs_copy_p (tree param
)
780 if (!is_gimple_reg (param
))
783 /* Parameters that are only defined but never used need not be copied. */
784 def
= ssa_default_def (cfun
, param
);
791 /* Eliminates tail call described by T. TMP_VARS is a list of
792 temporary variables used to copy the function arguments. */
795 eliminate_tail_call (struct tailcall
*t
)
801 basic_block bb
, first
;
804 gimple_stmt_iterator gsi
;
807 stmt
= orig_stmt
= gsi_stmt (t
->call_gsi
);
808 bb
= gsi_bb (t
->call_gsi
);
810 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
812 fprintf (dump_file
, "Eliminated tail recursion in bb %d : ",
814 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
815 fprintf (dump_file
, "\n");
818 gcc_assert (is_gimple_call (stmt
));
820 first
= single_succ (ENTRY_BLOCK_PTR
);
822 /* Remove the code after call_gsi that will become unreachable. The
823 possibly unreachable code in other blocks is removed later in
827 while (!gsi_end_p (gsi
))
829 gimple t
= gsi_stmt (gsi
);
830 /* Do not remove the return statement, so that redirect_edge_and_branch
831 sees how the block ends. */
832 if (gimple_code (t
) == GIMPLE_RETURN
)
835 gsi_remove (&gsi
, true);
839 /* Number of executions of function has reduced by the tailcall. */
840 e
= single_succ_edge (gsi_bb (t
->call_gsi
));
841 decrease_profile (EXIT_BLOCK_PTR
, e
->count
, EDGE_FREQUENCY (e
));
842 decrease_profile (ENTRY_BLOCK_PTR
, e
->count
, EDGE_FREQUENCY (e
));
843 if (e
->dest
!= EXIT_BLOCK_PTR
)
844 decrease_profile (e
->dest
, e
->count
, EDGE_FREQUENCY (e
));
846 /* Replace the call by a jump to the start of function. */
847 e
= redirect_edge_and_branch (single_succ_edge (gsi_bb (t
->call_gsi
)),
850 PENDING_STMT (e
) = NULL
;
852 /* Add phi node entries for arguments. The ordering of the phi nodes should
853 be the same as the ordering of the arguments. */
854 for (param
= DECL_ARGUMENTS (current_function_decl
),
855 idx
= 0, gsi
= gsi_start_phis (first
);
857 param
= DECL_CHAIN (param
), idx
++)
859 if (!arg_needs_copy_p (param
))
862 arg
= gimple_call_arg (stmt
, idx
);
863 phi
= gsi_stmt (gsi
);
864 gcc_assert (param
== SSA_NAME_VAR (PHI_RESULT (phi
)));
866 add_phi_arg (phi
, arg
, e
, gimple_location (stmt
));
870 /* Update the values of accumulators. */
871 adjust_accumulator_values (t
->call_gsi
, t
->mult
, t
->add
, e
);
873 call
= gsi_stmt (t
->call_gsi
);
874 rslt
= gimple_call_lhs (call
);
875 if (rslt
!= NULL_TREE
)
877 /* Result of the call will no longer be defined. So adjust the
878 SSA_NAME_DEF_STMT accordingly. */
879 SSA_NAME_DEF_STMT (rslt
) = gimple_build_nop ();
882 gsi_remove (&t
->call_gsi
, true);
886 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
887 mark the tailcalls for the sibcall optimization. */
890 optimize_tail_call (struct tailcall
*t
, bool opt_tailcalls
)
892 if (t
->tail_recursion
)
894 eliminate_tail_call (t
);
900 gimple stmt
= gsi_stmt (t
->call_gsi
);
902 gimple_call_set_tail (stmt
, true);
903 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
905 fprintf (dump_file
, "Found tail call ");
906 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
907 fprintf (dump_file
, " in bb %i\n", (gsi_bb (t
->call_gsi
))->index
);
914 /* Creates a tail-call accumulator of the same type as the return type of the
915 current function. LABEL is the name used to creating the temporary
916 variable for the accumulator. The accumulator will be inserted in the
917 phis of a basic block BB with single predecessor with an initial value
918 INIT converted to the current function return type. */
921 create_tailcall_accumulator (const char *label
, basic_block bb
, tree init
)
923 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
924 if (POINTER_TYPE_P (ret_type
))
927 tree tmp
= make_temp_ssa_name (ret_type
, NULL
, label
);
930 phi
= create_phi_node (tmp
, bb
);
931 /* RET_TYPE can be a float when -ffast-maths is enabled. */
932 add_phi_arg (phi
, fold_convert (ret_type
, init
), single_pred_edge (bb
),
934 return PHI_RESULT (phi
);
937 /* Optimizes tail calls in the function, turning the tail recursion
941 tree_optimize_tail_calls_1 (bool opt_tailcalls
)
944 bool phis_constructed
= false;
945 struct tailcall
*tailcalls
= NULL
, *act
, *next
;
946 bool changed
= false;
947 basic_block first
= single_succ (ENTRY_BLOCK_PTR
);
952 if (!suitable_for_tail_opt_p ())
955 opt_tailcalls
= suitable_for_tail_call_opt_p ();
957 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
959 /* Only traverse the normal exits, i.e. those that end with return
961 stmt
= last_stmt (e
->src
);
964 && gimple_code (stmt
) == GIMPLE_RETURN
)
965 find_tail_calls (e
->src
, &tailcalls
);
968 /* Construct the phi nodes and accumulators if necessary. */
969 a_acc
= m_acc
= NULL_TREE
;
970 for (act
= tailcalls
; act
; act
= act
->next
)
972 if (!act
->tail_recursion
)
975 if (!phis_constructed
)
977 /* Ensure that there is only one predecessor of the block
978 or if there are existing degenerate PHI nodes. */
979 if (!single_pred_p (first
)
980 || !gimple_seq_empty_p (phi_nodes (first
)))
981 first
= split_edge (single_succ_edge (ENTRY_BLOCK_PTR
));
983 /* Copy the args if needed. */
984 for (param
= DECL_ARGUMENTS (current_function_decl
);
986 param
= DECL_CHAIN (param
))
987 if (arg_needs_copy_p (param
))
989 tree name
= ssa_default_def (cfun
, param
);
990 tree new_name
= make_ssa_name (param
, SSA_NAME_DEF_STMT (name
));
993 set_ssa_default_def (cfun
, param
, new_name
);
994 phi
= create_phi_node (name
, first
);
995 add_phi_arg (phi
, new_name
, single_pred_edge (first
),
996 EXPR_LOCATION (param
));
998 phis_constructed
= true;
1001 if (act
->add
&& !a_acc
)
1002 a_acc
= create_tailcall_accumulator ("add_acc", first
,
1005 if (act
->mult
&& !m_acc
)
1006 m_acc
= create_tailcall_accumulator ("mult_acc", first
,
1012 /* When the tail call elimination using accumulators is performed,
1013 statements adding the accumulated value are inserted at all exits.
1014 This turns all other tail calls to non-tail ones. */
1015 opt_tailcalls
= false;
1018 for (; tailcalls
; tailcalls
= next
)
1020 next
= tailcalls
->next
;
1021 changed
|= optimize_tail_call (tailcalls
, opt_tailcalls
);
1027 /* Modify the remaining return statements. */
1028 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1030 stmt
= last_stmt (e
->src
);
1033 && gimple_code (stmt
) == GIMPLE_RETURN
)
1034 adjust_return_value (e
->src
, m_acc
, a_acc
);
1040 /* We may have created new loops. Make them magically appear. */
1042 loops_state_set (LOOPS_NEED_FIXUP
);
1043 free_dominance_info (CDI_DOMINATORS
);
1046 /* Add phi nodes for the virtual operands defined in the function to the
1047 header of the loop created by tail recursion elimination. Do so
1048 by triggering the SSA renamer. */
1049 if (phis_constructed
)
1050 mark_virtual_operands_for_renaming (cfun
);
1053 return TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
1058 execute_tail_recursion (void)
1060 return tree_optimize_tail_calls_1 (false);
1064 gate_tail_calls (void)
1066 return flag_optimize_sibling_calls
!= 0 && dbg_cnt (tail_call
);
1070 execute_tail_calls (void)
1072 return tree_optimize_tail_calls_1 (true);
1077 const pass_data pass_data_tail_recursion
=
1079 GIMPLE_PASS
, /* type */
1081 OPTGROUP_NONE
, /* optinfo_flags */
1082 true, /* has_gate */
1083 true, /* has_execute */
1084 TV_NONE
, /* tv_id */
1085 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1086 0, /* properties_provided */
1087 0, /* properties_destroyed */
1088 0, /* todo_flags_start */
1089 TODO_verify_ssa
, /* todo_flags_finish */
1092 class pass_tail_recursion
: public gimple_opt_pass
1095 pass_tail_recursion (gcc::context
*ctxt
)
1096 : gimple_opt_pass (pass_data_tail_recursion
, ctxt
)
1099 /* opt_pass methods: */
1100 opt_pass
* clone () { return new pass_tail_recursion (m_ctxt
); }
1101 bool gate () { return gate_tail_calls (); }
1102 unsigned int execute () { return execute_tail_recursion (); }
1104 }; // class pass_tail_recursion
1109 make_pass_tail_recursion (gcc::context
*ctxt
)
1111 return new pass_tail_recursion (ctxt
);
1116 const pass_data pass_data_tail_calls
=
1118 GIMPLE_PASS
, /* type */
1120 OPTGROUP_NONE
, /* optinfo_flags */
1121 true, /* has_gate */
1122 true, /* has_execute */
1123 TV_NONE
, /* tv_id */
1124 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1125 0, /* properties_provided */
1126 0, /* properties_destroyed */
1127 0, /* todo_flags_start */
1128 TODO_verify_ssa
, /* todo_flags_finish */
1131 class pass_tail_calls
: public gimple_opt_pass
1134 pass_tail_calls (gcc::context
*ctxt
)
1135 : gimple_opt_pass (pass_data_tail_calls
, ctxt
)
1138 /* opt_pass methods: */
1139 bool gate () { return gate_tail_calls (); }
1140 unsigned int execute () { return execute_tail_calls (); }
1142 }; // class pass_tail_calls
1147 make_pass_tail_calls (gcc::context
*ctxt
)
1149 return new pass_tail_calls (ctxt
);