1 /* Tail call optimization on trees.
2 Copyright (C) 2003, 2004 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 2, 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 COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
33 #include "diagnostic.h"
35 #include "tree-pass.h"
37 #include "langhooks.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 block in that the call occur. */
104 basic_block call_block
;
106 /* The iterator pointing to the call statement. */
107 block_stmt_iterator call_bsi
;
109 /* True if it is a call to the current function. */
112 /* The return value of the caller is mult * f + add, where f is the return
113 value of the call. */
116 /* Next tailcall in the chain. */
117 struct tailcall
*next
;
120 /* The variables holding the value of multiplicative and additive
122 static tree m_acc
, a_acc
;
124 static bool suitable_for_tail_opt_p (void);
125 static bool optimize_tail_call (struct tailcall
*, bool);
126 static void eliminate_tail_call (struct tailcall
*);
127 static void find_tail_calls (basic_block
, struct tailcall
**);
129 /* Returns false when the function is not suitable for tail call optimization
130 from some reason (e.g. if it takes variable number of arguments). */
133 suitable_for_tail_opt_p (void)
137 if (current_function_stdarg
)
140 /* No local variable should be call-clobbered. We ignore any kind
141 of memory tag, as these are not real variables. */
142 for (i
= 0; i
< (int) VARRAY_ACTIVE_SIZE (referenced_vars
); i
++)
144 tree var
= VARRAY_TREE (referenced_vars
, i
);
146 if (!(TREE_STATIC (var
) || DECL_EXTERNAL (var
))
147 && var_ann (var
)->mem_tag_kind
== NOT_A_TAG
148 && is_call_clobbered (var
))
154 /* Returns false when the function is not suitable for tail call optimization
155 from some reason (e.g. if it takes variable number of arguments).
156 This test must pass in addition to suitable_for_tail_opt_p in order to make
157 tail call discovery happen. */
160 suitable_for_tail_call_opt_p (void)
162 /* alloca (until we have stack slot life analysis) inhibits
163 sibling call optimizations, but not tail recursion. */
164 if (current_function_calls_alloca
)
167 /* If we are using sjlj exceptions, we may need to add a call to
168 _Unwind_SjLj_Unregister at exit of the function. Which means
169 that we cannot do any sibcall transformations. */
170 if (USING_SJLJ_EXCEPTIONS
&& current_function_has_exception_handlers ())
173 /* Any function that calls setjmp might have longjmp called from
174 any called function. ??? We really should represent this
175 properly in the CFG so that this needn't be special cased. */
176 if (current_function_calls_setjmp
)
182 /* Checks whether the expression EXPR in stmt AT is independent of the
183 statement pointed by BSI (in a sense that we already know EXPR's value
184 at BSI). We use the fact that we are only called from the chain of
185 basic blocks that have only single successor. Returns the expression
186 containing the value of EXPR at BSI. */
189 independent_of_stmt_p (tree expr
, tree at
, block_stmt_iterator bsi
)
191 basic_block bb
, call_bb
, at_bb
;
195 if (is_gimple_min_invariant (expr
))
198 if (TREE_CODE (expr
) != SSA_NAME
)
201 /* Mark the blocks in the chain leading to the end. */
202 at_bb
= bb_for_stmt (at
);
203 call_bb
= bb_for_stmt (bsi_stmt (bsi
));
204 for (bb
= call_bb
; bb
!= at_bb
; bb
= EDGE_SUCC (bb
, 0)->dest
)
210 at
= SSA_NAME_DEF_STMT (expr
);
211 bb
= bb_for_stmt (at
);
213 /* The default definition or defined before the chain. */
219 for (; !bsi_end_p (bsi
); bsi_next (&bsi
))
220 if (bsi_stmt (bsi
) == at
)
223 if (!bsi_end_p (bsi
))
228 if (TREE_CODE (at
) != PHI_NODE
)
234 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
239 expr
= PHI_ARG_DEF_FROM_EDGE (at
, e
);
240 if (TREE_CODE (expr
) != SSA_NAME
)
242 /* The value is a constant. */
247 /* Unmark the blocks. */
248 for (bb
= call_bb
; bb
!= at_bb
; bb
= EDGE_SUCC (bb
, 0)->dest
)
255 /* Simulates the effect of an assignment of ASS in STMT on the return value
256 of the tail recursive CALL passed in ASS_VAR. M and A are the
257 multiplicative and the additive factor for the real return value. */
260 process_assignment (tree ass
, tree stmt
, block_stmt_iterator call
, tree
*m
,
261 tree
*a
, tree
*ass_var
)
263 tree op0
, op1
, non_ass_var
;
264 tree dest
= TREE_OPERAND (ass
, 0);
265 tree src
= TREE_OPERAND (ass
, 1);
266 enum tree_code code
= TREE_CODE (src
);
269 /* See if this is a simple copy operation of an SSA name to the function
270 result. In that case we may have a simple tail call. Ignore type
271 conversions that can never produce extra code between the function
272 call and the function return. */
273 STRIP_NOPS (src_var
);
274 if (TREE_CODE (src_var
) == SSA_NAME
)
276 if (src_var
!= *ass_var
)
283 if (TREE_CODE_CLASS (code
) != tcc_binary
)
286 /* Accumulator optimizations will reverse the order of operations.
287 We can only do that for floating-point types if we're assuming
288 that addition and multiplication are associative. */
289 if (!flag_unsafe_math_optimizations
)
290 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl
))))
293 /* We only handle the code like
300 TODO -- Extend it for cases where the linear transformation of the output
301 is expressed in a more complicated way. */
303 op0
= TREE_OPERAND (src
, 0);
304 op1
= TREE_OPERAND (src
, 1);
307 && (non_ass_var
= independent_of_stmt_p (op1
, stmt
, call
)))
309 else if (op1
== *ass_var
310 && (non_ass_var
= independent_of_stmt_p (op0
, stmt
, call
)))
318 /* There should be no previous addition. TODO -- it should be fairly
319 straightforward to lift this restriction -- just allow storing
320 more complicated expressions in *A, and gimplify it in
321 adjust_accumulator_values. */
329 /* Similar remark applies here. Handling multiplication after addition
330 is just slightly more complicated -- we need to multiply both *A and
338 /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR). */
345 /* Propagate VAR through phis on edge E. */
348 propagate_through_phis (tree var
, edge e
)
350 basic_block dest
= e
->dest
;
353 for (phi
= phi_nodes (dest
); phi
; phi
= PHI_CHAIN (phi
))
354 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
)
355 return PHI_RESULT (phi
);
360 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
361 added to the start of RET. */
364 find_tail_calls (basic_block bb
, struct tailcall
**ret
)
366 tree ass_var
, ret_var
, stmt
, func
, param
, args
, call
= NULL_TREE
;
367 block_stmt_iterator bsi
, absi
;
375 if (EDGE_COUNT (bb
->succs
) > 1)
378 for (bsi
= bsi_last (bb
); !bsi_end_p (bsi
); bsi_prev (&bsi
))
380 stmt
= bsi_stmt (bsi
);
383 if (TREE_CODE (stmt
) == LABEL_EXPR
)
386 get_stmt_operands (stmt
);
388 /* Check for a call. */
389 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
391 ass_var
= TREE_OPERAND (stmt
, 0);
392 call
= TREE_OPERAND (stmt
, 1);
393 if (TREE_CODE (call
) == WITH_SIZE_EXPR
)
394 call
= TREE_OPERAND (call
, 0);
402 if (TREE_CODE (call
) == CALL_EXPR
)
405 /* If the statement has virtual or volatile operands, fail. */
406 ann
= stmt_ann (stmt
);
407 if (!ZERO_SSA_OPERANDS (stmt
, (SSA_OP_VUSE
| SSA_OP_VIRTUAL_DEFS
))
408 || ann
->has_volatile_ops
)
415 /* Recurse to the predecessors. */
416 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
417 find_tail_calls (e
->src
, ret
);
422 /* We found the call, check whether it is suitable. */
423 tail_recursion
= false;
424 func
= get_callee_fndecl (call
);
425 if (func
== current_function_decl
)
427 for (param
= DECL_ARGUMENTS (func
), args
= TREE_OPERAND (call
, 1);
429 param
= TREE_CHAIN (param
), args
= TREE_CHAIN (args
))
431 tree arg
= TREE_VALUE (args
);
434 /* Make sure there are no problems with copying. The parameter
435 have a copyable type and the two arguments must have reasonably
436 equivalent types. The latter requirement could be relaxed if
437 we emitted a suitable type conversion statement. */
438 if (!is_gimple_reg_type (TREE_TYPE (param
))
439 || !lang_hooks
.types_compatible_p (TREE_TYPE (param
),
443 /* The parameter should be a real operand, so that phi node
444 created for it at the start of the function has the meaning
445 of copying the value. This test implies is_gimple_reg_type
446 from the previous condition, however this one could be
447 relaxed by being more careful with copying the new value
448 of the parameter (emitting appropriate MODIFY_EXPR and
449 updating the virtual operands). */
450 if (!is_gimple_reg (param
))
455 tail_recursion
= true;
458 /* Now check the statements after the call. None of them has virtual
459 operands, so they may only depend on the call through its return
460 value. The return value should also be dependent on each of them,
461 since we are running after dce. */
471 while (bsi_end_p (absi
))
473 ass_var
= propagate_through_phis (ass_var
, EDGE_SUCC (abb
, 0));
474 abb
= EDGE_SUCC (abb
, 0)->dest
;
475 absi
= bsi_start (abb
);
478 stmt
= bsi_stmt (absi
);
480 if (TREE_CODE (stmt
) == LABEL_EXPR
)
483 if (TREE_CODE (stmt
) == RETURN_EXPR
)
486 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
489 if (!process_assignment (stmt
, stmt
, bsi
, &m
, &a
, &ass_var
))
493 /* See if this is a tail call we can handle. */
494 ret_var
= TREE_OPERAND (stmt
, 0);
496 && TREE_CODE (ret_var
) == MODIFY_EXPR
)
498 tree ret_op
= TREE_OPERAND (ret_var
, 1);
501 && TREE_CODE (ret_op
) != SSA_NAME
)
504 if (!process_assignment (ret_var
, stmt
, bsi
, &m
, &a
, &ass_var
))
506 ret_var
= TREE_OPERAND (ret_var
, 0);
509 /* We may proceed if there either is no return value, or the return value
510 is identical to the call's return. */
512 && (ret_var
!= ass_var
))
515 /* If this is not a tail recursive call, we cannot handle addends or
517 if (!tail_recursion
&& (m
|| a
))
520 nw
= xmalloc (sizeof (struct tailcall
));
525 nw
->tail_recursion
= tail_recursion
;
534 /* Adjust the accumulator values according to A and M after BSI, and update
535 the phi nodes on edge BACK. */
538 adjust_accumulator_values (block_stmt_iterator bsi
, tree m
, tree a
, edge back
)
540 tree stmt
, var
, phi
, tmp
;
541 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
542 tree a_acc_arg
= a_acc
, m_acc_arg
= m_acc
;
548 if (integer_onep (a
))
552 stmt
= build (MODIFY_EXPR
, ret_type
, NULL_TREE
,
553 build (MULT_EXPR
, ret_type
, m_acc
, a
));
555 tmp
= create_tmp_var (ret_type
, "acc_tmp");
556 add_referenced_tmp_var (tmp
);
558 var
= make_ssa_name (tmp
, stmt
);
559 TREE_OPERAND (stmt
, 0) = var
;
560 bsi_insert_after (&bsi
, stmt
, BSI_NEW_STMT
);
566 stmt
= build (MODIFY_EXPR
, ret_type
, NULL_TREE
,
567 build (PLUS_EXPR
, ret_type
, a_acc
, var
));
568 var
= make_ssa_name (SSA_NAME_VAR (a_acc
), stmt
);
569 TREE_OPERAND (stmt
, 0) = var
;
570 bsi_insert_after (&bsi
, stmt
, BSI_NEW_STMT
);
576 stmt
= build (MODIFY_EXPR
, ret_type
, NULL_TREE
,
577 build (MULT_EXPR
, ret_type
, m_acc
, m
));
578 var
= make_ssa_name (SSA_NAME_VAR (m_acc
), stmt
);
579 TREE_OPERAND (stmt
, 0) = var
;
580 bsi_insert_after (&bsi
, stmt
, BSI_NEW_STMT
);
586 for (phi
= phi_nodes (back
->dest
); phi
; phi
= PHI_CHAIN (phi
))
587 if (PHI_RESULT (phi
) == a_acc
)
590 add_phi_arg (&phi
, a_acc_arg
, back
);
595 for (phi
= phi_nodes (back
->dest
); phi
; phi
= PHI_CHAIN (phi
))
596 if (PHI_RESULT (phi
) == m_acc
)
599 add_phi_arg (&phi
, m_acc_arg
, back
);
603 /* Adjust value of the return at the end of BB according to M and A
607 adjust_return_value (basic_block bb
, tree m
, tree a
)
609 tree ret_stmt
= last_stmt (bb
), ret_var
, var
, stmt
, tmp
;
610 tree ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
611 block_stmt_iterator bsi
= bsi_last (bb
);
613 gcc_assert (TREE_CODE (ret_stmt
) == RETURN_EXPR
);
615 ret_var
= TREE_OPERAND (ret_stmt
, 0);
619 if (TREE_CODE (ret_var
) == MODIFY_EXPR
)
621 ret_var
->common
.ann
= (tree_ann_t
) stmt_ann (ret_stmt
);
622 bsi_replace (&bsi
, ret_var
, true);
623 SSA_NAME_DEF_STMT (TREE_OPERAND (ret_var
, 0)) = ret_var
;
624 ret_var
= TREE_OPERAND (ret_var
, 0);
625 ret_stmt
= build1 (RETURN_EXPR
, TREE_TYPE (ret_stmt
), ret_var
);
626 bsi_insert_after (&bsi
, ret_stmt
, BSI_NEW_STMT
);
631 stmt
= build (MODIFY_EXPR
, ret_type
, NULL_TREE
,
632 build (MULT_EXPR
, ret_type
, m_acc
, ret_var
));
634 tmp
= create_tmp_var (ret_type
, "acc_tmp");
635 add_referenced_tmp_var (tmp
);
637 var
= make_ssa_name (tmp
, stmt
);
638 TREE_OPERAND (stmt
, 0) = var
;
639 bsi_insert_before (&bsi
, stmt
, BSI_SAME_STMT
);
646 stmt
= build (MODIFY_EXPR
, ret_type
, NULL_TREE
,
647 build (PLUS_EXPR
, ret_type
, a_acc
, var
));
649 tmp
= create_tmp_var (ret_type
, "acc_tmp");
650 add_referenced_tmp_var (tmp
);
652 var
= make_ssa_name (tmp
, stmt
);
653 TREE_OPERAND (stmt
, 0) = var
;
654 bsi_insert_before (&bsi
, stmt
, BSI_SAME_STMT
);
657 TREE_OPERAND (ret_stmt
, 0) = var
;
658 update_stmt (ret_stmt
);
661 /* Eliminates tail call described by T. TMP_VARS is a list of
662 temporary variables used to copy the function arguments. */
665 eliminate_tail_call (struct tailcall
*t
)
667 tree param
, stmt
, args
, rslt
, call
;
668 basic_block bb
, first
;
671 block_stmt_iterator bsi
;
672 use_operand_p mayuse
;
673 def_operand_p maydef
;
677 stmt
= orig_stmt
= bsi_stmt (t
->call_bsi
);
678 get_stmt_operands (stmt
);
681 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
683 fprintf (dump_file
, "Eliminated tail recursion in bb %d : ",
685 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
686 fprintf (dump_file
, "\n");
689 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
690 stmt
= TREE_OPERAND (stmt
, 1);
692 first
= EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->dest
;
694 /* Remove the code after call_bsi that will become unreachable. The
695 possibly unreachable code in other blocks is removed later in
699 while (!bsi_end_p (bsi
))
701 tree t
= bsi_stmt (bsi
);
702 /* Do not remove the return statement, so that redirect_edge_and_branch
703 sees how the block ends. */
704 if (TREE_CODE (t
) == RETURN_EXPR
)
711 /* Replace the call by a jump to the start of function. */
712 e
= redirect_edge_and_branch (EDGE_SUCC (t
->call_block
, 0), first
);
714 PENDING_STMT (e
) = NULL_TREE
;
716 /* Add phi node entries for arguments. Not every PHI node corresponds to
717 a function argument (there may be PHI nodes for virtual definitions of the
718 eliminated calls), so we search for a PHI corresponding to each argument
719 rather than searching for which argument a PHI node corresponds to. */
721 for (param
= DECL_ARGUMENTS (current_function_decl
),
722 args
= TREE_OPERAND (stmt
, 1);
724 param
= TREE_CHAIN (param
),
725 args
= TREE_CHAIN (args
))
728 for (phi
= phi_nodes (first
); phi
; phi
= PHI_CHAIN (phi
))
729 if (param
== SSA_NAME_VAR (PHI_RESULT (phi
)))
732 /* The phi node indeed does not have to be there, in case the operand is
733 invariant in the function. */
737 add_phi_arg (&phi
, TREE_VALUE (args
), e
);
740 /* Add phi nodes for the call clobbered variables. */
741 FOR_EACH_SSA_MAYDEF_OPERAND (maydef
, mayuse
, orig_stmt
, iter
)
743 param
= SSA_NAME_VAR (DEF_FROM_PTR (maydef
));
744 for (phi
= phi_nodes (first
); phi
; phi
= PHI_CHAIN (phi
))
745 if (param
== SSA_NAME_VAR (PHI_RESULT (phi
)))
750 tree name
= var_ann (param
)->default_def
;
755 /* It may happen that the tag does not have a default_def in case
756 when all uses of it are dominated by a MUST_DEF. This however
757 means that it is not necessary to add a phi node for this
761 new_name
= make_ssa_name (param
, SSA_NAME_DEF_STMT (name
));
763 var_ann (param
)->default_def
= new_name
;
764 phi
= create_phi_node (name
, first
);
765 SSA_NAME_DEF_STMT (name
) = phi
;
766 add_phi_arg (&phi
, new_name
, EDGE_SUCC (ENTRY_BLOCK_PTR
, 0));
768 /* For all calls the same set of variables should be clobbered. This
769 means that there always should be the appropriate phi node except
770 for the first time we eliminate the call. */
771 gcc_assert (EDGE_COUNT (first
->preds
) <= 2);
774 add_phi_arg (&phi
, USE_FROM_PTR (mayuse
), e
);
777 /* Update the values of accumulators. */
778 adjust_accumulator_values (t
->call_bsi
, t
->mult
, t
->add
, e
);
780 call
= bsi_stmt (t
->call_bsi
);
781 if (TREE_CODE (call
) == MODIFY_EXPR
)
783 rslt
= TREE_OPERAND (call
, 0);
785 /* Result of the call will no longer be defined. So adjust the
786 SSA_NAME_DEF_STMT accordingly. */
787 SSA_NAME_DEF_STMT (rslt
) = build_empty_stmt ();
790 bsi_remove (&t
->call_bsi
);
794 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
795 mark the tailcalls for the sibcall optimization. */
798 optimize_tail_call (struct tailcall
*t
, bool opt_tailcalls
)
800 if (t
->tail_recursion
)
802 eliminate_tail_call (t
);
808 tree stmt
= bsi_stmt (t
->call_bsi
);
810 stmt
= get_call_expr_in (stmt
);
811 CALL_EXPR_TAILCALL (stmt
) = 1;
812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
814 fprintf (dump_file
, "Found tail call ");
815 print_generic_expr (dump_file
, stmt
, dump_flags
);
816 fprintf (dump_file
, " in bb %i\n", t
->call_block
->index
);
823 /* Optimizes tail calls in the function, turning the tail recursion
827 tree_optimize_tail_calls_1 (bool opt_tailcalls
)
830 bool phis_constructed
= false;
831 struct tailcall
*tailcalls
= NULL
, *act
, *next
;
832 bool changed
= false;
833 basic_block first
= EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->dest
;
834 tree stmt
, param
, ret_type
, tmp
, phi
;
837 if (!suitable_for_tail_opt_p ())
840 opt_tailcalls
= suitable_for_tail_call_opt_p ();
842 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
844 /* Only traverse the normal exits, i.e. those that end with return
846 stmt
= last_stmt (e
->src
);
849 && TREE_CODE (stmt
) == RETURN_EXPR
)
850 find_tail_calls (e
->src
, &tailcalls
);
853 /* Construct the phi nodes and accumulators if necessary. */
854 a_acc
= m_acc
= NULL_TREE
;
855 for (act
= tailcalls
; act
; act
= act
->next
)
857 if (!act
->tail_recursion
)
860 if (!phis_constructed
)
862 /* Ensure that there is only one predecessor of the block. */
863 if (EDGE_COUNT (first
->preds
) > 1)
864 first
= split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR
, 0));
866 /* Copy the args if needed. */
867 for (param
= DECL_ARGUMENTS (current_function_decl
);
869 param
= TREE_CHAIN (param
))
871 /* Also parameters that are only defined but never used need not
873 && (var_ann (param
)->default_def
874 && TREE_CODE (var_ann (param
)->default_def
) == SSA_NAME
))
876 tree name
= var_ann (param
)->default_def
;
877 tree new_name
= make_ssa_name (param
, SSA_NAME_DEF_STMT (name
));
880 var_ann (param
)->default_def
= new_name
;
881 phi
= create_phi_node (name
, first
);
882 SSA_NAME_DEF_STMT (name
) = phi
;
883 add_phi_arg (&phi
, new_name
, EDGE_PRED (first
, 0));
885 phis_constructed
= true;
888 if (act
->add
&& !a_acc
)
890 ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
892 tmp
= create_tmp_var (ret_type
, "add_acc");
893 add_referenced_tmp_var (tmp
);
895 phi
= create_phi_node (tmp
, first
);
897 /* RET_TYPE can be a float when -ffast-maths is
899 fold_convert (ret_type
, integer_zero_node
),
900 EDGE_PRED (first
, 0));
901 a_acc
= PHI_RESULT (phi
);
904 if (act
->mult
&& !m_acc
)
906 ret_type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
908 tmp
= create_tmp_var (ret_type
, "mult_acc");
909 add_referenced_tmp_var (tmp
);
911 phi
= create_phi_node (tmp
, first
);
913 /* RET_TYPE can be a float when -ffast-maths is
915 fold_convert (ret_type
, integer_one_node
),
916 EDGE_PRED (first
, 0));
917 m_acc
= PHI_RESULT (phi
);
921 for (; tailcalls
; tailcalls
= next
)
923 next
= tailcalls
->next
;
924 changed
|= optimize_tail_call (tailcalls
, opt_tailcalls
);
930 /* Modify the remaining return statements. */
931 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
933 stmt
= last_stmt (e
->src
);
936 && TREE_CODE (stmt
) == RETURN_EXPR
)
937 adjust_return_value (e
->src
, m_acc
, a_acc
);
943 free_dominance_info (CDI_DOMINATORS
);
949 execute_tail_recursion (void)
951 tree_optimize_tail_calls_1 (false);
955 gate_tail_calls (void)
957 return flag_optimize_sibling_calls
!= 0;
961 execute_tail_calls (void)
963 tree_optimize_tail_calls_1 (true);
966 struct tree_opt_pass pass_tail_recursion
=
970 execute_tail_recursion
, /* execute */
973 0, /* static_pass_number */
975 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
976 0, /* properties_provided */
977 0, /* properties_destroyed */
978 0, /* todo_flags_start */
979 TODO_dump_func
| TODO_verify_ssa
, /* todo_flags_finish */
983 struct tree_opt_pass pass_tail_calls
=
986 gate_tail_calls
, /* gate */
987 execute_tail_calls
, /* execute */
990 0, /* static_pass_number */
992 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
993 0, /* properties_provided */
994 0, /* properties_destroyed */
995 0, /* todo_flags_start */
996 TODO_dump_func
| TODO_verify_ssa
, /* todo_flags_finish */