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)
144 /* Returns false when the function is not suitable for tail call optimization
145 for some reason (e.g. if it takes variable number of arguments).
146 This test must pass in addition to suitable_for_tail_opt_p in order to make
147 tail call discovery happen. */
150 suitable_for_tail_call_opt_p (void)
154 /* alloca (until we have stack slot life analysis) inhibits
155 sibling call optimizations, but not tail recursion. */
156 if (cfun
->calls_alloca
)
159 /* If we are using sjlj exceptions, we may need to add a call to
160 _Unwind_SjLj_Unregister at exit of the function. Which means
161 that we cannot do any sibcall transformations. */
162 if (targetm_common
.except_unwind_info (&global_options
) == UI_SJLJ
163 && current_function_has_exception_handlers ())
166 /* Any function that calls setjmp might have longjmp called from
167 any called function. ??? We really should represent this
168 properly in the CFG so that this needn't be special cased. */
169 if (cfun
->calls_setjmp
)
172 /* Various targets don't handle tail calls correctly in functions
173 that call __builtin_eh_return. */
174 if (cfun
->calls_eh_return
)
177 /* ??? It is OK if the argument of a function is taken in some cases,
178 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
179 for (param
= DECL_ARGUMENTS (current_function_decl
);
181 param
= DECL_CHAIN (param
))
182 if (TREE_ADDRESSABLE (param
))
188 /* Checks whether the expression EXPR in stmt AT is independent of the
189 statement pointed to by GSI (in a sense that we already know EXPR's value
190 at GSI). We use the fact that we are only called from the chain of
191 basic blocks that have only single successor. Returns the expression
192 containing the value of EXPR at GSI. */
195 independent_of_stmt_p (tree expr
, gimple
*at
, gimple_stmt_iterator gsi
,
198 basic_block bb
, call_bb
, at_bb
;
202 if (is_gimple_min_invariant (expr
))
205 if (TREE_CODE (expr
) != SSA_NAME
)
208 if (bitmap_bit_p (to_move
, SSA_NAME_VERSION (expr
)))
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 enum par
{ FAIL
, OK
, TRY_MOVE
};
267 /* Simulates the effect of an assignment STMT on the return value of the tail
268 recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
269 additive factor for the real return value. */
272 process_assignment (gassign
*stmt
,
273 gimple_stmt_iterator call
, tree
*m
,
274 tree
*a
, tree
*ass_var
, bitmap to_move
)
276 tree op0
, op1
= NULL_TREE
, non_ass_var
= NULL_TREE
;
277 tree dest
= gimple_assign_lhs (stmt
);
278 enum tree_code code
= gimple_assign_rhs_code (stmt
);
279 enum gimple_rhs_class rhs_class
= get_gimple_rhs_class (code
);
280 tree src_var
= gimple_assign_rhs1 (stmt
);
282 /* See if this is a simple copy operation of an SSA name to the function
283 result. In that case we may have a simple tail call. Ignore type
284 conversions that can never produce extra code between the function
285 call and the function return. */
286 if ((rhs_class
== GIMPLE_SINGLE_RHS
|| gimple_assign_cast_p (stmt
))
287 && src_var
== *ass_var
)
289 /* Reject a tailcall if the type conversion might need
291 if (gimple_assign_cast_p (stmt
))
293 if (TYPE_MODE (TREE_TYPE (dest
)) != TYPE_MODE (TREE_TYPE (src_var
)))
296 /* Even if the type modes are the same, if the precision of the
297 type is smaller than mode's precision,
298 reduce_to_bit_field_precision would generate additional code. */
299 if (INTEGRAL_TYPE_P (TREE_TYPE (dest
))
300 && !type_has_mode_precision_p (TREE_TYPE (dest
)))
310 case GIMPLE_BINARY_RHS
:
311 op1
= gimple_assign_rhs2 (stmt
);
315 case GIMPLE_UNARY_RHS
:
316 op0
= gimple_assign_rhs1 (stmt
);
323 /* Accumulator optimizations will reverse the order of operations.
324 We can only do that for floating-point types if we're assuming
325 that addition and multiplication are associative. */
326 if (!flag_associative_math
)
327 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
330 if (rhs_class
== GIMPLE_UNARY_RHS
333 else if (op0
== *ass_var
334 && (non_ass_var
= independent_of_stmt_p (op1
, stmt
, call
,
337 else if (op1
== *ass_var
338 && (non_ass_var
= independent_of_stmt_p (op0
, stmt
, call
,
351 case POINTER_PLUS_EXPR
:
364 *m
= build_minus_one_cst (TREE_TYPE (op0
));
370 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
373 *m
= build_minus_one_cst (TREE_TYPE (non_ass_var
));
374 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
385 /* Propagate VAR through phis on edge E. */
388 propagate_through_phis (tree var
, edge e
)
390 basic_block dest
= e
->dest
;
393 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
395 gphi
*phi
= gsi
.phi ();
396 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
)
397 return PHI_RESULT (phi
);
402 /* Argument for compute_live_vars/live_vars_at_stmt and what compute_live_vars
403 returns. Computed lazily, but just once for the function. */
404 static live_vars_map
*live_vars
;
405 static vec
<bitmap_head
> live_vars_vec
;
407 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
408 added to the start of RET. */
411 find_tail_calls (basic_block bb
, struct tailcall
**ret
)
413 tree ass_var
= NULL_TREE
, ret_var
, func
, param
;
416 gimple_stmt_iterator gsi
, agsi
;
425 if (!single_succ_p (bb
))
428 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
430 stmt
= gsi_stmt (gsi
);
432 /* Ignore labels, returns, nops, clobbers and debug stmts. */
433 if (gimple_code (stmt
) == GIMPLE_LABEL
434 || gimple_code (stmt
) == GIMPLE_RETURN
435 || gimple_code (stmt
) == GIMPLE_NOP
436 || gimple_code (stmt
) == GIMPLE_PREDICT
437 || gimple_clobber_p (stmt
)
438 || is_gimple_debug (stmt
))
441 /* Check for a call. */
442 if (is_gimple_call (stmt
))
444 call
= as_a
<gcall
*> (stmt
);
445 ass_var
= gimple_call_lhs (call
);
449 /* Allow simple copies between local variables, even if they're
451 if (is_gimple_assign (stmt
)
452 && auto_var_in_fn_p (gimple_assign_lhs (stmt
), cfun
->decl
)
453 && auto_var_in_fn_p (gimple_assign_rhs1 (stmt
), cfun
->decl
))
456 /* If the statement references memory or volatile operands, fail. */
457 if (gimple_references_memory_p (stmt
)
458 || gimple_has_volatile_ops (stmt
))
465 /* Recurse to the predecessors. */
466 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
467 find_tail_calls (e
->src
, ret
);
472 /* If the LHS of our call is not just a simple register or local
473 variable, we can't transform this into a tail or sibling call.
474 This situation happens, in (e.g.) "*p = foo()" where foo returns a
475 struct. In this case we won't have a temporary here, but we need
476 to carry out the side effect anyway, so tailcall is impossible.
478 ??? In some situations (when the struct is returned in memory via
479 invisible argument) we could deal with this, e.g. by passing 'p'
480 itself as that argument to foo, but it's too early to do this here,
481 and expand_call() will not handle it anyway. If it ever can, then
482 we need to revisit this here, to allow that situation. */
484 && !is_gimple_reg (ass_var
)
485 && !auto_var_in_fn_p (ass_var
, cfun
->decl
))
488 /* If the call might throw an exception that wouldn't propagate out of
489 cfun, we can't transform to a tail or sibling call (82081). */
490 if (stmt_could_throw_p (cfun
, stmt
)
491 && !stmt_can_throw_external (cfun
, stmt
))
494 /* We found the call, check whether it is suitable. */
495 tail_recursion
= false;
496 func
= gimple_call_fndecl (call
);
498 && !fndecl_built_in_p (func
)
499 && recursive_call_p (current_function_decl
, func
))
503 for (param
= DECL_ARGUMENTS (current_function_decl
), idx
= 0;
504 param
&& idx
< gimple_call_num_args (call
);
505 param
= DECL_CHAIN (param
), idx
++)
507 arg
= gimple_call_arg (call
, idx
);
510 /* Make sure there are no problems with copying. The parameter
511 have a copyable type and the two arguments must have reasonably
512 equivalent types. The latter requirement could be relaxed if
513 we emitted a suitable type conversion statement. */
514 if (!is_gimple_reg_type (TREE_TYPE (param
))
515 || !useless_type_conversion_p (TREE_TYPE (param
),
519 /* The parameter should be a real operand, so that phi node
520 created for it at the start of the function has the meaning
521 of copying the value. This test implies is_gimple_reg_type
522 from the previous condition, however this one could be
523 relaxed by being more careful with copying the new value
524 of the parameter (emitting appropriate GIMPLE_ASSIGN and
525 updating the virtual operands). */
526 if (!is_gimple_reg (param
))
530 if (idx
== gimple_call_num_args (call
) && !param
)
531 tail_recursion
= true;
534 /* Compute live vars if not computed yet. */
535 if (live_vars
== NULL
)
537 unsigned int cnt
= 0;
538 FOR_EACH_LOCAL_DECL (cfun
, idx
, var
)
540 && auto_var_in_fn_p (var
, cfun
->decl
)
541 && may_be_aliased (var
))
543 if (live_vars
== NULL
)
544 live_vars
= new live_vars_map
;
545 live_vars
->put (DECL_UID (var
), cnt
++);
548 live_vars_vec
= compute_live_vars (cfun
, live_vars
);
551 /* Determine a bitmap of variables which are still in scope after the
553 bitmap local_live_vars
= NULL
;
555 local_live_vars
= live_vars_at_stmt (live_vars_vec
, live_vars
, call
);
557 /* Make sure the tail invocation of this function does not indirectly
558 refer to local variables. (Passing variables directly by value
560 FOR_EACH_LOCAL_DECL (cfun
, idx
, var
)
562 if (TREE_CODE (var
) != PARM_DECL
563 && auto_var_in_fn_p (var
, cfun
->decl
)
564 && may_be_aliased (var
)
565 && (ref_maybe_used_by_stmt_p (call
, var
)
566 || call_may_clobber_ref_p (call
, var
)))
571 BITMAP_FREE (local_live_vars
);
576 unsigned int *v
= live_vars
->get (DECL_UID (var
));
577 if (bitmap_bit_p (local_live_vars
, *v
))
579 BITMAP_FREE (local_live_vars
);
587 BITMAP_FREE (local_live_vars
);
589 /* Now check the statements after the call. None of them has virtual
590 operands, so they may only depend on the call through its return
591 value. The return value should also be dependent on each of them,
592 since we are running after dce. */
595 auto_bitmap to_move_defs
;
596 auto_vec
<gimple
*> to_move_stmts
;
602 tree tmp_a
= NULL_TREE
;
603 tree tmp_m
= NULL_TREE
;
606 while (gsi_end_p (agsi
))
608 ass_var
= propagate_through_phis (ass_var
, single_succ_edge (abb
));
609 abb
= single_succ (abb
);
610 agsi
= gsi_start_bb (abb
);
613 stmt
= gsi_stmt (agsi
);
614 if (gimple_code (stmt
) == GIMPLE_RETURN
)
617 if (gimple_code (stmt
) == GIMPLE_LABEL
618 || gimple_code (stmt
) == GIMPLE_NOP
619 || gimple_code (stmt
) == GIMPLE_PREDICT
620 || gimple_clobber_p (stmt
)
621 || is_gimple_debug (stmt
))
624 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
627 /* This is a gimple assign. */
628 par ret
= process_assignment (as_a
<gassign
*> (stmt
), gsi
,
629 &tmp_m
, &tmp_a
, &ass_var
, to_move_defs
);
632 else if (ret
== TRY_MOVE
)
634 if (! tail_recursion
)
636 /* Do not deal with checking dominance, the real fix is to
637 do path isolation for the transform phase anyway, removing
638 the need to compute the accumulators with new stmts. */
641 for (unsigned opno
= 1; opno
< gimple_num_ops (stmt
); ++opno
)
643 tree op
= gimple_op (stmt
, opno
);
644 if (independent_of_stmt_p (op
, stmt
, gsi
, to_move_defs
) != op
)
647 bitmap_set_bit (to_move_defs
,
648 SSA_NAME_VERSION (gimple_assign_lhs (stmt
)));
649 to_move_stmts
.safe_push (stmt
);
655 tree type
= TREE_TYPE (tmp_a
);
657 a
= fold_build2 (PLUS_EXPR
, type
, fold_convert (type
, a
), tmp_a
);
663 tree type
= TREE_TYPE (tmp_m
);
665 m
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, m
), tmp_m
);
670 a
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, a
), tmp_m
);
674 /* See if this is a tail call we can handle. */
675 ret_var
= gimple_return_retval (as_a
<greturn
*> (stmt
));
677 /* We may proceed if there either is no return value, or the return value
678 is identical to the call's return. */
680 && (ret_var
!= ass_var
))
683 /* If this is not a tail recursive call, we cannot handle addends or
685 if (!tail_recursion
&& (m
|| a
))
688 /* For pointers only allow additions. */
689 if (m
&& POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
692 /* Move queued defs. */
696 FOR_EACH_VEC_ELT (to_move_stmts
, i
, stmt
)
698 gimple_stmt_iterator mgsi
= gsi_for_stmt (stmt
);
699 gsi_move_before (&mgsi
, &gsi
);
703 nw
= XNEW (struct tailcall
);
707 nw
->tail_recursion
= tail_recursion
;
716 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
719 add_successor_phi_arg (edge e
, tree var
, tree phi_arg
)
723 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
724 if (PHI_RESULT (gsi
.phi ()) == var
)
727 gcc_assert (!gsi_end_p (gsi
));
728 add_phi_arg (gsi
.phi (), phi_arg
, e
, UNKNOWN_LOCATION
);
731 /* Creates a GIMPLE statement which computes the operation specified by
732 CODE, ACC and OP1 to a new variable with name LABEL and inserts the
733 statement in the position specified by GSI. Returns the
734 tree node of the statement's result. */
737 adjust_return_value_with_ops (enum tree_code code
, const char *label
,
738 tree acc
, tree op1
, gimple_stmt_iterator gsi
)
741 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
742 tree result
= make_temp_ssa_name (ret_type
, NULL
, label
);
745 if (POINTER_TYPE_P (ret_type
))
747 gcc_assert (code
== PLUS_EXPR
&& TREE_TYPE (acc
) == sizetype
);
748 code
= POINTER_PLUS_EXPR
;
750 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
))
751 && code
!= POINTER_PLUS_EXPR
)
752 stmt
= gimple_build_assign (result
, code
, acc
, op1
);
756 if (code
== POINTER_PLUS_EXPR
)
757 tem
= fold_build2 (code
, TREE_TYPE (op1
), op1
, acc
);
759 tem
= fold_build2 (code
, TREE_TYPE (op1
),
760 fold_convert (TREE_TYPE (op1
), acc
), op1
);
761 tree rhs
= fold_convert (ret_type
, tem
);
762 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
763 false, NULL
, true, GSI_SAME_STMT
);
764 stmt
= gimple_build_assign (result
, rhs
);
767 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
771 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
772 the computation specified by CODE and OP1 and insert the statement
773 at the position specified by GSI as a new statement. Returns new SSA name
774 of updated accumulator. */
777 update_accumulator_with_ops (enum tree_code code
, tree acc
, tree op1
,
778 gimple_stmt_iterator gsi
)
781 tree var
= copy_ssa_name (acc
);
782 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
)))
783 stmt
= gimple_build_assign (var
, code
, acc
, op1
);
786 tree rhs
= fold_convert (TREE_TYPE (acc
),
789 fold_convert (TREE_TYPE (op1
), acc
),
791 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
792 false, NULL
, false, GSI_CONTINUE_LINKING
);
793 stmt
= gimple_build_assign (var
, rhs
);
795 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
799 /* Adjust the accumulator values according to A and M after GSI, and update
800 the phi nodes on edge BACK. */
803 adjust_accumulator_values (gimple_stmt_iterator gsi
, tree m
, tree a
, edge back
)
805 tree var
, a_acc_arg
, m_acc_arg
;
808 m
= force_gimple_operand_gsi (&gsi
, m
, true, NULL
, true, GSI_SAME_STMT
);
810 a
= force_gimple_operand_gsi (&gsi
, a
, true, NULL
, true, GSI_SAME_STMT
);
818 if (integer_onep (a
))
821 var
= adjust_return_value_with_ops (MULT_EXPR
, "acc_tmp", m_acc
,
827 a_acc_arg
= update_accumulator_with_ops (PLUS_EXPR
, a_acc
, var
, gsi
);
831 m_acc_arg
= update_accumulator_with_ops (MULT_EXPR
, m_acc
, m
, gsi
);
834 add_successor_phi_arg (back
, a_acc
, a_acc_arg
);
837 add_successor_phi_arg (back
, m_acc
, m_acc_arg
);
840 /* Adjust value of the return at the end of BB according to M and A
844 adjust_return_value (basic_block bb
, tree m
, tree a
)
847 greturn
*ret_stmt
= as_a
<greturn
*> (gimple_seq_last_stmt (bb_seq (bb
)));
848 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
850 gcc_assert (gimple_code (ret_stmt
) == GIMPLE_RETURN
);
852 retval
= gimple_return_retval (ret_stmt
);
853 if (!retval
|| retval
== error_mark_node
)
857 retval
= adjust_return_value_with_ops (MULT_EXPR
, "mul_tmp", m_acc
, retval
,
860 retval
= adjust_return_value_with_ops (PLUS_EXPR
, "acc_tmp", a_acc
, retval
,
862 gimple_return_set_retval (ret_stmt
, retval
);
863 update_stmt (ret_stmt
);
866 /* Subtract COUNT and FREQUENCY from the basic block and it's
869 decrease_profile (basic_block bb
, profile_count count
)
871 bb
->count
= bb
->count
- count
;
872 if (!single_succ_p (bb
))
874 gcc_assert (!EDGE_COUNT (bb
->succs
));
879 /* Returns true if argument PARAM of the tail recursive call needs to be copied
880 when the call is eliminated. */
883 arg_needs_copy_p (tree param
)
887 if (!is_gimple_reg (param
))
890 /* Parameters that are only defined but never used need not be copied. */
891 def
= ssa_default_def (cfun
, param
);
898 /* Eliminates tail call described by T. TMP_VARS is a list of
899 temporary variables used to copy the function arguments. */
902 eliminate_tail_call (struct tailcall
*t
)
908 basic_block bb
, first
;
912 gimple_stmt_iterator gsi
;
915 stmt
= orig_stmt
= gsi_stmt (t
->call_gsi
);
916 bb
= gsi_bb (t
->call_gsi
);
918 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
920 fprintf (dump_file
, "Eliminated tail recursion in bb %d : ",
922 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
923 fprintf (dump_file
, "\n");
926 gcc_assert (is_gimple_call (stmt
));
928 first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
930 /* Remove the code after call_gsi that will become unreachable. The
931 possibly unreachable code in other blocks is removed later in
934 gimple_stmt_iterator gsi2
= gsi_last_bb (gimple_bb (gsi_stmt (gsi
)));
935 while (gsi_stmt (gsi2
) != gsi_stmt (gsi
))
937 gimple
*t
= gsi_stmt (gsi2
);
938 /* Do not remove the return statement, so that redirect_edge_and_branch
939 sees how the block ends. */
940 if (gimple_code (t
) != GIMPLE_RETURN
)
942 gimple_stmt_iterator gsi3
= gsi2
;
944 gsi_remove (&gsi3
, true);
951 /* Number of executions of function has reduced by the tailcall. */
952 e
= single_succ_edge (gsi_bb (t
->call_gsi
));
954 profile_count count
= e
->count ();
956 /* When profile is inconsistent and the recursion edge is more frequent
957 than number of executions of functions, scale it down, so we do not end
958 up with 0 executions of entry block. */
959 if (count
>= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
960 count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.apply_scale (7, 8);
961 decrease_profile (EXIT_BLOCK_PTR_FOR_FN (cfun
), count
);
962 decrease_profile (ENTRY_BLOCK_PTR_FOR_FN (cfun
), count
);
963 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
964 decrease_profile (e
->dest
, count
);
966 /* Replace the call by a jump to the start of function. */
967 e
= redirect_edge_and_branch (single_succ_edge (gsi_bb (t
->call_gsi
)),
970 PENDING_STMT (e
) = NULL
;
972 /* Add phi node entries for arguments. The ordering of the phi nodes should
973 be the same as the ordering of the arguments. */
974 for (param
= DECL_ARGUMENTS (current_function_decl
),
975 idx
= 0, gpi
= gsi_start_phis (first
);
977 param
= DECL_CHAIN (param
), idx
++)
979 if (!arg_needs_copy_p (param
))
982 arg
= gimple_call_arg (stmt
, idx
);
984 gcc_assert (param
== SSA_NAME_VAR (PHI_RESULT (phi
)));
986 add_phi_arg (phi
, arg
, e
, gimple_location (stmt
));
990 /* Update the values of accumulators. */
991 adjust_accumulator_values (t
->call_gsi
, t
->mult
, t
->add
, e
);
993 call
= gsi_stmt (t
->call_gsi
);
994 rslt
= gimple_call_lhs (call
);
995 if (rslt
!= NULL_TREE
&& TREE_CODE (rslt
) == SSA_NAME
)
997 /* Result of the call will no longer be defined. So adjust the
998 SSA_NAME_DEF_STMT accordingly. */
999 SSA_NAME_DEF_STMT (rslt
) = gimple_build_nop ();
1002 gsi_remove (&t
->call_gsi
, true);
1003 release_defs (call
);
1006 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
1007 mark the tailcalls for the sibcall optimization. */
1010 optimize_tail_call (struct tailcall
*t
, bool opt_tailcalls
)
1012 if (t
->tail_recursion
)
1014 eliminate_tail_call (t
);
1020 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (t
->call_gsi
));
1022 gimple_call_set_tail (stmt
, true);
1023 cfun
->tail_call_marked
= true;
1024 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1026 fprintf (dump_file
, "Found tail call ");
1027 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
1028 fprintf (dump_file
, " in bb %i\n", (gsi_bb (t
->call_gsi
))->index
);
1035 /* Creates a tail-call accumulator of the same type as the return type of the
1036 current function. LABEL is the name used to creating the temporary
1037 variable for the accumulator. The accumulator will be inserted in the
1038 phis of a basic block BB with single predecessor with an initial value
1039 INIT converted to the current function return type. */
1042 create_tailcall_accumulator (const char *label
, basic_block bb
, tree init
)
1044 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
1045 if (POINTER_TYPE_P (ret_type
))
1046 ret_type
= sizetype
;
1048 tree tmp
= make_temp_ssa_name (ret_type
, NULL
, label
);
1051 phi
= create_phi_node (tmp
, bb
);
1052 /* RET_TYPE can be a float when -ffast-maths is enabled. */
1053 add_phi_arg (phi
, fold_convert (ret_type
, init
), single_pred_edge (bb
),
1055 return PHI_RESULT (phi
);
1058 /* Optimizes tail calls in the function, turning the tail recursion
1062 tree_optimize_tail_calls_1 (bool opt_tailcalls
)
1065 bool phis_constructed
= false;
1066 struct tailcall
*tailcalls
= NULL
, *act
, *next
;
1067 bool changed
= false;
1068 basic_block first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1073 if (!suitable_for_tail_opt_p ())
1076 opt_tailcalls
= suitable_for_tail_call_opt_p ();
1078 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1080 /* Only traverse the normal exits, i.e. those that end with return
1082 stmt
= last_stmt (e
->src
);
1085 && gimple_code (stmt
) == GIMPLE_RETURN
)
1086 find_tail_calls (e
->src
, &tailcalls
);
1091 destroy_live_vars (live_vars_vec
);
1096 /* Construct the phi nodes and accumulators if necessary. */
1097 a_acc
= m_acc
= NULL_TREE
;
1098 for (act
= tailcalls
; act
; act
= act
->next
)
1100 if (!act
->tail_recursion
)
1103 if (!phis_constructed
)
1105 /* Ensure that there is only one predecessor of the block
1106 or if there are existing degenerate PHI nodes. */
1107 if (!single_pred_p (first
)
1108 || !gimple_seq_empty_p (phi_nodes (first
)))
1110 split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1112 /* Copy the args if needed. */
1113 for (param
= DECL_ARGUMENTS (current_function_decl
);
1115 param
= DECL_CHAIN (param
))
1116 if (arg_needs_copy_p (param
))
1118 tree name
= ssa_default_def (cfun
, param
);
1119 tree new_name
= make_ssa_name (param
, SSA_NAME_DEF_STMT (name
));
1122 set_ssa_default_def (cfun
, param
, new_name
);
1123 phi
= create_phi_node (name
, first
);
1124 add_phi_arg (phi
, new_name
, single_pred_edge (first
),
1125 EXPR_LOCATION (param
));
1127 phis_constructed
= true;
1130 if (act
->add
&& !a_acc
)
1131 a_acc
= create_tailcall_accumulator ("add_acc", first
,
1134 if (act
->mult
&& !m_acc
)
1135 m_acc
= create_tailcall_accumulator ("mult_acc", first
,
1141 /* When the tail call elimination using accumulators is performed,
1142 statements adding the accumulated value are inserted at all exits.
1143 This turns all other tail calls to non-tail ones. */
1144 opt_tailcalls
= false;
1147 for (; tailcalls
; tailcalls
= next
)
1149 next
= tailcalls
->next
;
1150 changed
|= optimize_tail_call (tailcalls
, opt_tailcalls
);
1156 /* Modify the remaining return statements. */
1157 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1159 stmt
= last_stmt (e
->src
);
1162 && gimple_code (stmt
) == GIMPLE_RETURN
)
1163 adjust_return_value (e
->src
, m_acc
, a_acc
);
1169 /* We may have created new loops. Make them magically appear. */
1170 loops_state_set (LOOPS_NEED_FIXUP
);
1171 free_dominance_info (CDI_DOMINATORS
);
1174 /* Add phi nodes for the virtual operands defined in the function to the
1175 header of the loop created by tail recursion elimination. Do so
1176 by triggering the SSA renamer. */
1177 if (phis_constructed
)
1178 mark_virtual_operands_for_renaming (cfun
);
1181 return TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
1186 gate_tail_calls (void)
1188 return flag_optimize_sibling_calls
!= 0 && dbg_cnt (tail_call
);
1192 execute_tail_calls (void)
1194 return tree_optimize_tail_calls_1 (true);
1199 const pass_data pass_data_tail_recursion
=
1201 GIMPLE_PASS
, /* type */
1203 OPTGROUP_NONE
, /* optinfo_flags */
1204 TV_NONE
, /* tv_id */
1205 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1206 0, /* properties_provided */
1207 0, /* properties_destroyed */
1208 0, /* todo_flags_start */
1209 0, /* todo_flags_finish */
1212 class pass_tail_recursion
: public gimple_opt_pass
1215 pass_tail_recursion (gcc::context
*ctxt
)
1216 : gimple_opt_pass (pass_data_tail_recursion
, ctxt
)
1219 /* opt_pass methods: */
1220 opt_pass
* clone () { return new pass_tail_recursion (m_ctxt
); }
1221 virtual bool gate (function
*) { return gate_tail_calls (); }
1222 virtual unsigned int execute (function
*)
1224 return tree_optimize_tail_calls_1 (false);
1227 }; // class pass_tail_recursion
1232 make_pass_tail_recursion (gcc::context
*ctxt
)
1234 return new pass_tail_recursion (ctxt
);
1239 const pass_data pass_data_tail_calls
=
1241 GIMPLE_PASS
, /* type */
1243 OPTGROUP_NONE
, /* optinfo_flags */
1244 TV_NONE
, /* tv_id */
1245 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1246 0, /* properties_provided */
1247 0, /* properties_destroyed */
1248 0, /* todo_flags_start */
1249 0, /* todo_flags_finish */
1252 class pass_tail_calls
: public gimple_opt_pass
1255 pass_tail_calls (gcc::context
*ctxt
)
1256 : gimple_opt_pass (pass_data_tail_calls
, ctxt
)
1259 /* opt_pass methods: */
1260 virtual bool gate (function
*) { return gate_tail_calls (); }
1261 virtual unsigned int execute (function
*) { return execute_tail_calls (); }
1263 }; // class pass_tail_calls
1268 make_pass_tail_calls (gcc::context
*ctxt
)
1270 return new pass_tail_calls (ctxt
);