1 /* Tail call optimization on trees.
2 Copyright (C) 2003-2019 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"
28 #include "tree-pass.h"
31 #include "gimple-pretty-print.h"
32 #include "fold-const.h"
33 #include "stor-layout.h"
34 #include "gimple-iterator.h"
35 #include "gimplify-me.h"
37 #include "tree-into-ssa.h"
43 #include "common/common-target.h"
44 #include "ipa-utils.h"
45 #include "tree-ssa-live.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 optimize_tail_call (struct tailcall
*, bool);
130 static void eliminate_tail_call (struct tailcall
*);
132 /* Returns false when the function is not suitable for tail call optimization
133 from some reason (e.g. if it takes variable number of arguments). */
136 suitable_for_tail_opt_p (void)
143 /* Returns false when the function is not suitable for tail call optimization
144 for some reason (e.g. if it takes variable number of arguments).
145 This test must pass in addition to suitable_for_tail_opt_p in order to make
146 tail call discovery happen. */
149 suitable_for_tail_call_opt_p (void)
153 /* alloca (until we have stack slot life analysis) inhibits
154 sibling call optimizations, but not tail recursion. */
155 if (cfun
->calls_alloca
)
158 /* If we are using sjlj exceptions, we may need to add a call to
159 _Unwind_SjLj_Unregister at exit of the function. Which means
160 that we cannot do any sibcall transformations. */
161 if (targetm_common
.except_unwind_info (&global_options
) == UI_SJLJ
162 && current_function_has_exception_handlers ())
165 /* Any function that calls setjmp might have longjmp called from
166 any called function. ??? We really should represent this
167 properly in the CFG so that this needn't be special cased. */
168 if (cfun
->calls_setjmp
)
171 /* ??? It is OK if the argument of a function is taken in some cases,
172 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
173 for (param
= DECL_ARGUMENTS (current_function_decl
);
175 param
= DECL_CHAIN (param
))
176 if (TREE_ADDRESSABLE (param
))
182 /* Checks whether the expression EXPR in stmt AT is independent of the
183 statement pointed to by GSI (in a sense that we already know EXPR's value
184 at GSI). We use the fact that we are only called from the chain of
185 basic blocks that have only single successor. Returns the expression
186 containing the value of EXPR at GSI. */
189 independent_of_stmt_p (tree expr
, gimple
*at
, gimple_stmt_iterator gsi
,
192 basic_block bb
, call_bb
, at_bb
;
196 if (is_gimple_min_invariant (expr
))
199 if (TREE_CODE (expr
) != SSA_NAME
)
202 if (bitmap_bit_p (to_move
, SSA_NAME_VERSION (expr
)))
205 /* Mark the blocks in the chain leading to the end. */
206 at_bb
= gimple_bb (at
);
207 call_bb
= gimple_bb (gsi_stmt (gsi
));
208 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
214 at
= SSA_NAME_DEF_STMT (expr
);
217 /* The default definition or defined before the chain. */
223 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
224 if (gsi_stmt (gsi
) == at
)
227 if (!gsi_end_p (gsi
))
232 if (gimple_code (at
) != GIMPLE_PHI
)
238 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
243 expr
= PHI_ARG_DEF_FROM_EDGE (at
, e
);
244 if (TREE_CODE (expr
) != SSA_NAME
)
246 /* The value is a constant. */
251 /* Unmark the blocks. */
252 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
259 enum par
{ FAIL
, OK
, TRY_MOVE
};
261 /* Simulates the effect of an assignment STMT on the return value of the tail
262 recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
263 additive factor for the real return value. */
266 process_assignment (gassign
*stmt
,
267 gimple_stmt_iterator call
, tree
*m
,
268 tree
*a
, tree
*ass_var
, bitmap to_move
)
270 tree op0
, op1
= NULL_TREE
, non_ass_var
= NULL_TREE
;
271 tree dest
= gimple_assign_lhs (stmt
);
272 enum tree_code code
= gimple_assign_rhs_code (stmt
);
273 enum gimple_rhs_class rhs_class
= get_gimple_rhs_class (code
);
274 tree src_var
= gimple_assign_rhs1 (stmt
);
276 /* See if this is a simple copy operation of an SSA name to the function
277 result. In that case we may have a simple tail call. Ignore type
278 conversions that can never produce extra code between the function
279 call and the function return. */
280 if ((rhs_class
== GIMPLE_SINGLE_RHS
|| gimple_assign_cast_p (stmt
))
281 && src_var
== *ass_var
)
283 /* Reject a tailcall if the type conversion might need
285 if (gimple_assign_cast_p (stmt
))
287 if (TYPE_MODE (TREE_TYPE (dest
)) != TYPE_MODE (TREE_TYPE (src_var
)))
290 /* Even if the type modes are the same, if the precision of the
291 type is smaller than mode's precision,
292 reduce_to_bit_field_precision would generate additional code. */
293 if (INTEGRAL_TYPE_P (TREE_TYPE (dest
))
294 && !type_has_mode_precision_p (TREE_TYPE (dest
)))
304 case GIMPLE_BINARY_RHS
:
305 op1
= gimple_assign_rhs2 (stmt
);
309 case GIMPLE_UNARY_RHS
:
310 op0
= gimple_assign_rhs1 (stmt
);
317 /* Accumulator optimizations will reverse the order of operations.
318 We can only do that for floating-point types if we're assuming
319 that addition and multiplication are associative. */
320 if (!flag_associative_math
)
321 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
324 if (rhs_class
== GIMPLE_UNARY_RHS
327 else if (op0
== *ass_var
328 && (non_ass_var
= independent_of_stmt_p (op1
, stmt
, call
,
331 else if (op1
== *ass_var
332 && (non_ass_var
= independent_of_stmt_p (op0
, stmt
, call
,
345 case POINTER_PLUS_EXPR
:
358 *m
= build_minus_one_cst (TREE_TYPE (op0
));
364 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
367 *m
= build_minus_one_cst (TREE_TYPE (non_ass_var
));
368 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
379 /* Propagate VAR through phis on edge E. */
382 propagate_through_phis (tree var
, edge e
)
384 basic_block dest
= e
->dest
;
387 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
389 gphi
*phi
= gsi
.phi ();
390 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
)
391 return PHI_RESULT (phi
);
396 /* Argument for compute_live_vars/live_vars_at_stmt and what compute_live_vars
397 returns. Computed lazily, but just once for the function. */
398 static live_vars_map
*live_vars
;
399 static vec
<bitmap_head
> live_vars_vec
;
401 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
402 added to the start of RET. */
405 find_tail_calls (basic_block bb
, struct tailcall
**ret
)
407 tree ass_var
= NULL_TREE
, ret_var
, func
, param
;
410 gimple_stmt_iterator gsi
, agsi
;
419 if (!single_succ_p (bb
))
422 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
424 stmt
= gsi_stmt (gsi
);
426 /* Ignore labels, returns, nops, clobbers and debug stmts. */
427 if (gimple_code (stmt
) == GIMPLE_LABEL
428 || gimple_code (stmt
) == GIMPLE_RETURN
429 || gimple_code (stmt
) == GIMPLE_NOP
430 || gimple_code (stmt
) == GIMPLE_PREDICT
431 || gimple_clobber_p (stmt
)
432 || is_gimple_debug (stmt
))
435 /* Check for a call. */
436 if (is_gimple_call (stmt
))
438 call
= as_a
<gcall
*> (stmt
);
439 ass_var
= gimple_call_lhs (call
);
443 /* Allow simple copies between local variables, even if they're
445 if (is_gimple_assign (stmt
)
446 && auto_var_in_fn_p (gimple_assign_lhs (stmt
), cfun
->decl
)
447 && auto_var_in_fn_p (gimple_assign_rhs1 (stmt
), cfun
->decl
))
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 or local
467 variable, we can't transform this into a tail or sibling call.
468 This situation happens, in (e.g.) "*p = foo()" where foo returns a
469 struct. In this case we won't have a temporary here, but we need
470 to carry out the side 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. */
478 && !is_gimple_reg (ass_var
)
479 && !auto_var_in_fn_p (ass_var
, cfun
->decl
))
482 /* If the call might throw an exception that wouldn't propagate out of
483 cfun, we can't transform to a tail or sibling call (82081). */
484 if (stmt_could_throw_p (cfun
, stmt
)
485 && !stmt_can_throw_external (cfun
, stmt
))
488 /* We found the call, check whether it is suitable. */
489 tail_recursion
= false;
490 func
= gimple_call_fndecl (call
);
492 && !fndecl_built_in_p (func
)
493 && recursive_call_p (current_function_decl
, func
))
497 for (param
= DECL_ARGUMENTS (current_function_decl
), idx
= 0;
498 param
&& idx
< gimple_call_num_args (call
);
499 param
= DECL_CHAIN (param
), idx
++)
501 arg
= gimple_call_arg (call
, idx
);
504 /* Make sure there are no problems with copying. The parameter
505 have a copyable type and the two arguments must have reasonably
506 equivalent types. The latter requirement could be relaxed if
507 we emitted a suitable type conversion statement. */
508 if (!is_gimple_reg_type (TREE_TYPE (param
))
509 || !useless_type_conversion_p (TREE_TYPE (param
),
513 /* The parameter should be a real operand, so that phi node
514 created for it at the start of the function has the meaning
515 of copying the value. This test implies is_gimple_reg_type
516 from the previous condition, however this one could be
517 relaxed by being more careful with copying the new value
518 of the parameter (emitting appropriate GIMPLE_ASSIGN and
519 updating the virtual operands). */
520 if (!is_gimple_reg (param
))
524 if (idx
== gimple_call_num_args (call
) && !param
)
525 tail_recursion
= true;
528 /* Compute live vars if not computed yet. */
529 if (live_vars
== NULL
)
531 unsigned int cnt
= 0;
532 FOR_EACH_LOCAL_DECL (cfun
, idx
, var
)
534 && auto_var_in_fn_p (var
, cfun
->decl
)
535 && may_be_aliased (var
))
537 if (live_vars
== NULL
)
538 live_vars
= new live_vars_map
;
539 live_vars
->put (DECL_UID (var
), cnt
++);
542 live_vars_vec
= compute_live_vars (cfun
, live_vars
);
545 /* Determine a bitmap of variables which are still in scope after the
547 bitmap local_live_vars
= NULL
;
549 local_live_vars
= live_vars_at_stmt (live_vars_vec
, live_vars
, call
);
551 /* Make sure the tail invocation of this function does not indirectly
552 refer to local variables. (Passing variables directly by value
554 FOR_EACH_LOCAL_DECL (cfun
, idx
, var
)
556 if (TREE_CODE (var
) != PARM_DECL
557 && auto_var_in_fn_p (var
, cfun
->decl
)
558 && may_be_aliased (var
)
559 && (ref_maybe_used_by_stmt_p (call
, var
)
560 || call_may_clobber_ref_p (call
, var
)))
565 BITMAP_FREE (local_live_vars
);
570 unsigned int *v
= live_vars
->get (DECL_UID (var
));
571 if (bitmap_bit_p (local_live_vars
, *v
))
573 BITMAP_FREE (local_live_vars
);
581 BITMAP_FREE (local_live_vars
);
583 /* Now check the statements after the call. None of them has virtual
584 operands, so they may only depend on the call through its return
585 value. The return value should also be dependent on each of them,
586 since we are running after dce. */
589 auto_bitmap to_move_defs
;
590 auto_vec
<gimple
*> to_move_stmts
;
596 tree tmp_a
= NULL_TREE
;
597 tree tmp_m
= NULL_TREE
;
600 while (gsi_end_p (agsi
))
602 ass_var
= propagate_through_phis (ass_var
, single_succ_edge (abb
));
603 abb
= single_succ (abb
);
604 agsi
= gsi_start_bb (abb
);
607 stmt
= gsi_stmt (agsi
);
608 if (gimple_code (stmt
) == GIMPLE_RETURN
)
611 if (gimple_code (stmt
) == GIMPLE_LABEL
612 || gimple_code (stmt
) == GIMPLE_NOP
613 || gimple_code (stmt
) == GIMPLE_PREDICT
614 || gimple_clobber_p (stmt
)
615 || is_gimple_debug (stmt
))
618 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
621 /* This is a gimple assign. */
622 par ret
= process_assignment (as_a
<gassign
*> (stmt
), gsi
,
623 &tmp_m
, &tmp_a
, &ass_var
, to_move_defs
);
626 else if (ret
== TRY_MOVE
)
628 if (! tail_recursion
)
630 /* Do not deal with checking dominance, the real fix is to
631 do path isolation for the transform phase anyway, removing
632 the need to compute the accumulators with new stmts. */
635 for (unsigned opno
= 1; opno
< gimple_num_ops (stmt
); ++opno
)
637 tree op
= gimple_op (stmt
, opno
);
638 if (independent_of_stmt_p (op
, stmt
, gsi
, to_move_defs
) != op
)
641 bitmap_set_bit (to_move_defs
,
642 SSA_NAME_VERSION (gimple_assign_lhs (stmt
)));
643 to_move_stmts
.safe_push (stmt
);
649 tree type
= TREE_TYPE (tmp_a
);
651 a
= fold_build2 (PLUS_EXPR
, type
, fold_convert (type
, a
), tmp_a
);
657 tree type
= TREE_TYPE (tmp_m
);
659 m
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, m
), tmp_m
);
664 a
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, a
), tmp_m
);
668 /* See if this is a tail call we can handle. */
669 ret_var
= gimple_return_retval (as_a
<greturn
*> (stmt
));
671 /* We may proceed if there either is no return value, or the return value
672 is identical to the call's return. */
674 && (ret_var
!= ass_var
))
677 /* If this is not a tail recursive call, we cannot handle addends or
679 if (!tail_recursion
&& (m
|| a
))
682 /* For pointers only allow additions. */
683 if (m
&& POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
686 /* Move queued defs. */
690 FOR_EACH_VEC_ELT (to_move_stmts
, i
, stmt
)
692 gimple_stmt_iterator mgsi
= gsi_for_stmt (stmt
);
693 gsi_move_before (&mgsi
, &gsi
);
697 nw
= XNEW (struct tailcall
);
701 nw
->tail_recursion
= tail_recursion
;
710 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
713 add_successor_phi_arg (edge e
, tree var
, tree phi_arg
)
717 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
718 if (PHI_RESULT (gsi
.phi ()) == var
)
721 gcc_assert (!gsi_end_p (gsi
));
722 add_phi_arg (gsi
.phi (), phi_arg
, e
, UNKNOWN_LOCATION
);
725 /* Creates a GIMPLE statement which computes the operation specified by
726 CODE, ACC and OP1 to a new variable with name LABEL and inserts the
727 statement in the position specified by GSI. Returns the
728 tree node of the statement's result. */
731 adjust_return_value_with_ops (enum tree_code code
, const char *label
,
732 tree acc
, tree op1
, gimple_stmt_iterator gsi
)
735 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
736 tree result
= make_temp_ssa_name (ret_type
, NULL
, label
);
739 if (POINTER_TYPE_P (ret_type
))
741 gcc_assert (code
== PLUS_EXPR
&& TREE_TYPE (acc
) == sizetype
);
742 code
= POINTER_PLUS_EXPR
;
744 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
))
745 && code
!= POINTER_PLUS_EXPR
)
746 stmt
= gimple_build_assign (result
, code
, acc
, op1
);
750 if (code
== POINTER_PLUS_EXPR
)
751 tem
= fold_build2 (code
, TREE_TYPE (op1
), op1
, acc
);
753 tem
= fold_build2 (code
, TREE_TYPE (op1
),
754 fold_convert (TREE_TYPE (op1
), acc
), op1
);
755 tree rhs
= fold_convert (ret_type
, tem
);
756 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
757 false, NULL
, true, GSI_SAME_STMT
);
758 stmt
= gimple_build_assign (result
, rhs
);
761 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
765 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
766 the computation specified by CODE and OP1 and insert the statement
767 at the position specified by GSI as a new statement. Returns new SSA name
768 of updated accumulator. */
771 update_accumulator_with_ops (enum tree_code code
, tree acc
, tree op1
,
772 gimple_stmt_iterator gsi
)
775 tree var
= copy_ssa_name (acc
);
776 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
)))
777 stmt
= gimple_build_assign (var
, code
, acc
, op1
);
780 tree rhs
= fold_convert (TREE_TYPE (acc
),
783 fold_convert (TREE_TYPE (op1
), acc
),
785 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
786 false, NULL
, false, GSI_CONTINUE_LINKING
);
787 stmt
= gimple_build_assign (var
, rhs
);
789 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
793 /* Adjust the accumulator values according to A and M after GSI, and update
794 the phi nodes on edge BACK. */
797 adjust_accumulator_values (gimple_stmt_iterator gsi
, tree m
, tree a
, edge back
)
799 tree var
, a_acc_arg
, m_acc_arg
;
802 m
= force_gimple_operand_gsi (&gsi
, m
, true, NULL
, true, GSI_SAME_STMT
);
804 a
= force_gimple_operand_gsi (&gsi
, a
, true, NULL
, true, GSI_SAME_STMT
);
812 if (integer_onep (a
))
815 var
= adjust_return_value_with_ops (MULT_EXPR
, "acc_tmp", m_acc
,
821 a_acc_arg
= update_accumulator_with_ops (PLUS_EXPR
, a_acc
, var
, gsi
);
825 m_acc_arg
= update_accumulator_with_ops (MULT_EXPR
, m_acc
, m
, gsi
);
828 add_successor_phi_arg (back
, a_acc
, a_acc_arg
);
831 add_successor_phi_arg (back
, m_acc
, m_acc_arg
);
834 /* Adjust value of the return at the end of BB according to M and A
838 adjust_return_value (basic_block bb
, tree m
, tree a
)
841 greturn
*ret_stmt
= as_a
<greturn
*> (gimple_seq_last_stmt (bb_seq (bb
)));
842 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
844 gcc_assert (gimple_code (ret_stmt
) == GIMPLE_RETURN
);
846 retval
= gimple_return_retval (ret_stmt
);
847 if (!retval
|| retval
== error_mark_node
)
851 retval
= adjust_return_value_with_ops (MULT_EXPR
, "mul_tmp", m_acc
, retval
,
854 retval
= adjust_return_value_with_ops (PLUS_EXPR
, "acc_tmp", a_acc
, retval
,
856 gimple_return_set_retval (ret_stmt
, retval
);
857 update_stmt (ret_stmt
);
860 /* Subtract COUNT and FREQUENCY from the basic block and it's
863 decrease_profile (basic_block bb
, profile_count count
)
865 bb
->count
= bb
->count
- count
;
866 if (!single_succ_p (bb
))
868 gcc_assert (!EDGE_COUNT (bb
->succs
));
873 /* Returns true if argument PARAM of the tail recursive call needs to be copied
874 when the call is eliminated. */
877 arg_needs_copy_p (tree param
)
881 if (!is_gimple_reg (param
))
884 /* Parameters that are only defined but never used need not be copied. */
885 def
= ssa_default_def (cfun
, param
);
892 /* Eliminates tail call described by T. TMP_VARS is a list of
893 temporary variables used to copy the function arguments. */
896 eliminate_tail_call (struct tailcall
*t
)
902 basic_block bb
, first
;
906 gimple_stmt_iterator gsi
;
909 stmt
= orig_stmt
= gsi_stmt (t
->call_gsi
);
910 bb
= gsi_bb (t
->call_gsi
);
912 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
914 fprintf (dump_file
, "Eliminated tail recursion in bb %d : ",
916 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
917 fprintf (dump_file
, "\n");
920 gcc_assert (is_gimple_call (stmt
));
922 first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
924 /* Remove the code after call_gsi that will become unreachable. The
925 possibly unreachable code in other blocks is removed later in
928 gimple_stmt_iterator gsi2
= gsi_last_bb (gimple_bb (gsi_stmt (gsi
)));
929 while (gsi_stmt (gsi2
) != gsi_stmt (gsi
))
931 gimple
*t
= gsi_stmt (gsi2
);
932 /* Do not remove the return statement, so that redirect_edge_and_branch
933 sees how the block ends. */
934 if (gimple_code (t
) != GIMPLE_RETURN
)
936 gimple_stmt_iterator gsi3
= gsi2
;
938 gsi_remove (&gsi3
, true);
945 /* Number of executions of function has reduced by the tailcall. */
946 e
= single_succ_edge (gsi_bb (t
->call_gsi
));
948 profile_count count
= e
->count ();
950 /* When profile is inconsistent and the recursion edge is more frequent
951 than number of executions of functions, scale it down, so we do not end
952 up with 0 executions of entry block. */
953 if (count
>= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
954 count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.apply_scale (7, 8);
955 decrease_profile (EXIT_BLOCK_PTR_FOR_FN (cfun
), count
);
956 decrease_profile (ENTRY_BLOCK_PTR_FOR_FN (cfun
), count
);
957 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
958 decrease_profile (e
->dest
, count
);
960 /* Replace the call by a jump to the start of function. */
961 e
= redirect_edge_and_branch (single_succ_edge (gsi_bb (t
->call_gsi
)),
964 PENDING_STMT (e
) = NULL
;
966 /* Add phi node entries for arguments. The ordering of the phi nodes should
967 be the same as the ordering of the arguments. */
968 for (param
= DECL_ARGUMENTS (current_function_decl
),
969 idx
= 0, gpi
= gsi_start_phis (first
);
971 param
= DECL_CHAIN (param
), idx
++)
973 if (!arg_needs_copy_p (param
))
976 arg
= gimple_call_arg (stmt
, idx
);
978 gcc_assert (param
== SSA_NAME_VAR (PHI_RESULT (phi
)));
980 add_phi_arg (phi
, arg
, e
, gimple_location (stmt
));
984 /* Update the values of accumulators. */
985 adjust_accumulator_values (t
->call_gsi
, t
->mult
, t
->add
, e
);
987 call
= gsi_stmt (t
->call_gsi
);
988 rslt
= gimple_call_lhs (call
);
989 if (rslt
!= NULL_TREE
&& TREE_CODE (rslt
) == SSA_NAME
)
991 /* Result of the call will no longer be defined. So adjust the
992 SSA_NAME_DEF_STMT accordingly. */
993 SSA_NAME_DEF_STMT (rslt
) = gimple_build_nop ();
996 gsi_remove (&t
->call_gsi
, true);
1000 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
1001 mark the tailcalls for the sibcall optimization. */
1004 optimize_tail_call (struct tailcall
*t
, bool opt_tailcalls
)
1006 if (t
->tail_recursion
)
1008 eliminate_tail_call (t
);
1014 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (t
->call_gsi
));
1016 gimple_call_set_tail (stmt
, true);
1017 cfun
->tail_call_marked
= true;
1018 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1020 fprintf (dump_file
, "Found tail call ");
1021 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
1022 fprintf (dump_file
, " in bb %i\n", (gsi_bb (t
->call_gsi
))->index
);
1029 /* Creates a tail-call accumulator of the same type as the return type of the
1030 current function. LABEL is the name used to creating the temporary
1031 variable for the accumulator. The accumulator will be inserted in the
1032 phis of a basic block BB with single predecessor with an initial value
1033 INIT converted to the current function return type. */
1036 create_tailcall_accumulator (const char *label
, basic_block bb
, tree init
)
1038 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
1039 if (POINTER_TYPE_P (ret_type
))
1040 ret_type
= sizetype
;
1042 tree tmp
= make_temp_ssa_name (ret_type
, NULL
, label
);
1045 phi
= create_phi_node (tmp
, bb
);
1046 /* RET_TYPE can be a float when -ffast-maths is enabled. */
1047 add_phi_arg (phi
, fold_convert (ret_type
, init
), single_pred_edge (bb
),
1049 return PHI_RESULT (phi
);
1052 /* Optimizes tail calls in the function, turning the tail recursion
1056 tree_optimize_tail_calls_1 (bool opt_tailcalls
)
1059 bool phis_constructed
= false;
1060 struct tailcall
*tailcalls
= NULL
, *act
, *next
;
1061 bool changed
= false;
1062 basic_block first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1067 if (!suitable_for_tail_opt_p ())
1070 opt_tailcalls
= suitable_for_tail_call_opt_p ();
1072 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1074 /* Only traverse the normal exits, i.e. those that end with return
1076 stmt
= last_stmt (e
->src
);
1079 && gimple_code (stmt
) == GIMPLE_RETURN
)
1080 find_tail_calls (e
->src
, &tailcalls
);
1085 destroy_live_vars (live_vars_vec
);
1090 /* Construct the phi nodes and accumulators if necessary. */
1091 a_acc
= m_acc
= NULL_TREE
;
1092 for (act
= tailcalls
; act
; act
= act
->next
)
1094 if (!act
->tail_recursion
)
1097 if (!phis_constructed
)
1099 /* Ensure that there is only one predecessor of the block
1100 or if there are existing degenerate PHI nodes. */
1101 if (!single_pred_p (first
)
1102 || !gimple_seq_empty_p (phi_nodes (first
)))
1104 split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1106 /* Copy the args if needed. */
1107 for (param
= DECL_ARGUMENTS (current_function_decl
);
1109 param
= DECL_CHAIN (param
))
1110 if (arg_needs_copy_p (param
))
1112 tree name
= ssa_default_def (cfun
, param
);
1113 tree new_name
= make_ssa_name (param
, SSA_NAME_DEF_STMT (name
));
1116 set_ssa_default_def (cfun
, param
, new_name
);
1117 phi
= create_phi_node (name
, first
);
1118 add_phi_arg (phi
, new_name
, single_pred_edge (first
),
1119 EXPR_LOCATION (param
));
1121 phis_constructed
= true;
1124 if (act
->add
&& !a_acc
)
1125 a_acc
= create_tailcall_accumulator ("add_acc", first
,
1128 if (act
->mult
&& !m_acc
)
1129 m_acc
= create_tailcall_accumulator ("mult_acc", first
,
1135 /* When the tail call elimination using accumulators is performed,
1136 statements adding the accumulated value are inserted at all exits.
1137 This turns all other tail calls to non-tail ones. */
1138 opt_tailcalls
= false;
1141 for (; tailcalls
; tailcalls
= next
)
1143 next
= tailcalls
->next
;
1144 changed
|= optimize_tail_call (tailcalls
, opt_tailcalls
);
1150 /* Modify the remaining return statements. */
1151 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1153 stmt
= last_stmt (e
->src
);
1156 && gimple_code (stmt
) == GIMPLE_RETURN
)
1157 adjust_return_value (e
->src
, m_acc
, a_acc
);
1163 /* We may have created new loops. Make them magically appear. */
1164 loops_state_set (LOOPS_NEED_FIXUP
);
1165 free_dominance_info (CDI_DOMINATORS
);
1168 /* Add phi nodes for the virtual operands defined in the function to the
1169 header of the loop created by tail recursion elimination. Do so
1170 by triggering the SSA renamer. */
1171 if (phis_constructed
)
1172 mark_virtual_operands_for_renaming (cfun
);
1175 return TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
1180 gate_tail_calls (void)
1182 return flag_optimize_sibling_calls
!= 0 && dbg_cnt (tail_call
);
1186 execute_tail_calls (void)
1188 return tree_optimize_tail_calls_1 (true);
1193 const pass_data pass_data_tail_recursion
=
1195 GIMPLE_PASS
, /* type */
1197 OPTGROUP_NONE
, /* optinfo_flags */
1198 TV_NONE
, /* tv_id */
1199 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1200 0, /* properties_provided */
1201 0, /* properties_destroyed */
1202 0, /* todo_flags_start */
1203 0, /* todo_flags_finish */
1206 class pass_tail_recursion
: public gimple_opt_pass
1209 pass_tail_recursion (gcc::context
*ctxt
)
1210 : gimple_opt_pass (pass_data_tail_recursion
, ctxt
)
1213 /* opt_pass methods: */
1214 opt_pass
* clone () { return new pass_tail_recursion (m_ctxt
); }
1215 virtual bool gate (function
*) { return gate_tail_calls (); }
1216 virtual unsigned int execute (function
*)
1218 return tree_optimize_tail_calls_1 (false);
1221 }; // class pass_tail_recursion
1226 make_pass_tail_recursion (gcc::context
*ctxt
)
1228 return new pass_tail_recursion (ctxt
);
1233 const pass_data pass_data_tail_calls
=
1235 GIMPLE_PASS
, /* type */
1237 OPTGROUP_NONE
, /* optinfo_flags */
1238 TV_NONE
, /* tv_id */
1239 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1240 0, /* properties_provided */
1241 0, /* properties_destroyed */
1242 0, /* todo_flags_start */
1243 0, /* todo_flags_finish */
1246 class pass_tail_calls
: public gimple_opt_pass
1249 pass_tail_calls (gcc::context
*ctxt
)
1250 : gimple_opt_pass (pass_data_tail_calls
, ctxt
)
1253 /* opt_pass methods: */
1254 virtual bool gate (function
*) { return gate_tail_calls (); }
1255 virtual unsigned int execute (function
*) { return execute_tail_calls (); }
1257 }; // class pass_tail_calls
1262 make_pass_tail_calls (gcc::context
*ctxt
)
1264 return new pass_tail_calls (ctxt
);