1 /* Tail call optimization on trees.
2 Copyright (C) 2003-2014 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"
25 #include "stor-layout.h"
32 #include "hard-reg-set.h"
35 #include "dominance.h"
37 #include "basic-block.h"
38 #include "tree-ssa-alias.h"
39 #include "internal-fn.h"
40 #include "gimple-expr.h"
43 #include "gimple-iterator.h"
44 #include "gimplify-me.h"
45 #include "gimple-ssa.h"
47 #include "tree-phinodes.h"
48 #include "stringpool.h"
49 #include "tree-ssanames.h"
50 #include "tree-into-ssa.h"
53 #include "gimple-pretty-print.h"
55 #include "tree-pass.h"
57 #include "langhooks.h"
61 #include "common/common-target.h"
62 #include "ipa-utils.h"
64 /* The file implements the tail recursion elimination. It is also used to
65 analyze the tail calls in general, passing the results to the rtl level
66 where they are used for sibcall optimization.
68 In addition to the standard tail recursion elimination, we handle the most
69 trivial cases of making the call tail recursive by creating accumulators.
70 For example the following function
75 return n + sum (n - 1);
92 To do this, we maintain two accumulators (a_acc and m_acc) that indicate
93 when we reach the return x statement, we should return a_acc + x * m_acc
94 instead. They are initially initialized to 0 and 1, respectively,
95 so the semantics of the function is obviously preserved. If we are
96 guaranteed that the value of the accumulator never change, we
99 There are three cases how the function may exit. The first one is
100 handled in adjust_return_value, the other two in adjust_accumulator_values
101 (the second case is actually a special case of the third one and we
102 present it separately just for clarity):
104 1) Just return x, where x is not in any of the remaining special shapes.
105 We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
107 2) return f (...), where f is the current function, is rewritten in a
108 classical tail-recursion elimination way, into assignment of arguments
109 and jump to the start of the function. Values of the accumulators
112 3) return a + m * f(...), where a and m do not depend on call to f.
113 To preserve the semantics described before we want this to be rewritten
114 in such a way that we finally return
116 a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
118 I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
119 eliminate the tail call to f. Special cases when the value is just
120 added or just multiplied are obtained by setting a = 0 or m = 1.
122 TODO -- it is possible to do similar tricks for other operations. */
124 /* A structure that describes the tailcall. */
128 /* The iterator pointing to the call statement. */
129 gimple_stmt_iterator call_gsi
;
131 /* True if it is a call to the current function. */
134 /* The return value of the caller is mult * f + add, where f is the return
135 value of the call. */
138 /* Next tailcall in the chain. */
139 struct tailcall
*next
;
142 /* The variables holding the value of multiplicative and additive
144 static tree m_acc
, a_acc
;
146 static bool suitable_for_tail_opt_p (void);
147 static bool optimize_tail_call (struct tailcall
*, bool);
148 static void eliminate_tail_call (struct tailcall
*);
149 static void find_tail_calls (basic_block
, struct tailcall
**);
151 /* Returns false when the function is not suitable for tail call optimization
152 from some reason (e.g. if it takes variable number of arguments). */
155 suitable_for_tail_opt_p (void)
162 /* Returns false when the function is not suitable for tail call optimization
163 from some reason (e.g. if it takes variable number of arguments).
164 This test must pass in addition to suitable_for_tail_opt_p in order to make
165 tail call discovery happen. */
168 suitable_for_tail_call_opt_p (void)
172 /* alloca (until we have stack slot life analysis) inhibits
173 sibling call optimizations, but not tail recursion. */
174 if (cfun
->calls_alloca
)
177 /* If we are using sjlj exceptions, we may need to add a call to
178 _Unwind_SjLj_Unregister at exit of the function. Which means
179 that we cannot do any sibcall transformations. */
180 if (targetm_common
.except_unwind_info (&global_options
) == UI_SJLJ
181 && current_function_has_exception_handlers ())
184 /* Any function that calls setjmp might have longjmp called from
185 any called function. ??? We really should represent this
186 properly in the CFG so that this needn't be special cased. */
187 if (cfun
->calls_setjmp
)
190 /* ??? It is OK if the argument of a function is taken in some cases,
191 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
192 for (param
= DECL_ARGUMENTS (current_function_decl
);
194 param
= DECL_CHAIN (param
))
195 if (TREE_ADDRESSABLE (param
))
201 /* Checks whether the expression EXPR in stmt AT is independent of the
202 statement pointed to by GSI (in a sense that we already know EXPR's value
203 at GSI). We use the fact that we are only called from the chain of
204 basic blocks that have only single successor. Returns the expression
205 containing the value of EXPR at GSI. */
208 independent_of_stmt_p (tree expr
, gimple at
, gimple_stmt_iterator gsi
)
210 basic_block bb
, call_bb
, at_bb
;
214 if (is_gimple_min_invariant (expr
))
217 if (TREE_CODE (expr
) != SSA_NAME
)
220 /* Mark the blocks in the chain leading to the end. */
221 at_bb
= gimple_bb (at
);
222 call_bb
= gimple_bb (gsi_stmt (gsi
));
223 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
229 at
= SSA_NAME_DEF_STMT (expr
);
232 /* The default definition or defined before the chain. */
238 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
239 if (gsi_stmt (gsi
) == at
)
242 if (!gsi_end_p (gsi
))
247 if (gimple_code (at
) != GIMPLE_PHI
)
253 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
258 expr
= PHI_ARG_DEF_FROM_EDGE (at
, e
);
259 if (TREE_CODE (expr
) != SSA_NAME
)
261 /* The value is a constant. */
266 /* Unmark the blocks. */
267 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
274 /* Simulates the effect of an assignment STMT on the return value of the tail
275 recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
276 additive factor for the real return value. */
279 process_assignment (gimple stmt
, gimple_stmt_iterator call
, tree
*m
,
280 tree
*a
, tree
*ass_var
)
282 tree op0
, op1
= NULL_TREE
, non_ass_var
= NULL_TREE
;
283 tree dest
= gimple_assign_lhs (stmt
);
284 enum tree_code code
= gimple_assign_rhs_code (stmt
);
285 enum gimple_rhs_class rhs_class
= get_gimple_rhs_class (code
);
286 tree src_var
= gimple_assign_rhs1 (stmt
);
288 /* See if this is a simple copy operation of an SSA name to the function
289 result. In that case we may have a simple tail call. Ignore type
290 conversions that can never produce extra code between the function
291 call and the function return. */
292 if ((rhs_class
== GIMPLE_SINGLE_RHS
|| gimple_assign_cast_p (stmt
))
293 && (TREE_CODE (src_var
) == SSA_NAME
))
295 /* Reject a tailcall if the type conversion might need
297 if (gimple_assign_cast_p (stmt
))
299 if (TYPE_MODE (TREE_TYPE (dest
)) != TYPE_MODE (TREE_TYPE (src_var
)))
302 /* Even if the type modes are the same, if the precision of the
303 type is smaller than mode's precision,
304 reduce_to_bit_field_precision would generate additional code. */
305 if (INTEGRAL_TYPE_P (TREE_TYPE (dest
))
306 && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (dest
)))
307 > TYPE_PRECISION (TREE_TYPE (dest
))))
311 if (src_var
!= *ass_var
)
320 case GIMPLE_BINARY_RHS
:
321 op1
= gimple_assign_rhs2 (stmt
);
325 case GIMPLE_UNARY_RHS
:
326 op0
= gimple_assign_rhs1 (stmt
);
333 /* Accumulator optimizations will reverse the order of operations.
334 We can only do that for floating-point types if we're assuming
335 that addition and multiplication are associative. */
336 if (!flag_associative_math
)
337 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
340 if (rhs_class
== GIMPLE_UNARY_RHS
)
342 else if (op0
== *ass_var
343 && (non_ass_var
= independent_of_stmt_p (op1
, stmt
, call
)))
345 else if (op1
== *ass_var
346 && (non_ass_var
= independent_of_stmt_p (op0
, stmt
, call
)))
358 case POINTER_PLUS_EXPR
:
371 *m
= build_minus_one_cst (TREE_TYPE (op0
));
377 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
380 *m
= build_minus_one_cst (TREE_TYPE (non_ass_var
));
381 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
387 /* TODO -- Handle POINTER_PLUS_EXPR. */
394 /* Propagate VAR through phis on edge E. */
397 propagate_through_phis (tree var
, edge e
)
399 basic_block dest
= e
->dest
;
400 gimple_stmt_iterator gsi
;
402 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
404 gimple phi
= gsi_stmt (gsi
);
405 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
)
406 return PHI_RESULT (phi
);
411 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
412 added to the start of RET. */
415 find_tail_calls (basic_block bb
, struct tailcall
**ret
)
417 tree ass_var
= NULL_TREE
, ret_var
, func
, param
;
418 gimple stmt
, call
= NULL
;
419 gimple_stmt_iterator gsi
, agsi
;
428 if (!single_succ_p (bb
))
431 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
433 stmt
= gsi_stmt (gsi
);
435 /* Ignore labels, returns, clobbers and debug stmts. */
436 if (gimple_code (stmt
) == GIMPLE_LABEL
437 || gimple_code (stmt
) == GIMPLE_RETURN
438 || gimple_clobber_p (stmt
)
439 || is_gimple_debug (stmt
))
442 /* Check for a call. */
443 if (is_gimple_call (stmt
))
446 ass_var
= gimple_call_lhs (stmt
);
450 /* If the statement references memory or volatile operands, fail. */
451 if (gimple_references_memory_p (stmt
)
452 || gimple_has_volatile_ops (stmt
))
459 /* Recurse to the predecessors. */
460 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
461 find_tail_calls (e
->src
, ret
);
466 /* If the LHS of our call is not just a simple register, we can't
467 transform this into a tail or sibling call. This situation happens,
468 in (e.g.) "*p = foo()" where foo returns a struct. In this case
469 we won't have a temporary here, but we need to carry out the side
470 effect anyway, so tailcall is impossible.
472 ??? In some situations (when the struct is returned in memory via
473 invisible argument) we could deal with this, e.g. by passing 'p'
474 itself as that argument to foo, but it's too early to do this here,
475 and expand_call() will not handle it anyway. If it ever can, then
476 we need to revisit this here, to allow that situation. */
477 if (ass_var
&& !is_gimple_reg (ass_var
))
480 /* We found the call, check whether it is suitable. */
481 tail_recursion
= false;
482 func
= gimple_call_fndecl (call
);
484 && !DECL_BUILT_IN (func
)
485 && recursive_call_p (current_function_decl
, func
))
489 for (param
= DECL_ARGUMENTS (func
), idx
= 0;
490 param
&& idx
< gimple_call_num_args (call
);
491 param
= DECL_CHAIN (param
), idx
++)
493 arg
= gimple_call_arg (call
, idx
);
496 /* Make sure there are no problems with copying. The parameter
497 have a copyable type and the two arguments must have reasonably
498 equivalent types. The latter requirement could be relaxed if
499 we emitted a suitable type conversion statement. */
500 if (!is_gimple_reg_type (TREE_TYPE (param
))
501 || !useless_type_conversion_p (TREE_TYPE (param
),
505 /* The parameter should be a real operand, so that phi node
506 created for it at the start of the function has the meaning
507 of copying the value. This test implies is_gimple_reg_type
508 from the previous condition, however this one could be
509 relaxed by being more careful with copying the new value
510 of the parameter (emitting appropriate GIMPLE_ASSIGN and
511 updating the virtual operands). */
512 if (!is_gimple_reg (param
))
516 if (idx
== gimple_call_num_args (call
) && !param
)
517 tail_recursion
= true;
520 /* Make sure the tail invocation of this function does not refer
521 to local variables. */
522 FOR_EACH_LOCAL_DECL (cfun
, idx
, var
)
524 if (TREE_CODE (var
) != PARM_DECL
525 && auto_var_in_fn_p (var
, cfun
->decl
)
526 && (ref_maybe_used_by_stmt_p (call
, var
)
527 || call_may_clobber_ref_p (call
, var
)))
531 /* Now check the statements after the call. None of them has virtual
532 operands, so they may only depend on the call through its return
533 value. The return value should also be dependent on each of them,
534 since we are running after dce. */
542 tree tmp_a
= NULL_TREE
;
543 tree tmp_m
= NULL_TREE
;
546 while (gsi_end_p (agsi
))
548 ass_var
= propagate_through_phis (ass_var
, single_succ_edge (abb
));
549 abb
= single_succ (abb
);
550 agsi
= gsi_start_bb (abb
);
553 stmt
= gsi_stmt (agsi
);
555 if (gimple_code (stmt
) == GIMPLE_LABEL
)
558 if (gimple_code (stmt
) == GIMPLE_RETURN
)
561 if (gimple_clobber_p (stmt
))
564 if (is_gimple_debug (stmt
))
567 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
570 /* This is a gimple assign. */
571 if (! process_assignment (stmt
, gsi
, &tmp_m
, &tmp_a
, &ass_var
))
576 tree type
= TREE_TYPE (tmp_a
);
578 a
= fold_build2 (PLUS_EXPR
, type
, fold_convert (type
, a
), tmp_a
);
584 tree type
= TREE_TYPE (tmp_m
);
586 m
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, m
), tmp_m
);
591 a
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, a
), tmp_m
);
595 /* See if this is a tail call we can handle. */
596 ret_var
= gimple_return_retval (stmt
);
598 /* We may proceed if there either is no return value, or the return value
599 is identical to the call's return. */
601 && (ret_var
!= ass_var
))
604 /* If this is not a tail recursive call, we cannot handle addends or
606 if (!tail_recursion
&& (m
|| a
))
609 /* For pointers only allow additions. */
610 if (m
&& POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
613 nw
= XNEW (struct tailcall
);
617 nw
->tail_recursion
= tail_recursion
;
626 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
629 add_successor_phi_arg (edge e
, tree var
, tree phi_arg
)
631 gimple_stmt_iterator gsi
;
633 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
634 if (PHI_RESULT (gsi_stmt (gsi
)) == var
)
637 gcc_assert (!gsi_end_p (gsi
));
638 add_phi_arg (gsi_stmt (gsi
), phi_arg
, e
, UNKNOWN_LOCATION
);
641 /* Creates a GIMPLE statement which computes the operation specified by
642 CODE, ACC and OP1 to a new variable with name LABEL and inserts the
643 statement in the position specified by GSI. Returns the
644 tree node of the statement's result. */
647 adjust_return_value_with_ops (enum tree_code code
, const char *label
,
648 tree acc
, tree op1
, gimple_stmt_iterator gsi
)
651 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
652 tree result
= make_temp_ssa_name (ret_type
, NULL
, label
);
655 if (POINTER_TYPE_P (ret_type
))
657 gcc_assert (code
== PLUS_EXPR
&& TREE_TYPE (acc
) == sizetype
);
658 code
= POINTER_PLUS_EXPR
;
660 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
))
661 && code
!= POINTER_PLUS_EXPR
)
662 stmt
= gimple_build_assign_with_ops (code
, result
, acc
, op1
);
666 if (code
== POINTER_PLUS_EXPR
)
667 tem
= fold_build2 (code
, TREE_TYPE (op1
), op1
, acc
);
669 tem
= fold_build2 (code
, TREE_TYPE (op1
),
670 fold_convert (TREE_TYPE (op1
), acc
), op1
);
671 tree rhs
= fold_convert (ret_type
, tem
);
672 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
673 false, NULL
, true, GSI_SAME_STMT
);
674 stmt
= gimple_build_assign (result
, rhs
);
677 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
681 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
682 the computation specified by CODE and OP1 and insert the statement
683 at the position specified by GSI as a new statement. Returns new SSA name
684 of updated accumulator. */
687 update_accumulator_with_ops (enum tree_code code
, tree acc
, tree op1
,
688 gimple_stmt_iterator gsi
)
691 tree var
= copy_ssa_name (acc
, NULL
);
692 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
)))
693 stmt
= gimple_build_assign_with_ops (code
, var
, acc
, op1
);
696 tree rhs
= fold_convert (TREE_TYPE (acc
),
699 fold_convert (TREE_TYPE (op1
), acc
),
701 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
702 false, NULL
, false, GSI_CONTINUE_LINKING
);
703 stmt
= gimple_build_assign (var
, rhs
);
705 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
709 /* Adjust the accumulator values according to A and M after GSI, and update
710 the phi nodes on edge BACK. */
713 adjust_accumulator_values (gimple_stmt_iterator gsi
, tree m
, tree a
, edge back
)
715 tree var
, a_acc_arg
, m_acc_arg
;
718 m
= force_gimple_operand_gsi (&gsi
, m
, true, NULL
, true, GSI_SAME_STMT
);
720 a
= force_gimple_operand_gsi (&gsi
, a
, true, NULL
, true, GSI_SAME_STMT
);
728 if (integer_onep (a
))
731 var
= adjust_return_value_with_ops (MULT_EXPR
, "acc_tmp", m_acc
,
737 a_acc_arg
= update_accumulator_with_ops (PLUS_EXPR
, a_acc
, var
, gsi
);
741 m_acc_arg
= update_accumulator_with_ops (MULT_EXPR
, m_acc
, m
, gsi
);
744 add_successor_phi_arg (back
, a_acc
, a_acc_arg
);
747 add_successor_phi_arg (back
, m_acc
, m_acc_arg
);
750 /* Adjust value of the return at the end of BB according to M and A
754 adjust_return_value (basic_block bb
, tree m
, tree a
)
757 gimple ret_stmt
= gimple_seq_last_stmt (bb_seq (bb
));
758 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
760 gcc_assert (gimple_code (ret_stmt
) == GIMPLE_RETURN
);
762 retval
= gimple_return_retval (ret_stmt
);
763 if (!retval
|| retval
== error_mark_node
)
767 retval
= adjust_return_value_with_ops (MULT_EXPR
, "mul_tmp", m_acc
, retval
,
770 retval
= adjust_return_value_with_ops (PLUS_EXPR
, "acc_tmp", a_acc
, retval
,
772 gimple_return_set_retval (ret_stmt
, retval
);
773 update_stmt (ret_stmt
);
776 /* Subtract COUNT and FREQUENCY from the basic block and it's
779 decrease_profile (basic_block bb
, gcov_type count
, int frequency
)
785 bb
->frequency
-= frequency
;
786 if (bb
->frequency
< 0)
788 if (!single_succ_p (bb
))
790 gcc_assert (!EDGE_COUNT (bb
->succs
));
793 e
= single_succ_edge (bb
);
799 /* Returns true if argument PARAM of the tail recursive call needs to be copied
800 when the call is eliminated. */
803 arg_needs_copy_p (tree param
)
807 if (!is_gimple_reg (param
))
810 /* Parameters that are only defined but never used need not be copied. */
811 def
= ssa_default_def (cfun
, param
);
818 /* Eliminates tail call described by T. TMP_VARS is a list of
819 temporary variables used to copy the function arguments. */
822 eliminate_tail_call (struct tailcall
*t
)
828 basic_block bb
, first
;
831 gimple_stmt_iterator gsi
;
834 stmt
= orig_stmt
= gsi_stmt (t
->call_gsi
);
835 bb
= gsi_bb (t
->call_gsi
);
837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
839 fprintf (dump_file
, "Eliminated tail recursion in bb %d : ",
841 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
842 fprintf (dump_file
, "\n");
845 gcc_assert (is_gimple_call (stmt
));
847 first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
849 /* Remove the code after call_gsi that will become unreachable. The
850 possibly unreachable code in other blocks is removed later in
854 while (!gsi_end_p (gsi
))
856 gimple t
= gsi_stmt (gsi
);
857 /* Do not remove the return statement, so that redirect_edge_and_branch
858 sees how the block ends. */
859 if (gimple_code (t
) == GIMPLE_RETURN
)
862 gsi_remove (&gsi
, true);
866 /* Number of executions of function has reduced by the tailcall. */
867 e
= single_succ_edge (gsi_bb (t
->call_gsi
));
868 decrease_profile (EXIT_BLOCK_PTR_FOR_FN (cfun
), e
->count
, EDGE_FREQUENCY (e
));
869 decrease_profile (ENTRY_BLOCK_PTR_FOR_FN (cfun
), e
->count
,
871 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
872 decrease_profile (e
->dest
, e
->count
, EDGE_FREQUENCY (e
));
874 /* Replace the call by a jump to the start of function. */
875 e
= redirect_edge_and_branch (single_succ_edge (gsi_bb (t
->call_gsi
)),
878 PENDING_STMT (e
) = NULL
;
880 /* Add phi node entries for arguments. The ordering of the phi nodes should
881 be the same as the ordering of the arguments. */
882 for (param
= DECL_ARGUMENTS (current_function_decl
),
883 idx
= 0, gsi
= gsi_start_phis (first
);
885 param
= DECL_CHAIN (param
), idx
++)
887 if (!arg_needs_copy_p (param
))
890 arg
= gimple_call_arg (stmt
, idx
);
891 phi
= gsi_stmt (gsi
);
892 gcc_assert (param
== SSA_NAME_VAR (PHI_RESULT (phi
)));
894 add_phi_arg (phi
, arg
, e
, gimple_location (stmt
));
898 /* Update the values of accumulators. */
899 adjust_accumulator_values (t
->call_gsi
, t
->mult
, t
->add
, e
);
901 call
= gsi_stmt (t
->call_gsi
);
902 rslt
= gimple_call_lhs (call
);
903 if (rslt
!= NULL_TREE
)
905 /* Result of the call will no longer be defined. So adjust the
906 SSA_NAME_DEF_STMT accordingly. */
907 SSA_NAME_DEF_STMT (rslt
) = gimple_build_nop ();
910 gsi_remove (&t
->call_gsi
, true);
914 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
915 mark the tailcalls for the sibcall optimization. */
918 optimize_tail_call (struct tailcall
*t
, bool opt_tailcalls
)
920 if (t
->tail_recursion
)
922 eliminate_tail_call (t
);
928 gimple stmt
= gsi_stmt (t
->call_gsi
);
930 gimple_call_set_tail (stmt
, true);
931 cfun
->tail_call_marked
= true;
932 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
934 fprintf (dump_file
, "Found tail call ");
935 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
936 fprintf (dump_file
, " in bb %i\n", (gsi_bb (t
->call_gsi
))->index
);
943 /* Creates a tail-call accumulator of the same type as the return type of the
944 current function. LABEL is the name used to creating the temporary
945 variable for the accumulator. The accumulator will be inserted in the
946 phis of a basic block BB with single predecessor with an initial value
947 INIT converted to the current function return type. */
950 create_tailcall_accumulator (const char *label
, basic_block bb
, tree init
)
952 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
953 if (POINTER_TYPE_P (ret_type
))
956 tree tmp
= make_temp_ssa_name (ret_type
, NULL
, label
);
959 phi
= create_phi_node (tmp
, bb
);
960 /* RET_TYPE can be a float when -ffast-maths is enabled. */
961 add_phi_arg (phi
, fold_convert (ret_type
, init
), single_pred_edge (bb
),
963 return PHI_RESULT (phi
);
966 /* Optimizes tail calls in the function, turning the tail recursion
970 tree_optimize_tail_calls_1 (bool opt_tailcalls
)
973 bool phis_constructed
= false;
974 struct tailcall
*tailcalls
= NULL
, *act
, *next
;
975 bool changed
= false;
976 basic_block first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
981 if (!suitable_for_tail_opt_p ())
984 opt_tailcalls
= suitable_for_tail_call_opt_p ();
986 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
988 /* Only traverse the normal exits, i.e. those that end with return
990 stmt
= last_stmt (e
->src
);
993 && gimple_code (stmt
) == GIMPLE_RETURN
)
994 find_tail_calls (e
->src
, &tailcalls
);
997 /* Construct the phi nodes and accumulators if necessary. */
998 a_acc
= m_acc
= NULL_TREE
;
999 for (act
= tailcalls
; act
; act
= act
->next
)
1001 if (!act
->tail_recursion
)
1004 if (!phis_constructed
)
1006 /* Ensure that there is only one predecessor of the block
1007 or if there are existing degenerate PHI nodes. */
1008 if (!single_pred_p (first
)
1009 || !gimple_seq_empty_p (phi_nodes (first
)))
1011 split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1013 /* Copy the args if needed. */
1014 for (param
= DECL_ARGUMENTS (current_function_decl
);
1016 param
= DECL_CHAIN (param
))
1017 if (arg_needs_copy_p (param
))
1019 tree name
= ssa_default_def (cfun
, param
);
1020 tree new_name
= make_ssa_name (param
, SSA_NAME_DEF_STMT (name
));
1023 set_ssa_default_def (cfun
, param
, new_name
);
1024 phi
= create_phi_node (name
, first
);
1025 add_phi_arg (phi
, new_name
, single_pred_edge (first
),
1026 EXPR_LOCATION (param
));
1028 phis_constructed
= true;
1031 if (act
->add
&& !a_acc
)
1032 a_acc
= create_tailcall_accumulator ("add_acc", first
,
1035 if (act
->mult
&& !m_acc
)
1036 m_acc
= create_tailcall_accumulator ("mult_acc", first
,
1042 /* When the tail call elimination using accumulators is performed,
1043 statements adding the accumulated value are inserted at all exits.
1044 This turns all other tail calls to non-tail ones. */
1045 opt_tailcalls
= false;
1048 for (; tailcalls
; tailcalls
= next
)
1050 next
= tailcalls
->next
;
1051 changed
|= optimize_tail_call (tailcalls
, opt_tailcalls
);
1057 /* Modify the remaining return statements. */
1058 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1060 stmt
= last_stmt (e
->src
);
1063 && gimple_code (stmt
) == GIMPLE_RETURN
)
1064 adjust_return_value (e
->src
, m_acc
, a_acc
);
1070 /* We may have created new loops. Make them magically appear. */
1071 loops_state_set (LOOPS_NEED_FIXUP
);
1072 free_dominance_info (CDI_DOMINATORS
);
1075 /* Add phi nodes for the virtual operands defined in the function to the
1076 header of the loop created by tail recursion elimination. Do so
1077 by triggering the SSA renamer. */
1078 if (phis_constructed
)
1079 mark_virtual_operands_for_renaming (cfun
);
1082 return TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
1087 gate_tail_calls (void)
1089 return flag_optimize_sibling_calls
!= 0 && dbg_cnt (tail_call
);
1093 execute_tail_calls (void)
1095 return tree_optimize_tail_calls_1 (true);
1100 const pass_data pass_data_tail_recursion
=
1102 GIMPLE_PASS
, /* type */
1104 OPTGROUP_NONE
, /* optinfo_flags */
1105 TV_NONE
, /* tv_id */
1106 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1107 0, /* properties_provided */
1108 0, /* properties_destroyed */
1109 0, /* todo_flags_start */
1110 0, /* todo_flags_finish */
1113 class pass_tail_recursion
: public gimple_opt_pass
1116 pass_tail_recursion (gcc::context
*ctxt
)
1117 : gimple_opt_pass (pass_data_tail_recursion
, ctxt
)
1120 /* opt_pass methods: */
1121 opt_pass
* clone () { return new pass_tail_recursion (m_ctxt
); }
1122 virtual bool gate (function
*) { return gate_tail_calls (); }
1123 virtual unsigned int execute (function
*)
1125 return tree_optimize_tail_calls_1 (false);
1128 }; // class pass_tail_recursion
1133 make_pass_tail_recursion (gcc::context
*ctxt
)
1135 return new pass_tail_recursion (ctxt
);
1140 const pass_data pass_data_tail_calls
=
1142 GIMPLE_PASS
, /* type */
1144 OPTGROUP_NONE
, /* optinfo_flags */
1145 TV_NONE
, /* tv_id */
1146 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1147 0, /* properties_provided */
1148 0, /* properties_destroyed */
1149 0, /* todo_flags_start */
1150 0, /* todo_flags_finish */
1153 class pass_tail_calls
: public gimple_opt_pass
1156 pass_tail_calls (gcc::context
*ctxt
)
1157 : gimple_opt_pass (pass_data_tail_calls
, ctxt
)
1160 /* opt_pass methods: */
1161 virtual bool gate (function
*) { return gate_tail_calls (); }
1162 virtual unsigned int execute (function
*) { return execute_tail_calls (); }
1164 }; // class pass_tail_calls
1169 make_pass_tail_calls (gcc::context
*ctxt
)
1171 return new pass_tail_calls (ctxt
);