1 /* Tail call optimization on trees.
2 Copyright (C) 2003-2015 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"
31 #include "fold-const.h"
32 #include "stor-layout.h"
35 #include "hard-reg-set.h"
37 #include "dominance.h"
39 #include "basic-block.h"
40 #include "tree-ssa-alias.h"
41 #include "internal-fn.h"
42 #include "gimple-expr.h"
45 #include "gimple-iterator.h"
46 #include "gimplify-me.h"
47 #include "gimple-ssa.h"
49 #include "tree-phinodes.h"
50 #include "stringpool.h"
51 #include "tree-ssanames.h"
52 #include "tree-into-ssa.h"
56 #include "statistics.h"
57 #include "insn-config.h"
67 #include "gimple-pretty-print.h"
69 #include "tree-pass.h"
70 #include "langhooks.h"
74 #include "common/common-target.h"
76 #include "plugin-api.h"
79 #include "ipa-utils.h"
81 /* The file implements the tail recursion elimination. It is also used to
82 analyze the tail calls in general, passing the results to the rtl level
83 where they are used for sibcall optimization.
85 In addition to the standard tail recursion elimination, we handle the most
86 trivial cases of making the call tail recursive by creating accumulators.
87 For example the following function
92 return n + sum (n - 1);
109 To do this, we maintain two accumulators (a_acc and m_acc) that indicate
110 when we reach the return x statement, we should return a_acc + x * m_acc
111 instead. They are initially initialized to 0 and 1, respectively,
112 so the semantics of the function is obviously preserved. If we are
113 guaranteed that the value of the accumulator never change, we
114 omit the accumulator.
116 There are three cases how the function may exit. The first one is
117 handled in adjust_return_value, the other two in adjust_accumulator_values
118 (the second case is actually a special case of the third one and we
119 present it separately just for clarity):
121 1) Just return x, where x is not in any of the remaining special shapes.
122 We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
124 2) return f (...), where f is the current function, is rewritten in a
125 classical tail-recursion elimination way, into assignment of arguments
126 and jump to the start of the function. Values of the accumulators
129 3) return a + m * f(...), where a and m do not depend on call to f.
130 To preserve the semantics described before we want this to be rewritten
131 in such a way that we finally return
133 a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
135 I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
136 eliminate the tail call to f. Special cases when the value is just
137 added or just multiplied are obtained by setting a = 0 or m = 1.
139 TODO -- it is possible to do similar tricks for other operations. */
141 /* A structure that describes the tailcall. */
145 /* The iterator pointing to the call statement. */
146 gimple_stmt_iterator call_gsi
;
148 /* True if it is a call to the current function. */
151 /* The return value of the caller is mult * f + add, where f is the return
152 value of the call. */
155 /* Next tailcall in the chain. */
156 struct tailcall
*next
;
159 /* The variables holding the value of multiplicative and additive
161 static tree m_acc
, a_acc
;
163 static bool optimize_tail_call (struct tailcall
*, bool);
164 static void eliminate_tail_call (struct tailcall
*);
166 /* Returns false when the function is not suitable for tail call optimization
167 from some reason (e.g. if it takes variable number of arguments). */
170 suitable_for_tail_opt_p (void)
177 /* Returns false when the function is not suitable for tail call optimization
178 for some reason (e.g. if it takes variable number of arguments).
179 This test must pass in addition to suitable_for_tail_opt_p in order to make
180 tail call discovery happen. */
183 suitable_for_tail_call_opt_p (void)
187 /* alloca (until we have stack slot life analysis) inhibits
188 sibling call optimizations, but not tail recursion. */
189 if (cfun
->calls_alloca
)
192 /* If we are using sjlj exceptions, we may need to add a call to
193 _Unwind_SjLj_Unregister at exit of the function. Which means
194 that we cannot do any sibcall transformations. */
195 if (targetm_common
.except_unwind_info (&global_options
) == UI_SJLJ
196 && current_function_has_exception_handlers ())
199 /* Any function that calls setjmp might have longjmp called from
200 any called function. ??? We really should represent this
201 properly in the CFG so that this needn't be special cased. */
202 if (cfun
->calls_setjmp
)
205 /* ??? It is OK if the argument of a function is taken in some cases,
206 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
207 for (param
= DECL_ARGUMENTS (current_function_decl
);
209 param
= DECL_CHAIN (param
))
210 if (TREE_ADDRESSABLE (param
))
216 /* Checks whether the expression EXPR in stmt AT is independent of the
217 statement pointed to by GSI (in a sense that we already know EXPR's value
218 at GSI). We use the fact that we are only called from the chain of
219 basic blocks that have only single successor. Returns the expression
220 containing the value of EXPR at GSI. */
223 independent_of_stmt_p (tree expr
, gimple at
, gimple_stmt_iterator gsi
)
225 basic_block bb
, call_bb
, at_bb
;
229 if (is_gimple_min_invariant (expr
))
232 if (TREE_CODE (expr
) != SSA_NAME
)
235 /* Mark the blocks in the chain leading to the end. */
236 at_bb
= gimple_bb (at
);
237 call_bb
= gimple_bb (gsi_stmt (gsi
));
238 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
244 at
= SSA_NAME_DEF_STMT (expr
);
247 /* The default definition or defined before the chain. */
253 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
254 if (gsi_stmt (gsi
) == at
)
257 if (!gsi_end_p (gsi
))
262 if (gimple_code (at
) != GIMPLE_PHI
)
268 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
273 expr
= PHI_ARG_DEF_FROM_EDGE (at
, e
);
274 if (TREE_CODE (expr
) != SSA_NAME
)
276 /* The value is a constant. */
281 /* Unmark the blocks. */
282 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
289 /* Simulates the effect of an assignment STMT on the return value of the tail
290 recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
291 additive factor for the real return value. */
294 process_assignment (gassign
*stmt
, gimple_stmt_iterator call
, tree
*m
,
295 tree
*a
, tree
*ass_var
)
297 tree op0
, op1
= NULL_TREE
, non_ass_var
= NULL_TREE
;
298 tree dest
= gimple_assign_lhs (stmt
);
299 enum tree_code code
= gimple_assign_rhs_code (stmt
);
300 enum gimple_rhs_class rhs_class
= get_gimple_rhs_class (code
);
301 tree src_var
= gimple_assign_rhs1 (stmt
);
303 /* See if this is a simple copy operation of an SSA name to the function
304 result. In that case we may have a simple tail call. Ignore type
305 conversions that can never produce extra code between the function
306 call and the function return. */
307 if ((rhs_class
== GIMPLE_SINGLE_RHS
|| gimple_assign_cast_p (stmt
))
308 && (TREE_CODE (src_var
) == SSA_NAME
))
310 /* Reject a tailcall if the type conversion might need
312 if (gimple_assign_cast_p (stmt
))
314 if (TYPE_MODE (TREE_TYPE (dest
)) != TYPE_MODE (TREE_TYPE (src_var
)))
317 /* Even if the type modes are the same, if the precision of the
318 type is smaller than mode's precision,
319 reduce_to_bit_field_precision would generate additional code. */
320 if (INTEGRAL_TYPE_P (TREE_TYPE (dest
))
321 && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (dest
)))
322 > TYPE_PRECISION (TREE_TYPE (dest
))))
326 if (src_var
!= *ass_var
)
335 case GIMPLE_BINARY_RHS
:
336 op1
= gimple_assign_rhs2 (stmt
);
340 case GIMPLE_UNARY_RHS
:
341 op0
= gimple_assign_rhs1 (stmt
);
348 /* Accumulator optimizations will reverse the order of operations.
349 We can only do that for floating-point types if we're assuming
350 that addition and multiplication are associative. */
351 if (!flag_associative_math
)
352 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
355 if (rhs_class
== GIMPLE_UNARY_RHS
)
357 else if (op0
== *ass_var
358 && (non_ass_var
= independent_of_stmt_p (op1
, stmt
, call
)))
360 else if (op1
== *ass_var
361 && (non_ass_var
= independent_of_stmt_p (op0
, stmt
, call
)))
373 case POINTER_PLUS_EXPR
:
386 *m
= build_minus_one_cst (TREE_TYPE (op0
));
392 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
395 *m
= build_minus_one_cst (TREE_TYPE (non_ass_var
));
396 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
402 /* TODO -- Handle POINTER_PLUS_EXPR. */
409 /* Propagate VAR through phis on edge E. */
412 propagate_through_phis (tree var
, edge e
)
414 basic_block dest
= e
->dest
;
417 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
419 gphi
*phi
= gsi
.phi ();
420 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
)
421 return PHI_RESULT (phi
);
426 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
427 added to the start of RET. */
430 find_tail_calls (basic_block bb
, struct tailcall
**ret
)
432 tree ass_var
= NULL_TREE
, ret_var
, func
, param
;
435 gimple_stmt_iterator gsi
, agsi
;
444 if (!single_succ_p (bb
))
447 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
449 stmt
= gsi_stmt (gsi
);
451 /* Ignore labels, returns, clobbers and debug stmts. */
452 if (gimple_code (stmt
) == GIMPLE_LABEL
453 || gimple_code (stmt
) == GIMPLE_RETURN
454 || gimple_clobber_p (stmt
)
455 || is_gimple_debug (stmt
))
458 /* Check for a call. */
459 if (is_gimple_call (stmt
))
461 call
= as_a
<gcall
*> (stmt
);
462 ass_var
= gimple_call_lhs (call
);
466 /* If the statement references memory or volatile operands, fail. */
467 if (gimple_references_memory_p (stmt
)
468 || gimple_has_volatile_ops (stmt
))
475 /* Recurse to the predecessors. */
476 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
477 find_tail_calls (e
->src
, ret
);
482 /* If the LHS of our call is not just a simple register, we can't
483 transform this into a tail or sibling call. This situation happens,
484 in (e.g.) "*p = foo()" where foo returns a struct. In this case
485 we won't have a temporary here, but we need to carry out the side
486 effect anyway, so tailcall is impossible.
488 ??? In some situations (when the struct is returned in memory via
489 invisible argument) we could deal with this, e.g. by passing 'p'
490 itself as that argument to foo, but it's too early to do this here,
491 and expand_call() will not handle it anyway. If it ever can, then
492 we need to revisit this here, to allow that situation. */
493 if (ass_var
&& !is_gimple_reg (ass_var
))
496 /* We found the call, check whether it is suitable. */
497 tail_recursion
= false;
498 func
= gimple_call_fndecl (call
);
500 && !DECL_BUILT_IN (func
)
501 && recursive_call_p (current_function_decl
, func
))
505 for (param
= DECL_ARGUMENTS (func
), idx
= 0;
506 param
&& idx
< gimple_call_num_args (call
);
507 param
= DECL_CHAIN (param
), idx
++)
509 arg
= gimple_call_arg (call
, idx
);
512 /* Make sure there are no problems with copying. The parameter
513 have a copyable type and the two arguments must have reasonably
514 equivalent types. The latter requirement could be relaxed if
515 we emitted a suitable type conversion statement. */
516 if (!is_gimple_reg_type (TREE_TYPE (param
))
517 || !useless_type_conversion_p (TREE_TYPE (param
),
521 /* The parameter should be a real operand, so that phi node
522 created for it at the start of the function has the meaning
523 of copying the value. This test implies is_gimple_reg_type
524 from the previous condition, however this one could be
525 relaxed by being more careful with copying the new value
526 of the parameter (emitting appropriate GIMPLE_ASSIGN and
527 updating the virtual operands). */
528 if (!is_gimple_reg (param
))
532 if (idx
== gimple_call_num_args (call
) && !param
)
533 tail_recursion
= true;
536 /* Make sure the tail invocation of this function does not refer
537 to local variables. */
538 FOR_EACH_LOCAL_DECL (cfun
, idx
, var
)
540 if (TREE_CODE (var
) != PARM_DECL
541 && auto_var_in_fn_p (var
, cfun
->decl
)
542 && (ref_maybe_used_by_stmt_p (call
, var
)
543 || call_may_clobber_ref_p (call
, var
)))
547 /* Now check the statements after the call. None of them has virtual
548 operands, so they may only depend on the call through its return
549 value. The return value should also be dependent on each of them,
550 since we are running after dce. */
558 tree tmp_a
= NULL_TREE
;
559 tree tmp_m
= NULL_TREE
;
562 while (gsi_end_p (agsi
))
564 ass_var
= propagate_through_phis (ass_var
, single_succ_edge (abb
));
565 abb
= single_succ (abb
);
566 agsi
= gsi_start_bb (abb
);
569 stmt
= gsi_stmt (agsi
);
571 if (gimple_code (stmt
) == GIMPLE_LABEL
)
574 if (gimple_code (stmt
) == GIMPLE_RETURN
)
577 if (gimple_clobber_p (stmt
))
580 if (is_gimple_debug (stmt
))
583 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
586 /* This is a gimple assign. */
587 if (! process_assignment (as_a
<gassign
*> (stmt
), gsi
, &tmp_m
,
593 tree type
= TREE_TYPE (tmp_a
);
595 a
= fold_build2 (PLUS_EXPR
, type
, fold_convert (type
, a
), tmp_a
);
601 tree type
= TREE_TYPE (tmp_m
);
603 m
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, m
), tmp_m
);
608 a
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, a
), tmp_m
);
612 /* See if this is a tail call we can handle. */
613 ret_var
= gimple_return_retval (as_a
<greturn
*> (stmt
));
615 /* We may proceed if there either is no return value, or the return value
616 is identical to the call's return. */
618 && (ret_var
!= ass_var
))
621 /* If this is not a tail recursive call, we cannot handle addends or
623 if (!tail_recursion
&& (m
|| a
))
626 /* For pointers only allow additions. */
627 if (m
&& POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
630 nw
= XNEW (struct tailcall
);
634 nw
->tail_recursion
= tail_recursion
;
643 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
646 add_successor_phi_arg (edge e
, tree var
, tree phi_arg
)
650 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
651 if (PHI_RESULT (gsi
.phi ()) == var
)
654 gcc_assert (!gsi_end_p (gsi
));
655 add_phi_arg (gsi
.phi (), phi_arg
, e
, UNKNOWN_LOCATION
);
658 /* Creates a GIMPLE statement which computes the operation specified by
659 CODE, ACC and OP1 to a new variable with name LABEL and inserts the
660 statement in the position specified by GSI. Returns the
661 tree node of the statement's result. */
664 adjust_return_value_with_ops (enum tree_code code
, const char *label
,
665 tree acc
, tree op1
, gimple_stmt_iterator gsi
)
668 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
669 tree result
= make_temp_ssa_name (ret_type
, NULL
, label
);
672 if (POINTER_TYPE_P (ret_type
))
674 gcc_assert (code
== PLUS_EXPR
&& TREE_TYPE (acc
) == sizetype
);
675 code
= POINTER_PLUS_EXPR
;
677 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
))
678 && code
!= POINTER_PLUS_EXPR
)
679 stmt
= gimple_build_assign (result
, code
, acc
, op1
);
683 if (code
== POINTER_PLUS_EXPR
)
684 tem
= fold_build2 (code
, TREE_TYPE (op1
), op1
, acc
);
686 tem
= fold_build2 (code
, TREE_TYPE (op1
),
687 fold_convert (TREE_TYPE (op1
), acc
), op1
);
688 tree rhs
= fold_convert (ret_type
, tem
);
689 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
690 false, NULL
, true, GSI_SAME_STMT
);
691 stmt
= gimple_build_assign (result
, rhs
);
694 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
698 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
699 the computation specified by CODE and OP1 and insert the statement
700 at the position specified by GSI as a new statement. Returns new SSA name
701 of updated accumulator. */
704 update_accumulator_with_ops (enum tree_code code
, tree acc
, tree op1
,
705 gimple_stmt_iterator gsi
)
708 tree var
= copy_ssa_name (acc
);
709 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
)))
710 stmt
= gimple_build_assign (var
, code
, acc
, op1
);
713 tree rhs
= fold_convert (TREE_TYPE (acc
),
716 fold_convert (TREE_TYPE (op1
), acc
),
718 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
719 false, NULL
, false, GSI_CONTINUE_LINKING
);
720 stmt
= gimple_build_assign (var
, rhs
);
722 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
726 /* Adjust the accumulator values according to A and M after GSI, and update
727 the phi nodes on edge BACK. */
730 adjust_accumulator_values (gimple_stmt_iterator gsi
, tree m
, tree a
, edge back
)
732 tree var
, a_acc_arg
, m_acc_arg
;
735 m
= force_gimple_operand_gsi (&gsi
, m
, true, NULL
, true, GSI_SAME_STMT
);
737 a
= force_gimple_operand_gsi (&gsi
, a
, true, NULL
, true, GSI_SAME_STMT
);
745 if (integer_onep (a
))
748 var
= adjust_return_value_with_ops (MULT_EXPR
, "acc_tmp", m_acc
,
754 a_acc_arg
= update_accumulator_with_ops (PLUS_EXPR
, a_acc
, var
, gsi
);
758 m_acc_arg
= update_accumulator_with_ops (MULT_EXPR
, m_acc
, m
, gsi
);
761 add_successor_phi_arg (back
, a_acc
, a_acc_arg
);
764 add_successor_phi_arg (back
, m_acc
, m_acc_arg
);
767 /* Adjust value of the return at the end of BB according to M and A
771 adjust_return_value (basic_block bb
, tree m
, tree a
)
774 greturn
*ret_stmt
= as_a
<greturn
*> (gimple_seq_last_stmt (bb_seq (bb
)));
775 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
777 gcc_assert (gimple_code (ret_stmt
) == GIMPLE_RETURN
);
779 retval
= gimple_return_retval (ret_stmt
);
780 if (!retval
|| retval
== error_mark_node
)
784 retval
= adjust_return_value_with_ops (MULT_EXPR
, "mul_tmp", m_acc
, retval
,
787 retval
= adjust_return_value_with_ops (PLUS_EXPR
, "acc_tmp", a_acc
, retval
,
789 gimple_return_set_retval (ret_stmt
, retval
);
790 update_stmt (ret_stmt
);
793 /* Subtract COUNT and FREQUENCY from the basic block and it's
796 decrease_profile (basic_block bb
, gcov_type count
, int frequency
)
802 bb
->frequency
-= frequency
;
803 if (bb
->frequency
< 0)
805 if (!single_succ_p (bb
))
807 gcc_assert (!EDGE_COUNT (bb
->succs
));
810 e
= single_succ_edge (bb
);
816 /* Returns true if argument PARAM of the tail recursive call needs to be copied
817 when the call is eliminated. */
820 arg_needs_copy_p (tree param
)
824 if (!is_gimple_reg (param
))
827 /* Parameters that are only defined but never used need not be copied. */
828 def
= ssa_default_def (cfun
, param
);
835 /* Eliminates tail call described by T. TMP_VARS is a list of
836 temporary variables used to copy the function arguments. */
839 eliminate_tail_call (struct tailcall
*t
)
845 basic_block bb
, first
;
849 gimple_stmt_iterator gsi
;
852 stmt
= orig_stmt
= gsi_stmt (t
->call_gsi
);
853 bb
= gsi_bb (t
->call_gsi
);
855 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
857 fprintf (dump_file
, "Eliminated tail recursion in bb %d : ",
859 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
860 fprintf (dump_file
, "\n");
863 gcc_assert (is_gimple_call (stmt
));
865 first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
867 /* Remove the code after call_gsi that will become unreachable. The
868 possibly unreachable code in other blocks is removed later in
872 while (!gsi_end_p (gsi
))
874 gimple t
= gsi_stmt (gsi
);
875 /* Do not remove the return statement, so that redirect_edge_and_branch
876 sees how the block ends. */
877 if (gimple_code (t
) == GIMPLE_RETURN
)
880 gsi_remove (&gsi
, true);
884 /* Number of executions of function has reduced by the tailcall. */
885 e
= single_succ_edge (gsi_bb (t
->call_gsi
));
886 decrease_profile (EXIT_BLOCK_PTR_FOR_FN (cfun
), e
->count
, EDGE_FREQUENCY (e
));
887 decrease_profile (ENTRY_BLOCK_PTR_FOR_FN (cfun
), e
->count
,
889 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
890 decrease_profile (e
->dest
, e
->count
, EDGE_FREQUENCY (e
));
892 /* Replace the call by a jump to the start of function. */
893 e
= redirect_edge_and_branch (single_succ_edge (gsi_bb (t
->call_gsi
)),
896 PENDING_STMT (e
) = NULL
;
898 /* Add phi node entries for arguments. The ordering of the phi nodes should
899 be the same as the ordering of the arguments. */
900 for (param
= DECL_ARGUMENTS (current_function_decl
),
901 idx
= 0, gpi
= gsi_start_phis (first
);
903 param
= DECL_CHAIN (param
), idx
++)
905 if (!arg_needs_copy_p (param
))
908 arg
= gimple_call_arg (stmt
, idx
);
910 gcc_assert (param
== SSA_NAME_VAR (PHI_RESULT (phi
)));
912 add_phi_arg (phi
, arg
, e
, gimple_location (stmt
));
916 /* Update the values of accumulators. */
917 adjust_accumulator_values (t
->call_gsi
, t
->mult
, t
->add
, e
);
919 call
= gsi_stmt (t
->call_gsi
);
920 rslt
= gimple_call_lhs (call
);
921 if (rslt
!= NULL_TREE
)
923 /* Result of the call will no longer be defined. So adjust the
924 SSA_NAME_DEF_STMT accordingly. */
925 SSA_NAME_DEF_STMT (rslt
) = gimple_build_nop ();
928 gsi_remove (&t
->call_gsi
, true);
932 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
933 mark the tailcalls for the sibcall optimization. */
936 optimize_tail_call (struct tailcall
*t
, bool opt_tailcalls
)
938 if (t
->tail_recursion
)
940 eliminate_tail_call (t
);
946 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (t
->call_gsi
));
948 gimple_call_set_tail (stmt
, true);
949 cfun
->tail_call_marked
= true;
950 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
952 fprintf (dump_file
, "Found tail call ");
953 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
954 fprintf (dump_file
, " in bb %i\n", (gsi_bb (t
->call_gsi
))->index
);
961 /* Creates a tail-call accumulator of the same type as the return type of the
962 current function. LABEL is the name used to creating the temporary
963 variable for the accumulator. The accumulator will be inserted in the
964 phis of a basic block BB with single predecessor with an initial value
965 INIT converted to the current function return type. */
968 create_tailcall_accumulator (const char *label
, basic_block bb
, tree init
)
970 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
971 if (POINTER_TYPE_P (ret_type
))
974 tree tmp
= make_temp_ssa_name (ret_type
, NULL
, label
);
977 phi
= create_phi_node (tmp
, bb
);
978 /* RET_TYPE can be a float when -ffast-maths is enabled. */
979 add_phi_arg (phi
, fold_convert (ret_type
, init
), single_pred_edge (bb
),
981 return PHI_RESULT (phi
);
984 /* Optimizes tail calls in the function, turning the tail recursion
988 tree_optimize_tail_calls_1 (bool opt_tailcalls
)
991 bool phis_constructed
= false;
992 struct tailcall
*tailcalls
= NULL
, *act
, *next
;
993 bool changed
= false;
994 basic_block first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
999 if (!suitable_for_tail_opt_p ())
1002 opt_tailcalls
= suitable_for_tail_call_opt_p ();
1004 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1006 /* Only traverse the normal exits, i.e. those that end with return
1008 stmt
= last_stmt (e
->src
);
1011 && gimple_code (stmt
) == GIMPLE_RETURN
)
1012 find_tail_calls (e
->src
, &tailcalls
);
1015 /* Construct the phi nodes and accumulators if necessary. */
1016 a_acc
= m_acc
= NULL_TREE
;
1017 for (act
= tailcalls
; act
; act
= act
->next
)
1019 if (!act
->tail_recursion
)
1022 if (!phis_constructed
)
1024 /* Ensure that there is only one predecessor of the block
1025 or if there are existing degenerate PHI nodes. */
1026 if (!single_pred_p (first
)
1027 || !gimple_seq_empty_p (phi_nodes (first
)))
1029 split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1031 /* Copy the args if needed. */
1032 for (param
= DECL_ARGUMENTS (current_function_decl
);
1034 param
= DECL_CHAIN (param
))
1035 if (arg_needs_copy_p (param
))
1037 tree name
= ssa_default_def (cfun
, param
);
1038 tree new_name
= make_ssa_name (param
, SSA_NAME_DEF_STMT (name
));
1041 set_ssa_default_def (cfun
, param
, new_name
);
1042 phi
= create_phi_node (name
, first
);
1043 add_phi_arg (phi
, new_name
, single_pred_edge (first
),
1044 EXPR_LOCATION (param
));
1046 phis_constructed
= true;
1049 if (act
->add
&& !a_acc
)
1050 a_acc
= create_tailcall_accumulator ("add_acc", first
,
1053 if (act
->mult
&& !m_acc
)
1054 m_acc
= create_tailcall_accumulator ("mult_acc", first
,
1060 /* When the tail call elimination using accumulators is performed,
1061 statements adding the accumulated value are inserted at all exits.
1062 This turns all other tail calls to non-tail ones. */
1063 opt_tailcalls
= false;
1066 for (; tailcalls
; tailcalls
= next
)
1068 next
= tailcalls
->next
;
1069 changed
|= optimize_tail_call (tailcalls
, opt_tailcalls
);
1075 /* Modify the remaining return statements. */
1076 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1078 stmt
= last_stmt (e
->src
);
1081 && gimple_code (stmt
) == GIMPLE_RETURN
)
1082 adjust_return_value (e
->src
, m_acc
, a_acc
);
1088 /* We may have created new loops. Make them magically appear. */
1089 loops_state_set (LOOPS_NEED_FIXUP
);
1090 free_dominance_info (CDI_DOMINATORS
);
1093 /* Add phi nodes for the virtual operands defined in the function to the
1094 header of the loop created by tail recursion elimination. Do so
1095 by triggering the SSA renamer. */
1096 if (phis_constructed
)
1097 mark_virtual_operands_for_renaming (cfun
);
1100 return TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
1105 gate_tail_calls (void)
1107 return flag_optimize_sibling_calls
!= 0 && dbg_cnt (tail_call
);
1111 execute_tail_calls (void)
1113 return tree_optimize_tail_calls_1 (true);
1118 const pass_data pass_data_tail_recursion
=
1120 GIMPLE_PASS
, /* type */
1122 OPTGROUP_NONE
, /* optinfo_flags */
1123 TV_NONE
, /* tv_id */
1124 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1125 0, /* properties_provided */
1126 0, /* properties_destroyed */
1127 0, /* todo_flags_start */
1128 0, /* todo_flags_finish */
1131 class pass_tail_recursion
: public gimple_opt_pass
1134 pass_tail_recursion (gcc::context
*ctxt
)
1135 : gimple_opt_pass (pass_data_tail_recursion
, ctxt
)
1138 /* opt_pass methods: */
1139 opt_pass
* clone () { return new pass_tail_recursion (m_ctxt
); }
1140 virtual bool gate (function
*) { return gate_tail_calls (); }
1141 virtual unsigned int execute (function
*)
1143 return tree_optimize_tail_calls_1 (false);
1146 }; // class pass_tail_recursion
1151 make_pass_tail_recursion (gcc::context
*ctxt
)
1153 return new pass_tail_recursion (ctxt
);
1158 const pass_data pass_data_tail_calls
=
1160 GIMPLE_PASS
, /* type */
1162 OPTGROUP_NONE
, /* optinfo_flags */
1163 TV_NONE
, /* tv_id */
1164 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1165 0, /* properties_provided */
1166 0, /* properties_destroyed */
1167 0, /* todo_flags_start */
1168 0, /* todo_flags_finish */
1171 class pass_tail_calls
: public gimple_opt_pass
1174 pass_tail_calls (gcc::context
*ctxt
)
1175 : gimple_opt_pass (pass_data_tail_calls
, ctxt
)
1178 /* opt_pass methods: */
1179 virtual bool gate (function
*) { return gate_tail_calls (); }
1180 virtual unsigned int execute (function
*) { return execute_tail_calls (); }
1182 }; // class pass_tail_calls
1187 make_pass_tail_calls (gcc::context
*ctxt
)
1189 return new pass_tail_calls (ctxt
);