1 /* Tail call optimization on trees.
2 Copyright (C) 2003-2017 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"
42 #include "common/common-target.h"
43 #include "ipa-utils.h"
45 /* The file implements the tail recursion elimination. It is also used to
46 analyze the tail calls in general, passing the results to the rtl level
47 where they are used for sibcall optimization.
49 In addition to the standard tail recursion elimination, we handle the most
50 trivial cases of making the call tail recursive by creating accumulators.
51 For example the following function
56 return n + sum (n - 1);
73 To do this, we maintain two accumulators (a_acc and m_acc) that indicate
74 when we reach the return x statement, we should return a_acc + x * m_acc
75 instead. They are initially initialized to 0 and 1, respectively,
76 so the semantics of the function is obviously preserved. If we are
77 guaranteed that the value of the accumulator never change, we
80 There are three cases how the function may exit. The first one is
81 handled in adjust_return_value, the other two in adjust_accumulator_values
82 (the second case is actually a special case of the third one and we
83 present it separately just for clarity):
85 1) Just return x, where x is not in any of the remaining special shapes.
86 We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
88 2) return f (...), where f is the current function, is rewritten in a
89 classical tail-recursion elimination way, into assignment of arguments
90 and jump to the start of the function. Values of the accumulators
93 3) return a + m * f(...), where a and m do not depend on call to f.
94 To preserve the semantics described before we want this to be rewritten
95 in such a way that we finally return
97 a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
99 I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
100 eliminate the tail call to f. Special cases when the value is just
101 added or just multiplied are obtained by setting a = 0 or m = 1.
103 TODO -- it is possible to do similar tricks for other operations. */
105 /* A structure that describes the tailcall. */
109 /* The iterator pointing to the call statement. */
110 gimple_stmt_iterator call_gsi
;
112 /* True if it is a call to the current function. */
115 /* The return value of the caller is mult * f + add, where f is the return
116 value of the call. */
119 /* Next tailcall in the chain. */
120 struct tailcall
*next
;
123 /* The variables holding the value of multiplicative and additive
125 static tree m_acc
, a_acc
;
127 static bool optimize_tail_call (struct tailcall
*, bool);
128 static void eliminate_tail_call (struct tailcall
*);
130 /* Returns false when the function is not suitable for tail call optimization
131 from some reason (e.g. if it takes variable number of arguments). */
134 suitable_for_tail_opt_p (void)
141 /* Returns false when the function is not suitable for tail call optimization
142 for some reason (e.g. if it takes variable number of arguments).
143 This test must pass in addition to suitable_for_tail_opt_p in order to make
144 tail call discovery happen. */
147 suitable_for_tail_call_opt_p (void)
151 /* alloca (until we have stack slot life analysis) inhibits
152 sibling call optimizations, but not tail recursion. */
153 if (cfun
->calls_alloca
)
156 /* If we are using sjlj exceptions, we may need to add a call to
157 _Unwind_SjLj_Unregister at exit of the function. Which means
158 that we cannot do any sibcall transformations. */
159 if (targetm_common
.except_unwind_info (&global_options
) == UI_SJLJ
160 && current_function_has_exception_handlers ())
163 /* Any function that calls setjmp might have longjmp called from
164 any called function. ??? We really should represent this
165 properly in the CFG so that this needn't be special cased. */
166 if (cfun
->calls_setjmp
)
169 /* ??? It is OK if the argument of a function is taken in some cases,
170 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
171 for (param
= DECL_ARGUMENTS (current_function_decl
);
173 param
= DECL_CHAIN (param
))
174 if (TREE_ADDRESSABLE (param
))
180 /* Checks whether the expression EXPR in stmt AT is independent of the
181 statement pointed to by GSI (in a sense that we already know EXPR's value
182 at GSI). We use the fact that we are only called from the chain of
183 basic blocks that have only single successor. Returns the expression
184 containing the value of EXPR at GSI. */
187 independent_of_stmt_p (tree expr
, gimple
*at
, gimple_stmt_iterator gsi
,
190 basic_block bb
, call_bb
, at_bb
;
194 if (is_gimple_min_invariant (expr
))
197 if (TREE_CODE (expr
) != SSA_NAME
)
200 if (bitmap_bit_p (to_move
, SSA_NAME_VERSION (expr
)))
203 /* Mark the blocks in the chain leading to the end. */
204 at_bb
= gimple_bb (at
);
205 call_bb
= gimple_bb (gsi_stmt (gsi
));
206 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
212 at
= SSA_NAME_DEF_STMT (expr
);
215 /* The default definition or defined before the chain. */
221 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
222 if (gsi_stmt (gsi
) == at
)
225 if (!gsi_end_p (gsi
))
230 if (gimple_code (at
) != GIMPLE_PHI
)
236 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
241 expr
= PHI_ARG_DEF_FROM_EDGE (at
, e
);
242 if (TREE_CODE (expr
) != SSA_NAME
)
244 /* The value is a constant. */
249 /* Unmark the blocks. */
250 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
257 enum par
{ FAIL
, OK
, TRY_MOVE
};
259 /* Simulates the effect of an assignment STMT on the return value of the tail
260 recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
261 additive factor for the real return value. */
264 process_assignment (gassign
*stmt
,
265 gimple_stmt_iterator call
, tree
*m
,
266 tree
*a
, tree
*ass_var
, bitmap to_move
)
268 tree op0
, op1
= NULL_TREE
, non_ass_var
= NULL_TREE
;
269 tree dest
= gimple_assign_lhs (stmt
);
270 enum tree_code code
= gimple_assign_rhs_code (stmt
);
271 enum gimple_rhs_class rhs_class
= get_gimple_rhs_class (code
);
272 tree src_var
= gimple_assign_rhs1 (stmt
);
274 /* See if this is a simple copy operation of an SSA name to the function
275 result. In that case we may have a simple tail call. Ignore type
276 conversions that can never produce extra code between the function
277 call and the function return. */
278 if ((rhs_class
== GIMPLE_SINGLE_RHS
|| gimple_assign_cast_p (stmt
))
279 && src_var
== *ass_var
)
281 /* Reject a tailcall if the type conversion might need
283 if (gimple_assign_cast_p (stmt
))
285 if (TYPE_MODE (TREE_TYPE (dest
)) != TYPE_MODE (TREE_TYPE (src_var
)))
288 /* Even if the type modes are the same, if the precision of the
289 type is smaller than mode's precision,
290 reduce_to_bit_field_precision would generate additional code. */
291 if (INTEGRAL_TYPE_P (TREE_TYPE (dest
))
292 && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (dest
)))
293 > TYPE_PRECISION (TREE_TYPE (dest
))))
303 case GIMPLE_BINARY_RHS
:
304 op1
= gimple_assign_rhs2 (stmt
);
308 case GIMPLE_UNARY_RHS
:
309 op0
= gimple_assign_rhs1 (stmt
);
316 /* Accumulator optimizations will reverse the order of operations.
317 We can only do that for floating-point types if we're assuming
318 that addition and multiplication are associative. */
319 if (!flag_associative_math
)
320 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
323 if (rhs_class
== GIMPLE_UNARY_RHS
326 else if (op0
== *ass_var
327 && (non_ass_var
= independent_of_stmt_p (op1
, stmt
, call
,
330 else if (op1
== *ass_var
331 && (non_ass_var
= independent_of_stmt_p (op0
, stmt
, call
,
344 case POINTER_PLUS_EXPR
:
357 *m
= build_minus_one_cst (TREE_TYPE (op0
));
363 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
366 *m
= build_minus_one_cst (TREE_TYPE (non_ass_var
));
367 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
378 /* Propagate VAR through phis on edge E. */
381 propagate_through_phis (tree var
, edge e
)
383 basic_block dest
= e
->dest
;
386 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
388 gphi
*phi
= gsi
.phi ();
389 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
)
390 return PHI_RESULT (phi
);
395 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
396 added to the start of RET. */
399 find_tail_calls (basic_block bb
, struct tailcall
**ret
)
401 tree ass_var
= NULL_TREE
, ret_var
, func
, param
;
404 gimple_stmt_iterator gsi
, agsi
;
413 if (!single_succ_p (bb
))
416 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
418 stmt
= gsi_stmt (gsi
);
420 /* Ignore labels, returns, nops, clobbers and debug stmts. */
421 if (gimple_code (stmt
) == GIMPLE_LABEL
422 || gimple_code (stmt
) == GIMPLE_RETURN
423 || gimple_code (stmt
) == GIMPLE_NOP
424 || gimple_code (stmt
) == GIMPLE_PREDICT
425 || gimple_clobber_p (stmt
)
426 || is_gimple_debug (stmt
))
429 /* Check for a call. */
430 if (is_gimple_call (stmt
))
432 call
= as_a
<gcall
*> (stmt
);
433 ass_var
= gimple_call_lhs (call
);
437 /* Allow simple copies between local variables, even if they're
439 if (is_gimple_assign (stmt
)
440 && auto_var_in_fn_p (gimple_assign_lhs (stmt
), cfun
->decl
)
441 && auto_var_in_fn_p (gimple_assign_rhs1 (stmt
), cfun
->decl
))
444 /* If the statement references memory or volatile operands, fail. */
445 if (gimple_references_memory_p (stmt
)
446 || gimple_has_volatile_ops (stmt
))
453 /* Recurse to the predecessors. */
454 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
455 find_tail_calls (e
->src
, ret
);
460 /* If the LHS of our call is not just a simple register or local
461 variable, we can't transform this into a tail or sibling call.
462 This situation happens, in (e.g.) "*p = foo()" where foo returns a
463 struct. In this case we won't have a temporary here, but we need
464 to carry out the side effect anyway, so tailcall is impossible.
466 ??? In some situations (when the struct is returned in memory via
467 invisible argument) we could deal with this, e.g. by passing 'p'
468 itself as that argument to foo, but it's too early to do this here,
469 and expand_call() will not handle it anyway. If it ever can, then
470 we need to revisit this here, to allow that situation. */
472 && !is_gimple_reg (ass_var
)
473 && !auto_var_in_fn_p (ass_var
, cfun
->decl
))
476 /* We found the call, check whether it is suitable. */
477 tail_recursion
= false;
478 func
= gimple_call_fndecl (call
);
480 && !DECL_BUILT_IN (func
)
481 && recursive_call_p (current_function_decl
, func
))
485 for (param
= DECL_ARGUMENTS (func
), idx
= 0;
486 param
&& idx
< gimple_call_num_args (call
);
487 param
= DECL_CHAIN (param
), idx
++)
489 arg
= gimple_call_arg (call
, idx
);
492 /* Make sure there are no problems with copying. The parameter
493 have a copyable type and the two arguments must have reasonably
494 equivalent types. The latter requirement could be relaxed if
495 we emitted a suitable type conversion statement. */
496 if (!is_gimple_reg_type (TREE_TYPE (param
))
497 || !useless_type_conversion_p (TREE_TYPE (param
),
501 /* The parameter should be a real operand, so that phi node
502 created for it at the start of the function has the meaning
503 of copying the value. This test implies is_gimple_reg_type
504 from the previous condition, however this one could be
505 relaxed by being more careful with copying the new value
506 of the parameter (emitting appropriate GIMPLE_ASSIGN and
507 updating the virtual operands). */
508 if (!is_gimple_reg (param
))
512 if (idx
== gimple_call_num_args (call
) && !param
)
513 tail_recursion
= true;
516 /* Make sure the tail invocation of this function does not indirectly
517 refer to local variables. (Passing variables directly by value
519 FOR_EACH_LOCAL_DECL (cfun
, idx
, var
)
521 if (TREE_CODE (var
) != PARM_DECL
522 && auto_var_in_fn_p (var
, cfun
->decl
)
523 && may_be_aliased (var
)
524 && (ref_maybe_used_by_stmt_p (call
, var
)
525 || call_may_clobber_ref_p (call
, var
)))
529 /* Now check the statements after the call. None of them has virtual
530 operands, so they may only depend on the call through its return
531 value. The return value should also be dependent on each of them,
532 since we are running after dce. */
535 auto_bitmap to_move_defs
;
536 auto_vec
<gimple
*> to_move_stmts
;
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
);
554 if (gimple_code (stmt
) == GIMPLE_RETURN
)
557 if (gimple_code (stmt
) == GIMPLE_LABEL
558 || gimple_code (stmt
) == GIMPLE_NOP
559 || gimple_code (stmt
) == GIMPLE_PREDICT
560 || gimple_clobber_p (stmt
)
561 || is_gimple_debug (stmt
))
564 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
567 /* This is a gimple assign. */
568 par ret
= process_assignment (as_a
<gassign
*> (stmt
), gsi
,
569 &tmp_m
, &tmp_a
, &ass_var
, to_move_defs
);
572 else if (ret
== TRY_MOVE
)
574 if (! tail_recursion
)
576 /* Do not deal with checking dominance, the real fix is to
577 do path isolation for the transform phase anyway, removing
578 the need to compute the accumulators with new stmts. */
581 for (unsigned opno
= 1; opno
< gimple_num_ops (stmt
); ++opno
)
583 tree op
= gimple_op (stmt
, opno
);
584 if (independent_of_stmt_p (op
, stmt
, gsi
, to_move_defs
) != op
)
587 bitmap_set_bit (to_move_defs
,
588 SSA_NAME_VERSION (gimple_assign_lhs (stmt
)));
589 to_move_stmts
.safe_push (stmt
);
595 tree type
= TREE_TYPE (tmp_a
);
597 a
= fold_build2 (PLUS_EXPR
, type
, fold_convert (type
, a
), tmp_a
);
603 tree type
= TREE_TYPE (tmp_m
);
605 m
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, m
), tmp_m
);
610 a
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, a
), tmp_m
);
614 /* See if this is a tail call we can handle. */
615 ret_var
= gimple_return_retval (as_a
<greturn
*> (stmt
));
617 /* We may proceed if there either is no return value, or the return value
618 is identical to the call's return. */
620 && (ret_var
!= ass_var
))
623 /* If this is not a tail recursive call, we cannot handle addends or
625 if (!tail_recursion
&& (m
|| a
))
628 /* For pointers only allow additions. */
629 if (m
&& POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
632 /* Move queued defs. */
636 FOR_EACH_VEC_ELT (to_move_stmts
, i
, stmt
)
638 gimple_stmt_iterator mgsi
= gsi_for_stmt (stmt
);
639 gsi_move_before (&mgsi
, &gsi
);
643 nw
= XNEW (struct tailcall
);
647 nw
->tail_recursion
= tail_recursion
;
656 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
659 add_successor_phi_arg (edge e
, tree var
, tree phi_arg
)
663 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
664 if (PHI_RESULT (gsi
.phi ()) == var
)
667 gcc_assert (!gsi_end_p (gsi
));
668 add_phi_arg (gsi
.phi (), phi_arg
, e
, UNKNOWN_LOCATION
);
671 /* Creates a GIMPLE statement which computes the operation specified by
672 CODE, ACC and OP1 to a new variable with name LABEL and inserts the
673 statement in the position specified by GSI. Returns the
674 tree node of the statement's result. */
677 adjust_return_value_with_ops (enum tree_code code
, const char *label
,
678 tree acc
, tree op1
, gimple_stmt_iterator gsi
)
681 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
682 tree result
= make_temp_ssa_name (ret_type
, NULL
, label
);
685 if (POINTER_TYPE_P (ret_type
))
687 gcc_assert (code
== PLUS_EXPR
&& TREE_TYPE (acc
) == sizetype
);
688 code
= POINTER_PLUS_EXPR
;
690 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
))
691 && code
!= POINTER_PLUS_EXPR
)
692 stmt
= gimple_build_assign (result
, code
, acc
, op1
);
696 if (code
== POINTER_PLUS_EXPR
)
697 tem
= fold_build2 (code
, TREE_TYPE (op1
), op1
, acc
);
699 tem
= fold_build2 (code
, TREE_TYPE (op1
),
700 fold_convert (TREE_TYPE (op1
), acc
), op1
);
701 tree rhs
= fold_convert (ret_type
, tem
);
702 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
703 false, NULL
, true, GSI_SAME_STMT
);
704 stmt
= gimple_build_assign (result
, rhs
);
707 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
711 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
712 the computation specified by CODE and OP1 and insert the statement
713 at the position specified by GSI as a new statement. Returns new SSA name
714 of updated accumulator. */
717 update_accumulator_with_ops (enum tree_code code
, tree acc
, tree op1
,
718 gimple_stmt_iterator gsi
)
721 tree var
= copy_ssa_name (acc
);
722 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
)))
723 stmt
= gimple_build_assign (var
, code
, acc
, op1
);
726 tree rhs
= fold_convert (TREE_TYPE (acc
),
729 fold_convert (TREE_TYPE (op1
), acc
),
731 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
732 false, NULL
, false, GSI_CONTINUE_LINKING
);
733 stmt
= gimple_build_assign (var
, rhs
);
735 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
739 /* Adjust the accumulator values according to A and M after GSI, and update
740 the phi nodes on edge BACK. */
743 adjust_accumulator_values (gimple_stmt_iterator gsi
, tree m
, tree a
, edge back
)
745 tree var
, a_acc_arg
, m_acc_arg
;
748 m
= force_gimple_operand_gsi (&gsi
, m
, true, NULL
, true, GSI_SAME_STMT
);
750 a
= force_gimple_operand_gsi (&gsi
, a
, true, NULL
, true, GSI_SAME_STMT
);
758 if (integer_onep (a
))
761 var
= adjust_return_value_with_ops (MULT_EXPR
, "acc_tmp", m_acc
,
767 a_acc_arg
= update_accumulator_with_ops (PLUS_EXPR
, a_acc
, var
, gsi
);
771 m_acc_arg
= update_accumulator_with_ops (MULT_EXPR
, m_acc
, m
, gsi
);
774 add_successor_phi_arg (back
, a_acc
, a_acc_arg
);
777 add_successor_phi_arg (back
, m_acc
, m_acc_arg
);
780 /* Adjust value of the return at the end of BB according to M and A
784 adjust_return_value (basic_block bb
, tree m
, tree a
)
787 greturn
*ret_stmt
= as_a
<greturn
*> (gimple_seq_last_stmt (bb_seq (bb
)));
788 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
790 gcc_assert (gimple_code (ret_stmt
) == GIMPLE_RETURN
);
792 retval
= gimple_return_retval (ret_stmt
);
793 if (!retval
|| retval
== error_mark_node
)
797 retval
= adjust_return_value_with_ops (MULT_EXPR
, "mul_tmp", m_acc
, retval
,
800 retval
= adjust_return_value_with_ops (PLUS_EXPR
, "acc_tmp", a_acc
, retval
,
802 gimple_return_set_retval (ret_stmt
, retval
);
803 update_stmt (ret_stmt
);
806 /* Subtract COUNT and FREQUENCY from the basic block and it's
809 decrease_profile (basic_block bb
, profile_count count
, int frequency
)
812 bb
->count
= bb
->count
- count
;
813 bb
->frequency
-= frequency
;
814 if (bb
->frequency
< 0)
816 if (!single_succ_p (bb
))
818 gcc_assert (!EDGE_COUNT (bb
->succs
));
821 e
= single_succ_edge (bb
);
825 /* Returns true if argument PARAM of the tail recursive call needs to be copied
826 when the call is eliminated. */
829 arg_needs_copy_p (tree param
)
833 if (!is_gimple_reg (param
))
836 /* Parameters that are only defined but never used need not be copied. */
837 def
= ssa_default_def (cfun
, param
);
844 /* Eliminates tail call described by T. TMP_VARS is a list of
845 temporary variables used to copy the function arguments. */
848 eliminate_tail_call (struct tailcall
*t
)
854 basic_block bb
, first
;
858 gimple_stmt_iterator gsi
;
861 stmt
= orig_stmt
= gsi_stmt (t
->call_gsi
);
862 bb
= gsi_bb (t
->call_gsi
);
864 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
866 fprintf (dump_file
, "Eliminated tail recursion in bb %d : ",
868 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
869 fprintf (dump_file
, "\n");
872 gcc_assert (is_gimple_call (stmt
));
874 first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
876 /* Remove the code after call_gsi that will become unreachable. The
877 possibly unreachable code in other blocks is removed later in
880 gimple_stmt_iterator gsi2
= gsi_last_bb (gimple_bb (gsi_stmt (gsi
)));
881 while (gsi_stmt (gsi2
) != gsi_stmt (gsi
))
883 gimple
*t
= gsi_stmt (gsi2
);
884 /* Do not remove the return statement, so that redirect_edge_and_branch
885 sees how the block ends. */
886 if (gimple_code (t
) != GIMPLE_RETURN
)
888 gimple_stmt_iterator gsi3
= gsi2
;
890 gsi_remove (&gsi3
, true);
897 /* Number of executions of function has reduced by the tailcall. */
898 e
= single_succ_edge (gsi_bb (t
->call_gsi
));
899 decrease_profile (EXIT_BLOCK_PTR_FOR_FN (cfun
), e
->count
, EDGE_FREQUENCY (e
));
900 decrease_profile (ENTRY_BLOCK_PTR_FOR_FN (cfun
), e
->count
,
902 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
903 decrease_profile (e
->dest
, e
->count
, EDGE_FREQUENCY (e
));
905 /* Replace the call by a jump to the start of function. */
906 e
= redirect_edge_and_branch (single_succ_edge (gsi_bb (t
->call_gsi
)),
909 PENDING_STMT (e
) = NULL
;
911 /* Add phi node entries for arguments. The ordering of the phi nodes should
912 be the same as the ordering of the arguments. */
913 for (param
= DECL_ARGUMENTS (current_function_decl
),
914 idx
= 0, gpi
= gsi_start_phis (first
);
916 param
= DECL_CHAIN (param
), idx
++)
918 if (!arg_needs_copy_p (param
))
921 arg
= gimple_call_arg (stmt
, idx
);
923 gcc_assert (param
== SSA_NAME_VAR (PHI_RESULT (phi
)));
925 add_phi_arg (phi
, arg
, e
, gimple_location (stmt
));
929 /* Update the values of accumulators. */
930 adjust_accumulator_values (t
->call_gsi
, t
->mult
, t
->add
, e
);
932 call
= gsi_stmt (t
->call_gsi
);
933 rslt
= gimple_call_lhs (call
);
934 if (rslt
!= NULL_TREE
&& TREE_CODE (rslt
) == SSA_NAME
)
936 /* Result of the call will no longer be defined. So adjust the
937 SSA_NAME_DEF_STMT accordingly. */
938 SSA_NAME_DEF_STMT (rslt
) = gimple_build_nop ();
941 gsi_remove (&t
->call_gsi
, true);
945 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
946 mark the tailcalls for the sibcall optimization. */
949 optimize_tail_call (struct tailcall
*t
, bool opt_tailcalls
)
951 if (t
->tail_recursion
)
953 eliminate_tail_call (t
);
959 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (t
->call_gsi
));
961 gimple_call_set_tail (stmt
, true);
962 cfun
->tail_call_marked
= true;
963 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
965 fprintf (dump_file
, "Found tail call ");
966 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
967 fprintf (dump_file
, " in bb %i\n", (gsi_bb (t
->call_gsi
))->index
);
974 /* Creates a tail-call accumulator of the same type as the return type of the
975 current function. LABEL is the name used to creating the temporary
976 variable for the accumulator. The accumulator will be inserted in the
977 phis of a basic block BB with single predecessor with an initial value
978 INIT converted to the current function return type. */
981 create_tailcall_accumulator (const char *label
, basic_block bb
, tree init
)
983 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
984 if (POINTER_TYPE_P (ret_type
))
987 tree tmp
= make_temp_ssa_name (ret_type
, NULL
, label
);
990 phi
= create_phi_node (tmp
, bb
);
991 /* RET_TYPE can be a float when -ffast-maths is enabled. */
992 add_phi_arg (phi
, fold_convert (ret_type
, init
), single_pred_edge (bb
),
994 return PHI_RESULT (phi
);
997 /* Optimizes tail calls in the function, turning the tail recursion
1001 tree_optimize_tail_calls_1 (bool opt_tailcalls
)
1004 bool phis_constructed
= false;
1005 struct tailcall
*tailcalls
= NULL
, *act
, *next
;
1006 bool changed
= false;
1007 basic_block first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1012 if (!suitable_for_tail_opt_p ())
1015 opt_tailcalls
= suitable_for_tail_call_opt_p ();
1017 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1019 /* Only traverse the normal exits, i.e. those that end with return
1021 stmt
= last_stmt (e
->src
);
1024 && gimple_code (stmt
) == GIMPLE_RETURN
)
1025 find_tail_calls (e
->src
, &tailcalls
);
1028 /* Construct the phi nodes and accumulators if necessary. */
1029 a_acc
= m_acc
= NULL_TREE
;
1030 for (act
= tailcalls
; act
; act
= act
->next
)
1032 if (!act
->tail_recursion
)
1035 if (!phis_constructed
)
1037 /* Ensure that there is only one predecessor of the block
1038 or if there are existing degenerate PHI nodes. */
1039 if (!single_pred_p (first
)
1040 || !gimple_seq_empty_p (phi_nodes (first
)))
1042 split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1044 /* Copy the args if needed. */
1045 for (param
= DECL_ARGUMENTS (current_function_decl
);
1047 param
= DECL_CHAIN (param
))
1048 if (arg_needs_copy_p (param
))
1050 tree name
= ssa_default_def (cfun
, param
);
1051 tree new_name
= make_ssa_name (param
, SSA_NAME_DEF_STMT (name
));
1054 set_ssa_default_def (cfun
, param
, new_name
);
1055 phi
= create_phi_node (name
, first
);
1056 add_phi_arg (phi
, new_name
, single_pred_edge (first
),
1057 EXPR_LOCATION (param
));
1059 phis_constructed
= true;
1062 if (act
->add
&& !a_acc
)
1063 a_acc
= create_tailcall_accumulator ("add_acc", first
,
1066 if (act
->mult
&& !m_acc
)
1067 m_acc
= create_tailcall_accumulator ("mult_acc", first
,
1073 /* When the tail call elimination using accumulators is performed,
1074 statements adding the accumulated value are inserted at all exits.
1075 This turns all other tail calls to non-tail ones. */
1076 opt_tailcalls
= false;
1079 for (; tailcalls
; tailcalls
= next
)
1081 next
= tailcalls
->next
;
1082 changed
|= optimize_tail_call (tailcalls
, opt_tailcalls
);
1088 /* Modify the remaining return statements. */
1089 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1091 stmt
= last_stmt (e
->src
);
1094 && gimple_code (stmt
) == GIMPLE_RETURN
)
1095 adjust_return_value (e
->src
, m_acc
, a_acc
);
1101 /* We may have created new loops. Make them magically appear. */
1102 loops_state_set (LOOPS_NEED_FIXUP
);
1103 free_dominance_info (CDI_DOMINATORS
);
1106 /* Add phi nodes for the virtual operands defined in the function to the
1107 header of the loop created by tail recursion elimination. Do so
1108 by triggering the SSA renamer. */
1109 if (phis_constructed
)
1110 mark_virtual_operands_for_renaming (cfun
);
1113 return TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
1118 gate_tail_calls (void)
1120 return flag_optimize_sibling_calls
!= 0 && dbg_cnt (tail_call
);
1124 execute_tail_calls (void)
1126 return tree_optimize_tail_calls_1 (true);
1131 const pass_data pass_data_tail_recursion
=
1133 GIMPLE_PASS
, /* type */
1135 OPTGROUP_NONE
, /* optinfo_flags */
1136 TV_NONE
, /* tv_id */
1137 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1138 0, /* properties_provided */
1139 0, /* properties_destroyed */
1140 0, /* todo_flags_start */
1141 0, /* todo_flags_finish */
1144 class pass_tail_recursion
: public gimple_opt_pass
1147 pass_tail_recursion (gcc::context
*ctxt
)
1148 : gimple_opt_pass (pass_data_tail_recursion
, ctxt
)
1151 /* opt_pass methods: */
1152 opt_pass
* clone () { return new pass_tail_recursion (m_ctxt
); }
1153 virtual bool gate (function
*) { return gate_tail_calls (); }
1154 virtual unsigned int execute (function
*)
1156 return tree_optimize_tail_calls_1 (false);
1159 }; // class pass_tail_recursion
1164 make_pass_tail_recursion (gcc::context
*ctxt
)
1166 return new pass_tail_recursion (ctxt
);
1171 const pass_data pass_data_tail_calls
=
1173 GIMPLE_PASS
, /* type */
1175 OPTGROUP_NONE
, /* optinfo_flags */
1176 TV_NONE
, /* tv_id */
1177 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1178 0, /* properties_provided */
1179 0, /* properties_destroyed */
1180 0, /* todo_flags_start */
1181 0, /* todo_flags_finish */
1184 class pass_tail_calls
: public gimple_opt_pass
1187 pass_tail_calls (gcc::context
*ctxt
)
1188 : gimple_opt_pass (pass_data_tail_calls
, ctxt
)
1191 /* opt_pass methods: */
1192 virtual bool gate (function
*) { return gate_tail_calls (); }
1193 virtual unsigned int execute (function
*) { return execute_tail_calls (); }
1195 }; // class pass_tail_calls
1200 make_pass_tail_calls (gcc::context
*ctxt
)
1202 return new pass_tail_calls (ctxt
);