1 /* Tail call optimization on trees.
2 Copyright (C) 2003-2013 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"
26 #include "basic-block.h"
28 #include "tree-flow.h"
29 #include "gimple-pretty-print.h"
31 #include "tree-pass.h"
33 #include "langhooks.h"
37 #include "common/common-target.h"
39 /* The file implements the tail recursion elimination. It is also used to
40 analyze the tail calls in general, passing the results to the rtl level
41 where they are used for sibcall optimization.
43 In addition to the standard tail recursion elimination, we handle the most
44 trivial cases of making the call tail recursive by creating accumulators.
45 For example the following function
50 return n + sum (n - 1);
67 To do this, we maintain two accumulators (a_acc and m_acc) that indicate
68 when we reach the return x statement, we should return a_acc + x * m_acc
69 instead. They are initially initialized to 0 and 1, respectively,
70 so the semantics of the function is obviously preserved. If we are
71 guaranteed that the value of the accumulator never change, we
74 There are three cases how the function may exit. The first one is
75 handled in adjust_return_value, the other two in adjust_accumulator_values
76 (the second case is actually a special case of the third one and we
77 present it separately just for clarity):
79 1) Just return x, where x is not in any of the remaining special shapes.
80 We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
82 2) return f (...), where f is the current function, is rewritten in a
83 classical tail-recursion elimination way, into assignment of arguments
84 and jump to the start of the function. Values of the accumulators
87 3) return a + m * f(...), where a and m do not depend on call to f.
88 To preserve the semantics described before we want this to be rewritten
89 in such a way that we finally return
91 a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
93 I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
94 eliminate the tail call to f. Special cases when the value is just
95 added or just multiplied are obtained by setting a = 0 or m = 1.
97 TODO -- it is possible to do similar tricks for other operations. */
99 /* A structure that describes the tailcall. */
103 /* The iterator pointing to the call statement. */
104 gimple_stmt_iterator call_gsi
;
106 /* True if it is a call to the current function. */
109 /* The return value of the caller is mult * f + add, where f is the return
110 value of the call. */
113 /* Next tailcall in the chain. */
114 struct tailcall
*next
;
117 /* The variables holding the value of multiplicative and additive
119 static tree m_acc
, a_acc
;
121 static bool suitable_for_tail_opt_p (void);
122 static bool optimize_tail_call (struct tailcall
*, bool);
123 static void eliminate_tail_call (struct tailcall
*);
124 static void find_tail_calls (basic_block
, struct tailcall
**);
126 /* Returns false when the function is not suitable for tail call optimization
127 from some reason (e.g. if it takes variable number of arguments). */
130 suitable_for_tail_opt_p (void)
137 /* Returns false when the function is not suitable for tail call optimization
138 from some reason (e.g. if it takes variable number of arguments).
139 This test must pass in addition to suitable_for_tail_opt_p in order to make
140 tail call discovery happen. */
143 suitable_for_tail_call_opt_p (void)
147 /* alloca (until we have stack slot life analysis) inhibits
148 sibling call optimizations, but not tail recursion. */
149 if (cfun
->calls_alloca
)
152 /* If we are using sjlj exceptions, we may need to add a call to
153 _Unwind_SjLj_Unregister at exit of the function. Which means
154 that we cannot do any sibcall transformations. */
155 if (targetm_common
.except_unwind_info (&global_options
) == UI_SJLJ
156 && current_function_has_exception_handlers ())
159 /* Any function that calls setjmp might have longjmp called from
160 any called function. ??? We really should represent this
161 properly in the CFG so that this needn't be special cased. */
162 if (cfun
->calls_setjmp
)
165 /* ??? It is OK if the argument of a function is taken in some cases,
166 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
167 for (param
= DECL_ARGUMENTS (current_function_decl
);
169 param
= DECL_CHAIN (param
))
170 if (TREE_ADDRESSABLE (param
))
176 /* Checks whether the expression EXPR in stmt AT is independent of the
177 statement pointed to by GSI (in a sense that we already know EXPR's value
178 at GSI). We use the fact that we are only called from the chain of
179 basic blocks that have only single successor. Returns the expression
180 containing the value of EXPR at GSI. */
183 independent_of_stmt_p (tree expr
, gimple at
, gimple_stmt_iterator gsi
)
185 basic_block bb
, call_bb
, at_bb
;
189 if (is_gimple_min_invariant (expr
))
192 if (TREE_CODE (expr
) != SSA_NAME
)
195 /* Mark the blocks in the chain leading to the end. */
196 at_bb
= gimple_bb (at
);
197 call_bb
= gimple_bb (gsi_stmt (gsi
));
198 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
204 at
= SSA_NAME_DEF_STMT (expr
);
207 /* The default definition or defined before the chain. */
213 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
214 if (gsi_stmt (gsi
) == at
)
217 if (!gsi_end_p (gsi
))
222 if (gimple_code (at
) != GIMPLE_PHI
)
228 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
233 expr
= PHI_ARG_DEF_FROM_EDGE (at
, e
);
234 if (TREE_CODE (expr
) != SSA_NAME
)
236 /* The value is a constant. */
241 /* Unmark the blocks. */
242 for (bb
= call_bb
; bb
!= at_bb
; bb
= single_succ (bb
))
249 /* Simulates the effect of an assignment STMT on the return value of the tail
250 recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
251 additive factor for the real return value. */
254 process_assignment (gimple stmt
, gimple_stmt_iterator call
, tree
*m
,
255 tree
*a
, tree
*ass_var
)
257 tree op0
, op1
= NULL_TREE
, non_ass_var
= NULL_TREE
;
258 tree dest
= gimple_assign_lhs (stmt
);
259 enum tree_code code
= gimple_assign_rhs_code (stmt
);
260 enum gimple_rhs_class rhs_class
= get_gimple_rhs_class (code
);
261 tree src_var
= gimple_assign_rhs1 (stmt
);
263 /* See if this is a simple copy operation of an SSA name to the function
264 result. In that case we may have a simple tail call. Ignore type
265 conversions that can never produce extra code between the function
266 call and the function return. */
267 if ((rhs_class
== GIMPLE_SINGLE_RHS
|| gimple_assign_cast_p (stmt
))
268 && (TREE_CODE (src_var
) == SSA_NAME
))
270 /* Reject a tailcall if the type conversion might need
272 if (gimple_assign_cast_p (stmt
)
273 && TYPE_MODE (TREE_TYPE (dest
)) != TYPE_MODE (TREE_TYPE (src_var
)))
276 if (src_var
!= *ass_var
)
285 case GIMPLE_BINARY_RHS
:
286 op1
= gimple_assign_rhs2 (stmt
);
290 case GIMPLE_UNARY_RHS
:
291 op0
= gimple_assign_rhs1 (stmt
);
298 /* Accumulator optimizations will reverse the order of operations.
299 We can only do that for floating-point types if we're assuming
300 that addition and multiplication are associative. */
301 if (!flag_associative_math
)
302 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
305 if (rhs_class
== GIMPLE_UNARY_RHS
)
307 else if (op0
== *ass_var
308 && (non_ass_var
= independent_of_stmt_p (op1
, stmt
, call
)))
310 else if (op1
== *ass_var
311 && (non_ass_var
= independent_of_stmt_p (op0
, stmt
, call
)))
323 case POINTER_PLUS_EXPR
:
336 *m
= build_minus_one_cst (TREE_TYPE (op0
));
342 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
345 *m
= build_minus_one_cst (TREE_TYPE (non_ass_var
));
346 *a
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (non_ass_var
), non_ass_var
);
352 /* TODO -- Handle POINTER_PLUS_EXPR. */
359 /* Propagate VAR through phis on edge E. */
362 propagate_through_phis (tree var
, edge e
)
364 basic_block dest
= e
->dest
;
365 gimple_stmt_iterator gsi
;
367 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
369 gimple phi
= gsi_stmt (gsi
);
370 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
)
371 return PHI_RESULT (phi
);
376 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
377 added to the start of RET. */
380 find_tail_calls (basic_block bb
, struct tailcall
**ret
)
382 tree ass_var
= NULL_TREE
, ret_var
, func
, param
;
383 gimple stmt
, call
= NULL
;
384 gimple_stmt_iterator gsi
, agsi
;
393 if (!single_succ_p (bb
))
396 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
398 stmt
= gsi_stmt (gsi
);
400 /* Ignore labels, returns, clobbers and debug stmts. */
401 if (gimple_code (stmt
) == GIMPLE_LABEL
402 || gimple_code (stmt
) == GIMPLE_RETURN
403 || gimple_clobber_p (stmt
)
404 || is_gimple_debug (stmt
))
407 /* Check for a call. */
408 if (is_gimple_call (stmt
))
411 ass_var
= gimple_call_lhs (stmt
);
415 /* If the statement references memory or volatile operands, fail. */
416 if (gimple_references_memory_p (stmt
)
417 || gimple_has_volatile_ops (stmt
))
424 /* Recurse to the predecessors. */
425 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
426 find_tail_calls (e
->src
, ret
);
431 /* If the LHS of our call is not just a simple register, we can't
432 transform this into a tail or sibling call. This situation happens,
433 in (e.g.) "*p = foo()" where foo returns a struct. In this case
434 we won't have a temporary here, but we need to carry out the side
435 effect anyway, so tailcall is impossible.
437 ??? In some situations (when the struct is returned in memory via
438 invisible argument) we could deal with this, e.g. by passing 'p'
439 itself as that argument to foo, but it's too early to do this here,
440 and expand_call() will not handle it anyway. If it ever can, then
441 we need to revisit this here, to allow that situation. */
442 if (ass_var
&& !is_gimple_reg (ass_var
))
445 /* We found the call, check whether it is suitable. */
446 tail_recursion
= false;
447 func
= gimple_call_fndecl (call
);
448 if (func
== current_function_decl
)
452 for (param
= DECL_ARGUMENTS (func
), idx
= 0;
453 param
&& idx
< gimple_call_num_args (call
);
454 param
= DECL_CHAIN (param
), idx
++)
456 arg
= gimple_call_arg (call
, idx
);
459 /* Make sure there are no problems with copying. The parameter
460 have a copyable type and the two arguments must have reasonably
461 equivalent types. The latter requirement could be relaxed if
462 we emitted a suitable type conversion statement. */
463 if (!is_gimple_reg_type (TREE_TYPE (param
))
464 || !useless_type_conversion_p (TREE_TYPE (param
),
468 /* The parameter should be a real operand, so that phi node
469 created for it at the start of the function has the meaning
470 of copying the value. This test implies is_gimple_reg_type
471 from the previous condition, however this one could be
472 relaxed by being more careful with copying the new value
473 of the parameter (emitting appropriate GIMPLE_ASSIGN and
474 updating the virtual operands). */
475 if (!is_gimple_reg (param
))
479 if (idx
== gimple_call_num_args (call
) && !param
)
480 tail_recursion
= true;
483 /* Make sure the tail invocation of this function does not refer
484 to local variables. */
485 FOR_EACH_LOCAL_DECL (cfun
, idx
, var
)
487 if (TREE_CODE (var
) != PARM_DECL
488 && auto_var_in_fn_p (var
, cfun
->decl
)
489 && (ref_maybe_used_by_stmt_p (call
, var
)
490 || call_may_clobber_ref_p (call
, var
)))
494 /* Now check the statements after the call. None of them has virtual
495 operands, so they may only depend on the call through its return
496 value. The return value should also be dependent on each of them,
497 since we are running after dce. */
505 tree tmp_a
= NULL_TREE
;
506 tree tmp_m
= NULL_TREE
;
509 while (gsi_end_p (agsi
))
511 ass_var
= propagate_through_phis (ass_var
, single_succ_edge (abb
));
512 abb
= single_succ (abb
);
513 agsi
= gsi_start_bb (abb
);
516 stmt
= gsi_stmt (agsi
);
518 if (gimple_code (stmt
) == GIMPLE_LABEL
)
521 if (gimple_code (stmt
) == GIMPLE_RETURN
)
524 if (gimple_clobber_p (stmt
))
527 if (is_gimple_debug (stmt
))
530 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
533 /* This is a gimple assign. */
534 if (! process_assignment (stmt
, gsi
, &tmp_m
, &tmp_a
, &ass_var
))
539 tree type
= TREE_TYPE (tmp_a
);
541 a
= fold_build2 (PLUS_EXPR
, type
, fold_convert (type
, a
), tmp_a
);
547 tree type
= TREE_TYPE (tmp_m
);
549 m
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, m
), tmp_m
);
554 a
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, a
), tmp_m
);
558 /* See if this is a tail call we can handle. */
559 ret_var
= gimple_return_retval (stmt
);
561 /* We may proceed if there either is no return value, or the return value
562 is identical to the call's return. */
564 && (ret_var
!= ass_var
))
567 /* If this is not a tail recursive call, we cannot handle addends or
569 if (!tail_recursion
&& (m
|| a
))
572 /* For pointers only allow additions. */
573 if (m
&& POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
576 nw
= XNEW (struct tailcall
);
580 nw
->tail_recursion
= tail_recursion
;
589 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
592 add_successor_phi_arg (edge e
, tree var
, tree phi_arg
)
594 gimple_stmt_iterator gsi
;
596 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
597 if (PHI_RESULT (gsi_stmt (gsi
)) == var
)
600 gcc_assert (!gsi_end_p (gsi
));
601 add_phi_arg (gsi_stmt (gsi
), phi_arg
, e
, UNKNOWN_LOCATION
);
604 /* Creates a GIMPLE statement which computes the operation specified by
605 CODE, ACC and OP1 to a new variable with name LABEL and inserts the
606 statement in the position specified by GSI. Returns the
607 tree node of the statement's result. */
610 adjust_return_value_with_ops (enum tree_code code
, const char *label
,
611 tree acc
, tree op1
, gimple_stmt_iterator gsi
)
614 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
615 tree result
= make_temp_ssa_name (ret_type
, NULL
, label
);
618 if (POINTER_TYPE_P (ret_type
))
620 gcc_assert (code
== PLUS_EXPR
&& TREE_TYPE (acc
) == sizetype
);
621 code
= POINTER_PLUS_EXPR
;
623 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
))
624 && code
!= POINTER_PLUS_EXPR
)
625 stmt
= gimple_build_assign_with_ops (code
, result
, acc
, op1
);
629 if (code
== POINTER_PLUS_EXPR
)
630 tem
= fold_build2 (code
, TREE_TYPE (op1
), op1
, acc
);
632 tem
= fold_build2 (code
, TREE_TYPE (op1
),
633 fold_convert (TREE_TYPE (op1
), acc
), op1
);
634 tree rhs
= fold_convert (ret_type
, tem
);
635 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
636 false, NULL
, true, GSI_SAME_STMT
);
637 stmt
= gimple_build_assign (result
, rhs
);
640 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
644 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
645 the computation specified by CODE and OP1 and insert the statement
646 at the position specified by GSI as a new statement. Returns new SSA name
647 of updated accumulator. */
650 update_accumulator_with_ops (enum tree_code code
, tree acc
, tree op1
,
651 gimple_stmt_iterator gsi
)
654 tree var
= copy_ssa_name (acc
, NULL
);
655 if (types_compatible_p (TREE_TYPE (acc
), TREE_TYPE (op1
)))
656 stmt
= gimple_build_assign_with_ops (code
, var
, acc
, op1
);
659 tree rhs
= fold_convert (TREE_TYPE (acc
),
662 fold_convert (TREE_TYPE (op1
), acc
),
664 rhs
= force_gimple_operand_gsi (&gsi
, rhs
,
665 false, NULL
, false, GSI_CONTINUE_LINKING
);
666 stmt
= gimple_build_assign (var
, rhs
);
668 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
672 /* Adjust the accumulator values according to A and M after GSI, and update
673 the phi nodes on edge BACK. */
676 adjust_accumulator_values (gimple_stmt_iterator gsi
, tree m
, tree a
, edge back
)
678 tree var
, a_acc_arg
, m_acc_arg
;
681 m
= force_gimple_operand_gsi (&gsi
, m
, true, NULL
, true, GSI_SAME_STMT
);
683 a
= force_gimple_operand_gsi (&gsi
, a
, true, NULL
, true, GSI_SAME_STMT
);
691 if (integer_onep (a
))
694 var
= adjust_return_value_with_ops (MULT_EXPR
, "acc_tmp", m_acc
,
700 a_acc_arg
= update_accumulator_with_ops (PLUS_EXPR
, a_acc
, var
, gsi
);
704 m_acc_arg
= update_accumulator_with_ops (MULT_EXPR
, m_acc
, m
, gsi
);
707 add_successor_phi_arg (back
, a_acc
, a_acc_arg
);
710 add_successor_phi_arg (back
, m_acc
, m_acc_arg
);
713 /* Adjust value of the return at the end of BB according to M and A
717 adjust_return_value (basic_block bb
, tree m
, tree a
)
720 gimple ret_stmt
= gimple_seq_last_stmt (bb_seq (bb
));
721 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
723 gcc_assert (gimple_code (ret_stmt
) == GIMPLE_RETURN
);
725 retval
= gimple_return_retval (ret_stmt
);
726 if (!retval
|| retval
== error_mark_node
)
730 retval
= adjust_return_value_with_ops (MULT_EXPR
, "mul_tmp", m_acc
, retval
,
733 retval
= adjust_return_value_with_ops (PLUS_EXPR
, "acc_tmp", a_acc
, retval
,
735 gimple_return_set_retval (ret_stmt
, retval
);
736 update_stmt (ret_stmt
);
739 /* Subtract COUNT and FREQUENCY from the basic block and it's
742 decrease_profile (basic_block bb
, gcov_type count
, int frequency
)
748 bb
->frequency
-= frequency
;
749 if (bb
->frequency
< 0)
751 if (!single_succ_p (bb
))
753 gcc_assert (!EDGE_COUNT (bb
->succs
));
756 e
= single_succ_edge (bb
);
762 /* Returns true if argument PARAM of the tail recursive call needs to be copied
763 when the call is eliminated. */
766 arg_needs_copy_p (tree param
)
770 if (!is_gimple_reg (param
))
773 /* Parameters that are only defined but never used need not be copied. */
774 def
= ssa_default_def (cfun
, param
);
781 /* Eliminates tail call described by T. TMP_VARS is a list of
782 temporary variables used to copy the function arguments. */
785 eliminate_tail_call (struct tailcall
*t
)
791 basic_block bb
, first
;
794 gimple_stmt_iterator gsi
;
797 stmt
= orig_stmt
= gsi_stmt (t
->call_gsi
);
798 bb
= gsi_bb (t
->call_gsi
);
800 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
802 fprintf (dump_file
, "Eliminated tail recursion in bb %d : ",
804 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
805 fprintf (dump_file
, "\n");
808 gcc_assert (is_gimple_call (stmt
));
810 first
= single_succ (ENTRY_BLOCK_PTR
);
812 /* Remove the code after call_gsi that will become unreachable. The
813 possibly unreachable code in other blocks is removed later in
817 while (!gsi_end_p (gsi
))
819 gimple t
= gsi_stmt (gsi
);
820 /* Do not remove the return statement, so that redirect_edge_and_branch
821 sees how the block ends. */
822 if (gimple_code (t
) == GIMPLE_RETURN
)
825 gsi_remove (&gsi
, true);
829 /* Number of executions of function has reduced by the tailcall. */
830 e
= single_succ_edge (gsi_bb (t
->call_gsi
));
831 decrease_profile (EXIT_BLOCK_PTR
, e
->count
, EDGE_FREQUENCY (e
));
832 decrease_profile (ENTRY_BLOCK_PTR
, e
->count
, EDGE_FREQUENCY (e
));
833 if (e
->dest
!= EXIT_BLOCK_PTR
)
834 decrease_profile (e
->dest
, e
->count
, EDGE_FREQUENCY (e
));
836 /* Replace the call by a jump to the start of function. */
837 e
= redirect_edge_and_branch (single_succ_edge (gsi_bb (t
->call_gsi
)),
840 PENDING_STMT (e
) = NULL
;
842 /* Add phi node entries for arguments. The ordering of the phi nodes should
843 be the same as the ordering of the arguments. */
844 for (param
= DECL_ARGUMENTS (current_function_decl
),
845 idx
= 0, gsi
= gsi_start_phis (first
);
847 param
= DECL_CHAIN (param
), idx
++)
849 if (!arg_needs_copy_p (param
))
852 arg
= gimple_call_arg (stmt
, idx
);
853 phi
= gsi_stmt (gsi
);
854 gcc_assert (param
== SSA_NAME_VAR (PHI_RESULT (phi
)));
856 add_phi_arg (phi
, arg
, e
, gimple_location (stmt
));
860 /* Update the values of accumulators. */
861 adjust_accumulator_values (t
->call_gsi
, t
->mult
, t
->add
, e
);
863 call
= gsi_stmt (t
->call_gsi
);
864 rslt
= gimple_call_lhs (call
);
865 if (rslt
!= NULL_TREE
)
867 /* Result of the call will no longer be defined. So adjust the
868 SSA_NAME_DEF_STMT accordingly. */
869 SSA_NAME_DEF_STMT (rslt
) = gimple_build_nop ();
872 gsi_remove (&t
->call_gsi
, true);
876 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
877 mark the tailcalls for the sibcall optimization. */
880 optimize_tail_call (struct tailcall
*t
, bool opt_tailcalls
)
882 if (t
->tail_recursion
)
884 eliminate_tail_call (t
);
890 gimple stmt
= gsi_stmt (t
->call_gsi
);
892 gimple_call_set_tail (stmt
, true);
893 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
895 fprintf (dump_file
, "Found tail call ");
896 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
897 fprintf (dump_file
, " in bb %i\n", (gsi_bb (t
->call_gsi
))->index
);
904 /* Creates a tail-call accumulator of the same type as the return type of the
905 current function. LABEL is the name used to creating the temporary
906 variable for the accumulator. The accumulator will be inserted in the
907 phis of a basic block BB with single predecessor with an initial value
908 INIT converted to the current function return type. */
911 create_tailcall_accumulator (const char *label
, basic_block bb
, tree init
)
913 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
914 if (POINTER_TYPE_P (ret_type
))
917 tree tmp
= make_temp_ssa_name (ret_type
, NULL
, label
);
920 phi
= create_phi_node (tmp
, bb
);
921 /* RET_TYPE can be a float when -ffast-maths is enabled. */
922 add_phi_arg (phi
, fold_convert (ret_type
, init
), single_pred_edge (bb
),
924 return PHI_RESULT (phi
);
927 /* Optimizes tail calls in the function, turning the tail recursion
931 tree_optimize_tail_calls_1 (bool opt_tailcalls
)
934 bool phis_constructed
= false;
935 struct tailcall
*tailcalls
= NULL
, *act
, *next
;
936 bool changed
= false;
937 basic_block first
= single_succ (ENTRY_BLOCK_PTR
);
942 if (!suitable_for_tail_opt_p ())
945 opt_tailcalls
= suitable_for_tail_call_opt_p ();
947 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
949 /* Only traverse the normal exits, i.e. those that end with return
951 stmt
= last_stmt (e
->src
);
954 && gimple_code (stmt
) == GIMPLE_RETURN
)
955 find_tail_calls (e
->src
, &tailcalls
);
958 /* Construct the phi nodes and accumulators if necessary. */
959 a_acc
= m_acc
= NULL_TREE
;
960 for (act
= tailcalls
; act
; act
= act
->next
)
962 if (!act
->tail_recursion
)
965 if (!phis_constructed
)
967 /* Ensure that there is only one predecessor of the block
968 or if there are existing degenerate PHI nodes. */
969 if (!single_pred_p (first
)
970 || !gimple_seq_empty_p (phi_nodes (first
)))
971 first
= split_edge (single_succ_edge (ENTRY_BLOCK_PTR
));
973 /* Copy the args if needed. */
974 for (param
= DECL_ARGUMENTS (current_function_decl
);
976 param
= DECL_CHAIN (param
))
977 if (arg_needs_copy_p (param
))
979 tree name
= ssa_default_def (cfun
, param
);
980 tree new_name
= make_ssa_name (param
, SSA_NAME_DEF_STMT (name
));
983 set_ssa_default_def (cfun
, param
, new_name
);
984 phi
= create_phi_node (name
, first
);
985 add_phi_arg (phi
, new_name
, single_pred_edge (first
),
986 EXPR_LOCATION (param
));
988 phis_constructed
= true;
991 if (act
->add
&& !a_acc
)
992 a_acc
= create_tailcall_accumulator ("add_acc", first
,
995 if (act
->mult
&& !m_acc
)
996 m_acc
= create_tailcall_accumulator ("mult_acc", first
,
1002 /* When the tail call elimination using accumulators is performed,
1003 statements adding the accumulated value are inserted at all exits.
1004 This turns all other tail calls to non-tail ones. */
1005 opt_tailcalls
= false;
1008 for (; tailcalls
; tailcalls
= next
)
1010 next
= tailcalls
->next
;
1011 changed
|= optimize_tail_call (tailcalls
, opt_tailcalls
);
1017 /* Modify the remaining return statements. */
1018 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1020 stmt
= last_stmt (e
->src
);
1023 && gimple_code (stmt
) == GIMPLE_RETURN
)
1024 adjust_return_value (e
->src
, m_acc
, a_acc
);
1030 /* We may have created new loops. Make them magically appear. */
1032 loops_state_set (LOOPS_NEED_FIXUP
);
1033 free_dominance_info (CDI_DOMINATORS
);
1036 /* Add phi nodes for the virtual operands defined in the function to the
1037 header of the loop created by tail recursion elimination. Do so
1038 by triggering the SSA renamer. */
1039 if (phis_constructed
)
1040 mark_virtual_operands_for_renaming (cfun
);
1043 return TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
1048 execute_tail_recursion (void)
1050 return tree_optimize_tail_calls_1 (false);
1054 gate_tail_calls (void)
1056 return flag_optimize_sibling_calls
!= 0 && dbg_cnt (tail_call
);
1060 execute_tail_calls (void)
1062 return tree_optimize_tail_calls_1 (true);
1067 const pass_data pass_data_tail_recursion
=
1069 GIMPLE_PASS
, /* type */
1071 OPTGROUP_NONE
, /* optinfo_flags */
1072 true, /* has_gate */
1073 true, /* has_execute */
1074 TV_NONE
, /* tv_id */
1075 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1076 0, /* properties_provided */
1077 0, /* properties_destroyed */
1078 0, /* todo_flags_start */
1079 TODO_verify_ssa
, /* todo_flags_finish */
1082 class pass_tail_recursion
: public gimple_opt_pass
1085 pass_tail_recursion(gcc::context
*ctxt
)
1086 : gimple_opt_pass(pass_data_tail_recursion
, ctxt
)
1089 /* opt_pass methods: */
1090 opt_pass
* clone () { return new pass_tail_recursion (ctxt_
); }
1091 bool gate () { return gate_tail_calls (); }
1092 unsigned int execute () { return execute_tail_recursion (); }
1094 }; // class pass_tail_recursion
1099 make_pass_tail_recursion (gcc::context
*ctxt
)
1101 return new pass_tail_recursion (ctxt
);
1106 const pass_data pass_data_tail_calls
=
1108 GIMPLE_PASS
, /* type */
1110 OPTGROUP_NONE
, /* optinfo_flags */
1111 true, /* has_gate */
1112 true, /* has_execute */
1113 TV_NONE
, /* tv_id */
1114 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1115 0, /* properties_provided */
1116 0, /* properties_destroyed */
1117 0, /* todo_flags_start */
1118 TODO_verify_ssa
, /* todo_flags_finish */
1121 class pass_tail_calls
: public gimple_opt_pass
1124 pass_tail_calls(gcc::context
*ctxt
)
1125 : gimple_opt_pass(pass_data_tail_calls
, ctxt
)
1128 /* opt_pass methods: */
1129 bool gate () { return gate_tail_calls (); }
1130 unsigned int execute () { return execute_tail_calls (); }
1132 }; // class pass_tail_calls
1137 make_pass_tail_calls (gcc::context
*ctxt
)
1139 return new pass_tail_calls (ctxt
);