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"
27 #include "basic-block.h"
29 #include "tree-ssa-alias.h"
30 #include "internal-fn.h"
31 #include "gimple-expr.h"
34 #include "gimple-iterator.h"
35 #include "gimplify-me.h"
36 #include "gimple-ssa.h"
38 #include "tree-phinodes.h"
39 #include "stringpool.h"
40 #include "tree-ssanames.h"
41 #include "tree-into-ssa.h"
44 #include "gimple-pretty-print.h"
46 #include "tree-pass.h"
48 #include "langhooks.h"
52 #include "common/common-target.h"
53 #include "ipa-utils.h"
55 /* The file implements the tail recursion elimination. It is also used to
56 analyze the tail calls in general, passing the results to the rtl level
57 where they are used for sibcall optimization.
59 In addition to the standard tail recursion elimination, we handle the most
60 trivial cases of making the call tail recursive by creating accumulators.
61 For example the following function
66 return n + sum (n - 1);
83 To do this, we maintain two accumulators (a_acc and m_acc) that indicate
84 when we reach the return x statement, we should return a_acc + x * m_acc
85 instead. They are initially initialized to 0 and 1, respectively,
86 so the semantics of the function is obviously preserved. If we are
87 guaranteed that the value of the accumulator never change, we
90 There are three cases how the function may exit. The first one is
91 handled in adjust_return_value, the other two in adjust_accumulator_values
92 (the second case is actually a special case of the third one and we
93 present it separately just for clarity):
95 1) Just return x, where x is not in any of the remaining special shapes.
96 We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
98 2) return f (...), where f is the current function, is rewritten in a
99 classical tail-recursion elimination way, into assignment of arguments
100 and jump to the start of the function. Values of the accumulators
103 3) return a + m * f(...), where a and m do not depend on call to f.
104 To preserve the semantics described before we want this to be rewritten
105 in such a way that we finally return
107 a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
109 I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
110 eliminate the tail call to f. Special cases when the value is just
111 added or just multiplied are obtained by setting a = 0 or m = 1.
113 TODO -- it is possible to do similar tricks for other operations. */
115 /* A structure that describes the tailcall. */
119 /* The iterator pointing to the call statement. */
120 gimple_stmt_iterator call_gsi
;
122 /* True if it is a call to the current function. */
125 /* The return value of the caller is mult * f + add, where f is the return
126 value of the call. */
129 /* Next tailcall in the chain. */
130 struct tailcall
*next
;
133 /* The variables holding the value of multiplicative and additive
135 static tree m_acc
, a_acc
;
137 static bool suitable_for_tail_opt_p (void);
138 static bool optimize_tail_call (struct tailcall
*, bool);
139 static void eliminate_tail_call (struct tailcall
*);
140 static void find_tail_calls (basic_block
, struct tailcall
**);
142 /* Returns false when the function is not suitable for tail call optimization
143 from some reason (e.g. if it takes variable number of arguments). */
146 suitable_for_tail_opt_p (void)
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 (targetm_common
.except_unwind_info (&global_options
) == UI_SJLJ
172 && current_function_has_exception_handlers ())
175 /* Any function that calls setjmp might have longjmp called from
176 any called function. ??? We really should represent this
177 properly in the CFG so that this needn't be special cased. */
178 if (cfun
->calls_setjmp
)
181 /* ??? It is OK if the argument of a function is taken in some cases,
182 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
183 for (param
= DECL_ARGUMENTS (current_function_decl
);
185 param
= DECL_CHAIN (param
))
186 if (TREE_ADDRESSABLE (param
))
192 /* Checks whether the expression EXPR in stmt AT is independent of the
193 statement pointed to by GSI (in a sense that we already know EXPR's value
194 at GSI). We use the fact that we are only called from the chain of
195 basic blocks that have only single successor. Returns the expression
196 containing the value of EXPR at GSI. */
199 independent_of_stmt_p (tree expr
, gimple at
, gimple_stmt_iterator gsi
)
201 basic_block bb
, call_bb
, at_bb
;
205 if (is_gimple_min_invariant (expr
))
208 if (TREE_CODE (expr
) != SSA_NAME
)
211 /* Mark the blocks in the chain leading to the end. */
212 at_bb
= gimple_bb (at
);
213 call_bb
= gimple_bb (gsi_stmt (gsi
));
214 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
220 at
= SSA_NAME_DEF_STMT (expr
);
223 /* The default definition or defined before the chain. */
229 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
230 if (gsi_stmt (gsi
) == at
)
233 if (!gsi_end_p (gsi
))
238 if (gimple_code (at
) != GIMPLE_PHI
)
244 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
249 expr
= PHI_ARG_DEF_FROM_EDGE (at
, e
);
250 if (TREE_CODE (expr
) != SSA_NAME
)
252 /* The value is a constant. */
257 /* Unmark the blocks. */
258 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
265 /* Simulates the effect of an assignment STMT on the return value of the tail
266 recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
267 additive factor for the real return value. */
270 process_assignment (gimple_assign stmt
, gimple_stmt_iterator call
, tree
*m
,
271 tree
*a
, tree
*ass_var
)
273 tree op0
, op1
= NULL_TREE
, non_ass_var
= NULL_TREE
;
274 tree dest
= gimple_assign_lhs (stmt
);
275 enum tree_code code
= gimple_assign_rhs_code (stmt
);
276 enum gimple_rhs_class rhs_class
= get_gimple_rhs_class (code
);
277 tree src_var
= gimple_assign_rhs1 (stmt
);
279 /* See if this is a simple copy operation of an SSA name to the function
280 result. In that case we may have a simple tail call. Ignore type
281 conversions that can never produce extra code between the function
282 call and the function return. */
283 if ((rhs_class
== GIMPLE_SINGLE_RHS
|| gimple_assign_cast_p (stmt
))
284 && (TREE_CODE (src_var
) == SSA_NAME
))
286 /* Reject a tailcall if the type conversion might need
288 if (gimple_assign_cast_p (stmt
))
290 if (TYPE_MODE (TREE_TYPE (dest
)) != TYPE_MODE (TREE_TYPE (src_var
)))
293 /* Even if the type modes are the same, if the precision of the
294 type is smaller than mode's precision,
295 reduce_to_bit_field_precision would generate additional code. */
296 if (INTEGRAL_TYPE_P (TREE_TYPE (dest
))
297 && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (dest
)))
298 > TYPE_PRECISION (TREE_TYPE (dest
))))
302 if (src_var
!= *ass_var
)
311 case GIMPLE_BINARY_RHS
:
312 op1
= gimple_assign_rhs2 (stmt
);
316 case GIMPLE_UNARY_RHS
:
317 op0
= gimple_assign_rhs1 (stmt
);
324 /* Accumulator optimizations will reverse the order of operations.
325 We can only do that for floating-point types if we're assuming
326 that addition and multiplication are associative. */
327 if (!flag_associative_math
)
328 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
331 if (rhs_class
== GIMPLE_UNARY_RHS
)
333 else if (op0
== *ass_var
334 && (non_ass_var
= independent_of_stmt_p (op1
, stmt
, call
)))
336 else if (op1
== *ass_var
337 && (non_ass_var
= independent_of_stmt_p (op0
, stmt
, call
)))
349 case POINTER_PLUS_EXPR
:
362 *m
= build_minus_one_cst (TREE_TYPE (op0
));
368 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
371 *m
= build_minus_one_cst (TREE_TYPE (non_ass_var
));
372 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
378 /* TODO -- Handle POINTER_PLUS_EXPR. */
385 /* Propagate VAR through phis on edge E. */
388 propagate_through_phis (tree var
, edge e
)
390 basic_block dest
= e
->dest
;
391 gimple_phi_iterator gsi
;
393 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
395 gimple_phi phi
= gsi
.phi ();
396 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
)
397 return PHI_RESULT (phi
);
402 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
403 added to the start of RET. */
406 find_tail_calls (basic_block bb
, struct tailcall
**ret
)
408 tree ass_var
= NULL_TREE
, ret_var
, func
, param
;
410 gimple_call call
= NULL
;
411 gimple_stmt_iterator gsi
, agsi
;
420 if (!single_succ_p (bb
))
423 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
425 stmt
= gsi_stmt (gsi
);
427 /* Ignore labels, returns, clobbers and debug stmts. */
428 if (gimple_code (stmt
) == GIMPLE_LABEL
429 || gimple_code (stmt
) == GIMPLE_RETURN
430 || gimple_clobber_p (stmt
)
431 || is_gimple_debug (stmt
))
434 /* Check for a call. */
435 if (is_gimple_call (stmt
))
437 call
= as_a
<gimple_call
> (stmt
);
438 ass_var
= gimple_call_lhs (call
);
442 /* If the statement references memory or volatile operands, fail. */
443 if (gimple_references_memory_p (stmt
)
444 || gimple_has_volatile_ops (stmt
))
451 /* Recurse to the predecessors. */
452 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
453 find_tail_calls (e
->src
, ret
);
458 /* If the LHS of our call is not just a simple register, we can't
459 transform this into a tail or sibling call. This situation happens,
460 in (e.g.) "*p = foo()" where foo returns a struct. In this case
461 we won't have a temporary here, but we need to carry out the side
462 effect anyway, so tailcall is impossible.
464 ??? In some situations (when the struct is returned in memory via
465 invisible argument) we could deal with this, e.g. by passing 'p'
466 itself as that argument to foo, but it's too early to do this here,
467 and expand_call() will not handle it anyway. If it ever can, then
468 we need to revisit this here, to allow that situation. */
469 if (ass_var
&& !is_gimple_reg (ass_var
))
472 /* We found the call, check whether it is suitable. */
473 tail_recursion
= false;
474 func
= gimple_call_fndecl (call
);
476 && !DECL_BUILT_IN (func
)
477 && recursive_call_p (current_function_decl
, func
))
481 for (param
= DECL_ARGUMENTS (func
), idx
= 0;
482 param
&& idx
< gimple_call_num_args (call
);
483 param
= DECL_CHAIN (param
), idx
++)
485 arg
= gimple_call_arg (call
, idx
);
488 /* Make sure there are no problems with copying. The parameter
489 have a copyable type and the two arguments must have reasonably
490 equivalent types. The latter requirement could be relaxed if
491 we emitted a suitable type conversion statement. */
492 if (!is_gimple_reg_type (TREE_TYPE (param
))
493 || !useless_type_conversion_p (TREE_TYPE (param
),
497 /* The parameter should be a real operand, so that phi node
498 created for it at the start of the function has the meaning
499 of copying the value. This test implies is_gimple_reg_type
500 from the previous condition, however this one could be
501 relaxed by being more careful with copying the new value
502 of the parameter (emitting appropriate GIMPLE_ASSIGN and
503 updating the virtual operands). */
504 if (!is_gimple_reg (param
))
508 if (idx
== gimple_call_num_args (call
) && !param
)
509 tail_recursion
= true;
512 /* Make sure the tail invocation of this function does not refer
513 to local variables. */
514 FOR_EACH_LOCAL_DECL (cfun
, idx
, var
)
516 if (TREE_CODE (var
) != PARM_DECL
517 && auto_var_in_fn_p (var
, cfun
->decl
)
518 && (ref_maybe_used_by_stmt_p (call
, var
)
519 || call_may_clobber_ref_p (call
, var
)))
523 /* Now check the statements after the call. None of them has virtual
524 operands, so they may only depend on the call through its return
525 value. The return value should also be dependent on each of them,
526 since we are running after dce. */
534 tree tmp_a
= NULL_TREE
;
535 tree tmp_m
= NULL_TREE
;
538 while (gsi_end_p (agsi
))
540 ass_var
= propagate_through_phis (ass_var
, single_succ_edge (abb
));
541 abb
= single_succ (abb
);
542 agsi
= gsi_start_bb (abb
);
545 stmt
= gsi_stmt (agsi
);
547 if (gimple_code (stmt
) == GIMPLE_LABEL
)
550 if (gimple_code (stmt
) == GIMPLE_RETURN
)
553 if (gimple_clobber_p (stmt
))
556 if (is_gimple_debug (stmt
))
559 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
562 /* This is a gimple assign. */
563 if (! process_assignment (as_a
<gimple_assign
> (stmt
), gsi
, &tmp_m
,
569 tree type
= TREE_TYPE (tmp_a
);
571 a
= fold_build2 (PLUS_EXPR
, type
, fold_convert (type
, a
), tmp_a
);
577 tree type
= TREE_TYPE (tmp_m
);
579 m
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, m
), tmp_m
);
584 a
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, a
), tmp_m
);
588 /* See if this is a tail call we can handle. */
589 ret_var
= gimple_return_retval (as_a
<gimple_return
> (stmt
));
591 /* We may proceed if there either is no return value, or the return value
592 is identical to the call's return. */
594 && (ret_var
!= ass_var
))
597 /* If this is not a tail recursive call, we cannot handle addends or
599 if (!tail_recursion
&& (m
|| a
))
602 /* For pointers only allow additions. */
603 if (m
&& POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
606 nw
= XNEW (struct tailcall
);
610 nw
->tail_recursion
= tail_recursion
;
619 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
622 add_successor_phi_arg (edge e
, tree var
, tree phi_arg
)
624 gimple_phi_iterator gsi
;
626 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
627 if (PHI_RESULT (gsi
.phi ()) == var
)
630 gcc_assert (!gsi_end_p (gsi
));
631 add_phi_arg (gsi
.phi (), phi_arg
, e
, UNKNOWN_LOCATION
);
634 /* Creates a GIMPLE statement which computes the operation specified by
635 CODE, ACC and OP1 to a new variable with name LABEL and inserts the
636 statement in the position specified by GSI. Returns the
637 tree node of the statement's result. */
640 adjust_return_value_with_ops (enum tree_code code
, const char *label
,
641 tree acc
, tree op1
, gimple_stmt_iterator gsi
)
644 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
645 tree result
= make_temp_ssa_name (ret_type
, NULL
, label
);
648 if (POINTER_TYPE_P (ret_type
))
650 gcc_assert (code
== PLUS_EXPR
&& TREE_TYPE (acc
) == sizetype
);
651 code
= POINTER_PLUS_EXPR
;
653 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
))
654 && code
!= POINTER_PLUS_EXPR
)
655 stmt
= gimple_build_assign_with_ops (code
, result
, acc
, op1
);
659 if (code
== POINTER_PLUS_EXPR
)
660 tem
= fold_build2 (code
, TREE_TYPE (op1
), op1
, acc
);
662 tem
= fold_build2 (code
, TREE_TYPE (op1
),
663 fold_convert (TREE_TYPE (op1
), acc
), op1
);
664 tree rhs
= fold_convert (ret_type
, tem
);
665 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
666 false, NULL
, true, GSI_SAME_STMT
);
667 stmt
= gimple_build_assign (result
, rhs
);
670 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
674 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
675 the computation specified by CODE and OP1 and insert the statement
676 at the position specified by GSI as a new statement. Returns new SSA name
677 of updated accumulator. */
680 update_accumulator_with_ops (enum tree_code code
, tree acc
, tree op1
,
681 gimple_stmt_iterator gsi
)
684 tree var
= copy_ssa_name (acc
, NULL
);
685 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
)))
686 stmt
= gimple_build_assign_with_ops (code
, var
, acc
, op1
);
689 tree rhs
= fold_convert (TREE_TYPE (acc
),
692 fold_convert (TREE_TYPE (op1
), acc
),
694 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
695 false, NULL
, false, GSI_CONTINUE_LINKING
);
696 stmt
= gimple_build_assign (var
, rhs
);
698 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
702 /* Adjust the accumulator values according to A and M after GSI, and update
703 the phi nodes on edge BACK. */
706 adjust_accumulator_values (gimple_stmt_iterator gsi
, tree m
, tree a
, edge back
)
708 tree var
, a_acc_arg
, m_acc_arg
;
711 m
= force_gimple_operand_gsi (&gsi
, m
, true, NULL
, true, GSI_SAME_STMT
);
713 a
= force_gimple_operand_gsi (&gsi
, a
, true, NULL
, true, GSI_SAME_STMT
);
721 if (integer_onep (a
))
724 var
= adjust_return_value_with_ops (MULT_EXPR
, "acc_tmp", m_acc
,
730 a_acc_arg
= update_accumulator_with_ops (PLUS_EXPR
, a_acc
, var
, gsi
);
734 m_acc_arg
= update_accumulator_with_ops (MULT_EXPR
, m_acc
, m
, gsi
);
737 add_successor_phi_arg (back
, a_acc
, a_acc_arg
);
740 add_successor_phi_arg (back
, m_acc
, m_acc_arg
);
743 /* Adjust value of the return at the end of BB according to M and A
747 adjust_return_value (basic_block bb
, tree m
, tree a
)
750 gimple_return ret_stmt
=
751 as_a
<gimple_return
> (gimple_seq_last_stmt (bb_seq (bb
)));
752 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
754 gcc_assert (gimple_code (ret_stmt
) == GIMPLE_RETURN
);
756 retval
= gimple_return_retval (ret_stmt
);
757 if (!retval
|| retval
== error_mark_node
)
761 retval
= adjust_return_value_with_ops (MULT_EXPR
, "mul_tmp", m_acc
, retval
,
764 retval
= adjust_return_value_with_ops (PLUS_EXPR
, "acc_tmp", a_acc
, retval
,
766 gimple_return_set_retval (ret_stmt
, retval
);
767 update_stmt (ret_stmt
);
770 /* Subtract COUNT and FREQUENCY from the basic block and it's
773 decrease_profile (basic_block bb
, gcov_type count
, int frequency
)
779 bb
->frequency
-= frequency
;
780 if (bb
->frequency
< 0)
782 if (!single_succ_p (bb
))
784 gcc_assert (!EDGE_COUNT (bb
->succs
));
787 e
= single_succ_edge (bb
);
793 /* Returns true if argument PARAM of the tail recursive call needs to be copied
794 when the call is eliminated. */
797 arg_needs_copy_p (tree param
)
801 if (!is_gimple_reg (param
))
804 /* Parameters that are only defined but never used need not be copied. */
805 def
= ssa_default_def (cfun
, param
);
812 /* Eliminates tail call described by T. TMP_VARS is a list of
813 temporary variables used to copy the function arguments. */
816 eliminate_tail_call (struct tailcall
*t
)
822 basic_block bb
, first
;
825 gimple_phi_iterator gpi
;
826 gimple_stmt_iterator gsi
;
829 stmt
= orig_stmt
= gsi_stmt (t
->call_gsi
);
830 bb
= gsi_bb (t
->call_gsi
);
832 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
834 fprintf (dump_file
, "Eliminated tail recursion in bb %d : ",
836 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
837 fprintf (dump_file
, "\n");
840 gcc_assert (is_gimple_call (stmt
));
842 first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
844 /* Remove the code after call_gsi that will become unreachable. The
845 possibly unreachable code in other blocks is removed later in
849 while (!gsi_end_p (gsi
))
851 gimple t
= gsi_stmt (gsi
);
852 /* Do not remove the return statement, so that redirect_edge_and_branch
853 sees how the block ends. */
854 if (gimple_code (t
) == GIMPLE_RETURN
)
857 gsi_remove (&gsi
, true);
861 /* Number of executions of function has reduced by the tailcall. */
862 e
= single_succ_edge (gsi_bb (t
->call_gsi
));
863 decrease_profile (EXIT_BLOCK_PTR_FOR_FN (cfun
), e
->count
, EDGE_FREQUENCY (e
));
864 decrease_profile (ENTRY_BLOCK_PTR_FOR_FN (cfun
), e
->count
,
866 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
867 decrease_profile (e
->dest
, e
->count
, EDGE_FREQUENCY (e
));
869 /* Replace the call by a jump to the start of function. */
870 e
= redirect_edge_and_branch (single_succ_edge (gsi_bb (t
->call_gsi
)),
873 PENDING_STMT (e
) = NULL
;
875 /* Add phi node entries for arguments. The ordering of the phi nodes should
876 be the same as the ordering of the arguments. */
877 for (param
= DECL_ARGUMENTS (current_function_decl
),
878 idx
= 0, gpi
= gsi_start_phis (first
);
880 param
= DECL_CHAIN (param
), idx
++)
882 if (!arg_needs_copy_p (param
))
885 arg
= gimple_call_arg (stmt
, idx
);
887 gcc_assert (param
== SSA_NAME_VAR (PHI_RESULT (phi
)));
889 add_phi_arg (phi
, arg
, e
, gimple_location (stmt
));
893 /* Update the values of accumulators. */
894 adjust_accumulator_values (t
->call_gsi
, t
->mult
, t
->add
, e
);
896 call
= gsi_stmt (t
->call_gsi
);
897 rslt
= gimple_call_lhs (call
);
898 if (rslt
!= NULL_TREE
)
900 /* Result of the call will no longer be defined. So adjust the
901 SSA_NAME_DEF_STMT accordingly. */
902 SSA_NAME_DEF_STMT (rslt
) = gimple_build_nop ();
905 gsi_remove (&t
->call_gsi
, true);
909 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
910 mark the tailcalls for the sibcall optimization. */
913 optimize_tail_call (struct tailcall
*t
, bool opt_tailcalls
)
915 if (t
->tail_recursion
)
917 eliminate_tail_call (t
);
923 gimple stmt
= gsi_stmt (t
->call_gsi
);
925 gimple_call_set_tail (stmt
, true);
926 cfun
->tail_call_marked
= true;
927 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
929 fprintf (dump_file
, "Found tail call ");
930 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
931 fprintf (dump_file
, " in bb %i\n", (gsi_bb (t
->call_gsi
))->index
);
938 /* Creates a tail-call accumulator of the same type as the return type of the
939 current function. LABEL is the name used to creating the temporary
940 variable for the accumulator. The accumulator will be inserted in the
941 phis of a basic block BB with single predecessor with an initial value
942 INIT converted to the current function return type. */
945 create_tailcall_accumulator (const char *label
, basic_block bb
, tree init
)
947 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
948 if (POINTER_TYPE_P (ret_type
))
951 tree tmp
= make_temp_ssa_name (ret_type
, NULL
, label
);
954 phi
= create_phi_node (tmp
, bb
);
955 /* RET_TYPE can be a float when -ffast-maths is enabled. */
956 add_phi_arg (phi
, fold_convert (ret_type
, init
), single_pred_edge (bb
),
958 return PHI_RESULT (phi
);
961 /* Optimizes tail calls in the function, turning the tail recursion
965 tree_optimize_tail_calls_1 (bool opt_tailcalls
)
968 bool phis_constructed
= false;
969 struct tailcall
*tailcalls
= NULL
, *act
, *next
;
970 bool changed
= false;
971 basic_block first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
976 if (!suitable_for_tail_opt_p ())
979 opt_tailcalls
= suitable_for_tail_call_opt_p ();
981 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
983 /* Only traverse the normal exits, i.e. those that end with return
985 stmt
= last_stmt (e
->src
);
988 && gimple_code (stmt
) == GIMPLE_RETURN
)
989 find_tail_calls (e
->src
, &tailcalls
);
992 /* Construct the phi nodes and accumulators if necessary. */
993 a_acc
= m_acc
= NULL_TREE
;
994 for (act
= tailcalls
; act
; act
= act
->next
)
996 if (!act
->tail_recursion
)
999 if (!phis_constructed
)
1001 /* Ensure that there is only one predecessor of the block
1002 or if there are existing degenerate PHI nodes. */
1003 if (!single_pred_p (first
)
1004 || !gimple_seq_empty_p (phi_nodes (first
)))
1006 split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1008 /* Copy the args if needed. */
1009 for (param
= DECL_ARGUMENTS (current_function_decl
);
1011 param
= DECL_CHAIN (param
))
1012 if (arg_needs_copy_p (param
))
1014 tree name
= ssa_default_def (cfun
, param
);
1015 tree new_name
= make_ssa_name (param
, SSA_NAME_DEF_STMT (name
));
1018 set_ssa_default_def (cfun
, param
, new_name
);
1019 phi
= create_phi_node (name
, first
);
1020 add_phi_arg (phi
, new_name
, single_pred_edge (first
),
1021 EXPR_LOCATION (param
));
1023 phis_constructed
= true;
1026 if (act
->add
&& !a_acc
)
1027 a_acc
= create_tailcall_accumulator ("add_acc", first
,
1030 if (act
->mult
&& !m_acc
)
1031 m_acc
= create_tailcall_accumulator ("mult_acc", first
,
1037 /* When the tail call elimination using accumulators is performed,
1038 statements adding the accumulated value are inserted at all exits.
1039 This turns all other tail calls to non-tail ones. */
1040 opt_tailcalls
= false;
1043 for (; tailcalls
; tailcalls
= next
)
1045 next
= tailcalls
->next
;
1046 changed
|= optimize_tail_call (tailcalls
, opt_tailcalls
);
1052 /* Modify the remaining return statements. */
1053 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1055 stmt
= last_stmt (e
->src
);
1058 && gimple_code (stmt
) == GIMPLE_RETURN
)
1059 adjust_return_value (e
->src
, m_acc
, a_acc
);
1065 /* We may have created new loops. Make them magically appear. */
1066 loops_state_set (LOOPS_NEED_FIXUP
);
1067 free_dominance_info (CDI_DOMINATORS
);
1070 /* Add phi nodes for the virtual operands defined in the function to the
1071 header of the loop created by tail recursion elimination. Do so
1072 by triggering the SSA renamer. */
1073 if (phis_constructed
)
1074 mark_virtual_operands_for_renaming (cfun
);
1077 return TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
1082 gate_tail_calls (void)
1084 return flag_optimize_sibling_calls
!= 0 && dbg_cnt (tail_call
);
1088 execute_tail_calls (void)
1090 return tree_optimize_tail_calls_1 (true);
1095 const pass_data pass_data_tail_recursion
=
1097 GIMPLE_PASS
, /* type */
1099 OPTGROUP_NONE
, /* optinfo_flags */
1100 TV_NONE
, /* tv_id */
1101 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1102 0, /* properties_provided */
1103 0, /* properties_destroyed */
1104 0, /* todo_flags_start */
1105 0, /* todo_flags_finish */
1108 class pass_tail_recursion
: public gimple_opt_pass
1111 pass_tail_recursion (gcc::context
*ctxt
)
1112 : gimple_opt_pass (pass_data_tail_recursion
, ctxt
)
1115 /* opt_pass methods: */
1116 opt_pass
* clone () { return new pass_tail_recursion (m_ctxt
); }
1117 virtual bool gate (function
*) { return gate_tail_calls (); }
1118 virtual unsigned int execute (function
*)
1120 return tree_optimize_tail_calls_1 (false);
1123 }; // class pass_tail_recursion
1128 make_pass_tail_recursion (gcc::context
*ctxt
)
1130 return new pass_tail_recursion (ctxt
);
1135 const pass_data pass_data_tail_calls
=
1137 GIMPLE_PASS
, /* type */
1139 OPTGROUP_NONE
, /* optinfo_flags */
1140 TV_NONE
, /* tv_id */
1141 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1142 0, /* properties_provided */
1143 0, /* properties_destroyed */
1144 0, /* todo_flags_start */
1145 0, /* todo_flags_finish */
1148 class pass_tail_calls
: public gimple_opt_pass
1151 pass_tail_calls (gcc::context
*ctxt
)
1152 : gimple_opt_pass (pass_data_tail_calls
, ctxt
)
1155 /* opt_pass methods: */
1156 virtual bool gate (function
*) { return gate_tail_calls (); }
1157 virtual unsigned int execute (function
*) { return execute_tail_calls (); }
1159 }; // class pass_tail_calls
1164 make_pass_tail_calls (gcc::context
*ctxt
)
1166 return new pass_tail_calls (ctxt
);