2008-11-19 Andrew Stubbs <ams@codesourcery.com>
[official-gcc.git] / gcc / tree-tailcall.c
blob935b41941a02655c6a54392a4c9a899b3e1c6f5a
1 /* Tail call optimization on trees.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 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)
9 any later version.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "tree.h"
25 #include "rtl.h"
26 #include "tm_p.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "function.h"
30 #include "tree-flow.h"
31 #include "tree-dump.h"
32 #include "diagnostic.h"
33 #include "except.h"
34 #include "tree-pass.h"
35 #include "flags.h"
36 #include "langhooks.h"
37 #include "dbgcnt.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
47 int sum (int n)
49 if (n > 0)
50 return n + sum (n - 1);
51 else
52 return 0;
55 is transformed into
57 int sum (int n)
59 int acc = 0;
61 while (n > 0)
62 acc += n--;
64 return acc;
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
72 omit the accumulator.
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
85 are unchanged.
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. */
101 struct 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. */
107 bool tail_recursion;
109 /* The return value of the caller is mult * f + add, where f is the return
110 value of the call. */
111 tree mult, add;
113 /* Next tailcall in the chain. */
114 struct tailcall *next;
117 /* The variables holding the value of multiplicative and additive
118 accumulator. */
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). */
129 static bool
130 suitable_for_tail_opt_p (void)
132 referenced_var_iterator rvi;
133 tree var;
135 if (cfun->stdarg)
136 return false;
138 /* No local variable nor structure field should be call-used. We
139 ignore any kind of memory tag, as these are not real variables. */
141 FOR_EACH_REFERENCED_VAR (var, rvi)
143 if (!is_global_var (var)
144 && !MTAG_P (var)
145 && (gimple_aliases_computed_p (cfun)? is_call_used (var)
146 : TREE_ADDRESSABLE (var)))
147 return false;
150 return true;
152 /* Returns false when the function is not suitable for tail call optimization
153 from some reason (e.g. if it takes variable number of arguments).
154 This test must pass in addition to suitable_for_tail_opt_p in order to make
155 tail call discovery happen. */
157 static bool
158 suitable_for_tail_call_opt_p (void)
160 tree param;
162 /* alloca (until we have stack slot life analysis) inhibits
163 sibling call optimizations, but not tail recursion. */
164 if (cfun->calls_alloca)
165 return false;
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 ())
171 return false;
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 (cfun->calls_setjmp)
177 return false;
179 /* ??? It is OK if the argument of a function is taken in some cases,
180 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
181 for (param = DECL_ARGUMENTS (current_function_decl);
182 param;
183 param = TREE_CHAIN (param))
184 if (TREE_ADDRESSABLE (param))
185 return false;
187 return true;
190 /* Checks whether the expression EXPR in stmt AT is independent of the
191 statement pointed to by GSI (in a sense that we already know EXPR's value
192 at GSI). We use the fact that we are only called from the chain of
193 basic blocks that have only single successor. Returns the expression
194 containing the value of EXPR at GSI. */
196 static tree
197 independent_of_stmt_p (tree expr, gimple at, gimple_stmt_iterator gsi)
199 basic_block bb, call_bb, at_bb;
200 edge e;
201 edge_iterator ei;
203 if (is_gimple_min_invariant (expr))
204 return expr;
206 if (TREE_CODE (expr) != SSA_NAME)
207 return NULL_TREE;
209 /* Mark the blocks in the chain leading to the end. */
210 at_bb = gimple_bb (at);
211 call_bb = gimple_bb (gsi_stmt (gsi));
212 for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
213 bb->aux = &bb->aux;
214 bb->aux = &bb->aux;
216 while (1)
218 at = SSA_NAME_DEF_STMT (expr);
219 bb = gimple_bb (at);
221 /* The default definition or defined before the chain. */
222 if (!bb || !bb->aux)
223 break;
225 if (bb == call_bb)
227 for (; !gsi_end_p (gsi); gsi_next (&gsi))
228 if (gsi_stmt (gsi) == at)
229 break;
231 if (!gsi_end_p (gsi))
232 expr = NULL_TREE;
233 break;
236 if (gimple_code (at) != GIMPLE_PHI)
238 expr = NULL_TREE;
239 break;
242 FOR_EACH_EDGE (e, ei, bb->preds)
243 if (e->src->aux)
244 break;
245 gcc_assert (e);
247 expr = PHI_ARG_DEF_FROM_EDGE (at, e);
248 if (TREE_CODE (expr) != SSA_NAME)
250 /* The value is a constant. */
251 break;
255 /* Unmark the blocks. */
256 for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
257 bb->aux = NULL;
258 bb->aux = NULL;
260 return expr;
263 /* Simulates the effect of an assignment STMT on the return value of the tail
264 recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
265 additive factor for the real return value. */
267 static bool
268 process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
269 tree *a, tree *ass_var)
271 tree op0, op1, non_ass_var;
272 tree dest = gimple_assign_lhs (stmt);
273 enum tree_code code = gimple_assign_rhs_code (stmt);
274 enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
275 tree src_var = gimple_assign_rhs1 (stmt);
277 /* See if this is a simple copy operation of an SSA name to the function
278 result. In that case we may have a simple tail call. Ignore type
279 conversions that can never produce extra code between the function
280 call and the function return. */
281 if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt))
282 && (TREE_CODE (src_var) == SSA_NAME))
284 /* Reject a tailcall if the type conversion might need
285 additional code. */
286 if (gimple_assign_cast_p (stmt)
287 && TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var)))
288 return false;
290 if (src_var != *ass_var)
291 return false;
293 *ass_var = dest;
294 return true;
297 if (rhs_class != GIMPLE_BINARY_RHS)
298 return false;
300 /* Accumulator optimizations will reverse the order of operations.
301 We can only do that for floating-point types if we're assuming
302 that addition and multiplication are associative. */
303 if (!flag_associative_math)
304 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
305 return false;
307 /* We only handle the code like
309 x = call ();
310 y = m * x;
311 z = y + a;
312 return z;
314 TODO -- Extend it for cases where the linear transformation of the output
315 is expressed in a more complicated way. */
317 op0 = gimple_assign_rhs1 (stmt);
318 op1 = gimple_assign_rhs2 (stmt);
320 if (op0 == *ass_var
321 && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
323 else if (op1 == *ass_var
324 && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
326 else
327 return false;
329 switch (code)
331 case PLUS_EXPR:
332 /* There should be no previous addition. TODO -- it should be fairly
333 straightforward to lift this restriction -- just allow storing
334 more complicated expressions in *A, and gimplify it in
335 adjust_accumulator_values. */
336 if (*a)
337 return false;
338 *a = non_ass_var;
339 *ass_var = dest;
340 return true;
342 case MULT_EXPR:
343 /* Similar remark applies here. Handling multiplication after addition
344 is just slightly more complicated -- we need to multiply both *A and
345 *M. */
346 if (*a || *m)
347 return false;
348 *m = non_ass_var;
349 *ass_var = dest;
350 return true;
352 /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR,
353 POINTER_PLUS_EXPR). */
355 default:
356 return false;
360 /* Propagate VAR through phis on edge E. */
362 static tree
363 propagate_through_phis (tree var, edge e)
365 basic_block dest = e->dest;
366 gimple_stmt_iterator gsi;
368 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
370 gimple phi = gsi_stmt (gsi);
371 if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
372 return PHI_RESULT (phi);
374 return var;
377 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
378 added to the start of RET. */
380 static void
381 find_tail_calls (basic_block bb, struct tailcall **ret)
383 tree ass_var = NULL_TREE, ret_var, func, param;
384 gimple stmt, call = NULL;
385 gimple_stmt_iterator gsi, agsi;
386 bool tail_recursion;
387 struct tailcall *nw;
388 edge e;
389 tree m, a;
390 basic_block abb;
391 size_t idx;
393 if (!single_succ_p (bb))
394 return;
396 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
398 stmt = gsi_stmt (gsi);
400 /* Ignore labels. */
401 if (gimple_code (stmt) == GIMPLE_LABEL)
402 continue;
404 /* Check for a call. */
405 if (is_gimple_call (stmt))
407 call = stmt;
408 ass_var = gimple_call_lhs (stmt);
409 break;
412 /* If the statement has virtual or volatile operands, fail. */
413 if (!ZERO_SSA_OPERANDS (stmt, (SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS))
414 || gimple_has_volatile_ops (stmt)
415 || (!gimple_aliases_computed_p (cfun)
416 && gimple_references_memory_p (stmt)))
417 return;
420 if (gsi_end_p (gsi))
422 edge_iterator ei;
423 /* Recurse to the predecessors. */
424 FOR_EACH_EDGE (e, ei, bb->preds)
425 find_tail_calls (e->src, ret);
427 return;
430 /* If the LHS of our call is not just a simple register, we can't
431 transform this into a tail or sibling call. This situation happens,
432 in (e.g.) "*p = foo()" where foo returns a struct. In this case
433 we won't have a temporary here, but we need to carry out the side
434 effect anyway, so tailcall is impossible.
436 ??? In some situations (when the struct is returned in memory via
437 invisible argument) we could deal with this, e.g. by passing 'p'
438 itself as that argument to foo, but it's too early to do this here,
439 and expand_call() will not handle it anyway. If it ever can, then
440 we need to revisit this here, to allow that situation. */
441 if (ass_var && !is_gimple_reg (ass_var))
442 return;
444 /* We found the call, check whether it is suitable. */
445 tail_recursion = false;
446 func = gimple_call_fndecl (call);
447 if (func == current_function_decl)
449 tree arg;
450 for (param = DECL_ARGUMENTS (func), idx = 0;
451 param && idx < gimple_call_num_args (call);
452 param = TREE_CHAIN (param), idx ++)
454 arg = gimple_call_arg (call, idx);
455 if (param != arg)
457 /* Make sure there are no problems with copying. The parameter
458 have a copyable type and the two arguments must have reasonably
459 equivalent types. The latter requirement could be relaxed if
460 we emitted a suitable type conversion statement. */
461 if (!is_gimple_reg_type (TREE_TYPE (param))
462 || !useless_type_conversion_p (TREE_TYPE (param),
463 TREE_TYPE (arg)))
464 break;
466 /* The parameter should be a real operand, so that phi node
467 created for it at the start of the function has the meaning
468 of copying the value. This test implies is_gimple_reg_type
469 from the previous condition, however this one could be
470 relaxed by being more careful with copying the new value
471 of the parameter (emitting appropriate GIMPLE_ASSIGN and
472 updating the virtual operands). */
473 if (!is_gimple_reg (param))
474 break;
477 if (idx == gimple_call_num_args (call) && !param)
478 tail_recursion = true;
481 /* Now check the statements after the call. None of them has virtual
482 operands, so they may only depend on the call through its return
483 value. The return value should also be dependent on each of them,
484 since we are running after dce. */
485 m = NULL_TREE;
486 a = NULL_TREE;
488 abb = bb;
489 agsi = gsi;
490 while (1)
492 gsi_next (&agsi);
494 while (gsi_end_p (agsi))
496 ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
497 abb = single_succ (abb);
498 agsi = gsi_start_bb (abb);
501 stmt = gsi_stmt (agsi);
503 if (gimple_code (stmt) == GIMPLE_LABEL)
504 continue;
506 if (gimple_code (stmt) == GIMPLE_RETURN)
507 break;
509 if (gimple_code (stmt) != GIMPLE_ASSIGN)
510 return;
512 /* This is a gimple assign. */
513 if (! process_assignment (stmt, gsi, &m, &a, &ass_var))
514 return;
517 /* See if this is a tail call we can handle. */
518 ret_var = gimple_return_retval (stmt);
520 /* We may proceed if there either is no return value, or the return value
521 is identical to the call's return. */
522 if (ret_var
523 && (ret_var != ass_var))
524 return;
526 /* If this is not a tail recursive call, we cannot handle addends or
527 multiplicands. */
528 if (!tail_recursion && (m || a))
529 return;
531 nw = XNEW (struct tailcall);
533 nw->call_gsi = gsi;
535 nw->tail_recursion = tail_recursion;
537 nw->mult = m;
538 nw->add = a;
540 nw->next = *ret;
541 *ret = nw;
544 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
546 static void
547 add_successor_phi_arg (edge e, tree var, tree phi_arg)
549 gimple_stmt_iterator gsi;
551 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
552 if (PHI_RESULT (gsi_stmt (gsi)) == var)
553 break;
555 gcc_assert (!gsi_end_p (gsi));
556 add_phi_arg (gsi_stmt (gsi), phi_arg, e);
559 /* Creates a GIMPLE statement which computes the operation specified by
560 CODE, OP0 and OP1 to a new variable with name LABEL and inserts the
561 statement in the position specified by GSI and UPDATE. Returns the
562 tree node of the statement's result. */
564 static tree
565 adjust_return_value_with_ops (enum tree_code code, const char *label,
566 tree op0, tree op1, gimple_stmt_iterator gsi,
567 enum gsi_iterator_update update)
570 tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
571 tree tmp = create_tmp_var (ret_type, label);
572 gimple stmt = gimple_build_assign_with_ops (code, tmp, op0, op1);
573 tree result;
575 add_referenced_var (tmp);
576 result = make_ssa_name (tmp, stmt);
577 gimple_assign_set_lhs (stmt, result);
578 update_stmt (stmt);
579 gsi_insert_before (&gsi, stmt, update);
580 return result;
583 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
584 the computation specified by CODE and OP1 and insert the statement
585 at the position specified by GSI as a new statement. Returns new SSA name
586 of updated accumulator. */
588 static tree
589 update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
590 gimple_stmt_iterator gsi)
592 gimple stmt = gimple_build_assign_with_ops (code, SSA_NAME_VAR (acc), acc,
593 op1);
594 tree var = make_ssa_name (SSA_NAME_VAR (acc), stmt);
595 gimple_assign_set_lhs (stmt, var);
596 update_stmt (stmt);
597 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
598 return var;
601 /* Adjust the accumulator values according to A and M after GSI, and update
602 the phi nodes on edge BACK. */
604 static void
605 adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
607 tree var, a_acc_arg = a_acc, m_acc_arg = m_acc;
609 if (a)
611 if (m_acc)
613 if (integer_onep (a))
614 var = m_acc;
615 else
616 var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
617 a, gsi, GSI_NEW_STMT);
619 else
620 var = a;
622 a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
625 if (m)
626 m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
628 if (a_acc)
629 add_successor_phi_arg (back, a_acc, a_acc_arg);
631 if (m_acc)
632 add_successor_phi_arg (back, m_acc, m_acc_arg);
635 /* Adjust value of the return at the end of BB according to M and A
636 accumulators. */
638 static void
639 adjust_return_value (basic_block bb, tree m, tree a)
641 tree retval;
642 gimple ret_stmt = gimple_seq_last_stmt (bb_seq (bb));
643 gimple_stmt_iterator gsi = gsi_last_bb (bb);
645 gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
647 retval = gimple_return_retval (ret_stmt);
648 if (!retval || retval == error_mark_node)
649 return;
651 if (m)
652 retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
653 gsi, GSI_SAME_STMT);
654 if (a)
655 retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
656 gsi, GSI_SAME_STMT);
657 gimple_return_set_retval (ret_stmt, retval);
658 update_stmt (ret_stmt);
661 /* Subtract COUNT and FREQUENCY from the basic block and it's
662 outgoing edge. */
663 static void
664 decrease_profile (basic_block bb, gcov_type count, int frequency)
666 edge e;
667 bb->count -= count;
668 if (bb->count < 0)
669 bb->count = 0;
670 bb->frequency -= frequency;
671 if (bb->frequency < 0)
672 bb->frequency = 0;
673 if (!single_succ_p (bb))
675 gcc_assert (!EDGE_COUNT (bb->succs));
676 return;
678 e = single_succ_edge (bb);
679 e->count -= count;
680 if (e->count < 0)
681 e->count = 0;
684 /* Returns true if argument PARAM of the tail recursive call needs to be copied
685 when the call is eliminated. */
687 static bool
688 arg_needs_copy_p (tree param)
690 tree def;
692 if (!is_gimple_reg (param) || !var_ann (param))
693 return false;
695 /* Parameters that are only defined but never used need not be copied. */
696 def = gimple_default_def (cfun, param);
697 if (!def)
698 return false;
700 return true;
703 /* Eliminates tail call described by T. TMP_VARS is a list of
704 temporary variables used to copy the function arguments. */
706 static void
707 eliminate_tail_call (struct tailcall *t)
709 tree param, rslt;
710 gimple stmt, call;
711 tree arg;
712 size_t idx;
713 basic_block bb, first;
714 edge e;
715 gimple phi;
716 gimple_stmt_iterator gsi;
717 gimple orig_stmt;
719 stmt = orig_stmt = gsi_stmt (t->call_gsi);
720 bb = gsi_bb (t->call_gsi);
722 if (dump_file && (dump_flags & TDF_DETAILS))
724 fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
725 bb->index);
726 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
727 fprintf (dump_file, "\n");
730 gcc_assert (is_gimple_call (stmt));
732 first = single_succ (ENTRY_BLOCK_PTR);
734 /* Remove the code after call_gsi that will become unreachable. The
735 possibly unreachable code in other blocks is removed later in
736 cfg cleanup. */
737 gsi = t->call_gsi;
738 gsi_next (&gsi);
739 while (!gsi_end_p (gsi))
741 gimple t = gsi_stmt (gsi);
742 /* Do not remove the return statement, so that redirect_edge_and_branch
743 sees how the block ends. */
744 if (gimple_code (t) == GIMPLE_RETURN)
745 break;
747 gsi_remove (&gsi, true);
748 release_defs (t);
751 /* Number of executions of function has reduced by the tailcall. */
752 e = single_succ_edge (gsi_bb (t->call_gsi));
753 decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
754 decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
755 if (e->dest != EXIT_BLOCK_PTR)
756 decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
758 /* Replace the call by a jump to the start of function. */
759 e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)),
760 first);
761 gcc_assert (e);
762 PENDING_STMT (e) = NULL;
764 /* Add phi node entries for arguments. The ordering of the phi nodes should
765 be the same as the ordering of the arguments. */
766 for (param = DECL_ARGUMENTS (current_function_decl),
767 idx = 0, gsi = gsi_start_phis (first);
768 param;
769 param = TREE_CHAIN (param), idx++)
771 if (!arg_needs_copy_p (param))
772 continue;
774 arg = gimple_call_arg (stmt, idx);
775 phi = gsi_stmt (gsi);
776 gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
778 add_phi_arg (phi, arg, e);
779 gsi_next (&gsi);
782 /* Update the values of accumulators. */
783 adjust_accumulator_values (t->call_gsi, t->mult, t->add, e);
785 call = gsi_stmt (t->call_gsi);
786 rslt = gimple_call_lhs (call);
787 if (rslt != NULL_TREE)
789 /* Result of the call will no longer be defined. So adjust the
790 SSA_NAME_DEF_STMT accordingly. */
791 SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
794 gsi_remove (&t->call_gsi, true);
795 release_defs (call);
798 /* Add phi nodes for the virtual operands defined in the function to the
799 header of the loop created by tail recursion elimination.
801 Originally, we used to add phi nodes only for call clobbered variables,
802 as the value of the non-call clobbered ones obviously cannot be used
803 or changed within the recursive call. However, the local variables
804 from multiple calls now share the same location, so the virtual ssa form
805 requires us to say that the location dies on further iterations of the loop,
806 which requires adding phi nodes.
808 static void
809 add_virtual_phis (void)
811 referenced_var_iterator rvi;
812 tree var;
814 /* The problematic part is that there is no way how to know what
815 to put into phi nodes (there in fact does not have to be such
816 ssa name available). A solution would be to have an artificial
817 use/kill for all virtual operands in EXIT node. Unless we have
818 this, we cannot do much better than to rebuild the ssa form for
819 possibly affected virtual ssa names from scratch. */
821 FOR_EACH_REFERENCED_VAR (var, rvi)
823 if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
824 mark_sym_for_renaming (var);
828 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
829 mark the tailcalls for the sibcall optimization. */
831 static bool
832 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
834 if (t->tail_recursion)
836 eliminate_tail_call (t);
837 return true;
840 if (opt_tailcalls)
842 gimple stmt = gsi_stmt (t->call_gsi);
844 gimple_call_set_tail (stmt, true);
845 if (dump_file && (dump_flags & TDF_DETAILS))
847 fprintf (dump_file, "Found tail call ");
848 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
849 fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
853 return false;
856 /* Creates a tail-call accumulator of the same type as the return type of the
857 current function. LABEL is the name used to creating the temporary
858 variable for the accumulator. The accumulator will be inserted in the
859 phis of a basic block BB with single predecessor with an initial value
860 INIT converted to the current function return type. */
862 static tree
863 create_tailcall_accumulator (const char *label, basic_block bb, tree init)
865 tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
866 tree tmp = create_tmp_var (ret_type, label);
867 gimple phi;
869 add_referenced_var (tmp);
870 phi = create_phi_node (tmp, bb);
871 /* RET_TYPE can be a float when -ffast-maths is enabled. */
872 add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb));
873 return PHI_RESULT (phi);
876 /* Optimizes tail calls in the function, turning the tail recursion
877 into iteration. */
879 static unsigned int
880 tree_optimize_tail_calls_1 (bool opt_tailcalls)
882 edge e;
883 bool phis_constructed = false;
884 struct tailcall *tailcalls = NULL, *act, *next;
885 bool changed = false;
886 basic_block first = single_succ (ENTRY_BLOCK_PTR);
887 tree param;
888 gimple stmt;
889 edge_iterator ei;
891 if (!suitable_for_tail_opt_p ())
892 return 0;
893 if (opt_tailcalls)
894 opt_tailcalls = suitable_for_tail_call_opt_p ();
896 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
898 /* Only traverse the normal exits, i.e. those that end with return
899 statement. */
900 stmt = last_stmt (e->src);
902 if (stmt
903 && gimple_code (stmt) == GIMPLE_RETURN)
904 find_tail_calls (e->src, &tailcalls);
907 /* Construct the phi nodes and accumulators if necessary. */
908 a_acc = m_acc = NULL_TREE;
909 for (act = tailcalls; act; act = act->next)
911 if (!act->tail_recursion)
912 continue;
914 if (!phis_constructed)
916 /* Ensure that there is only one predecessor of the block. */
917 if (!single_pred_p (first))
918 first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
920 /* Copy the args if needed. */
921 for (param = DECL_ARGUMENTS (current_function_decl);
922 param;
923 param = TREE_CHAIN (param))
924 if (arg_needs_copy_p (param))
926 tree name = gimple_default_def (cfun, param);
927 tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
928 gimple phi;
930 set_default_def (param, new_name);
931 phi = create_phi_node (name, first);
932 SSA_NAME_DEF_STMT (name) = phi;
933 add_phi_arg (phi, new_name, single_pred_edge (first));
935 phis_constructed = true;
938 if (act->add && !a_acc)
939 a_acc = create_tailcall_accumulator ("add_acc", first,
940 integer_zero_node);
942 if (act->mult && !m_acc)
943 m_acc = create_tailcall_accumulator ("mult_acc", first,
944 integer_one_node);
947 for (; tailcalls; tailcalls = next)
949 next = tailcalls->next;
950 changed |= optimize_tail_call (tailcalls, opt_tailcalls);
951 free (tailcalls);
954 if (a_acc || m_acc)
956 /* Modify the remaining return statements. */
957 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
959 stmt = last_stmt (e->src);
961 if (stmt
962 && gimple_code (stmt) == GIMPLE_RETURN)
963 adjust_return_value (e->src, m_acc, a_acc);
967 if (changed)
968 free_dominance_info (CDI_DOMINATORS);
970 if (phis_constructed)
971 add_virtual_phis ();
972 if (changed)
973 return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
974 return 0;
977 static unsigned int
978 execute_tail_recursion (void)
980 return tree_optimize_tail_calls_1 (false);
983 static bool
984 gate_tail_calls (void)
986 return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
989 static unsigned int
990 execute_tail_calls (void)
992 return tree_optimize_tail_calls_1 (true);
995 struct gimple_opt_pass pass_tail_recursion =
998 GIMPLE_PASS,
999 "tailr", /* name */
1000 gate_tail_calls, /* gate */
1001 execute_tail_recursion, /* execute */
1002 NULL, /* sub */
1003 NULL, /* next */
1004 0, /* static_pass_number */
1005 0, /* tv_id */
1006 PROP_cfg | PROP_ssa, /* properties_required */
1007 0, /* properties_provided */
1008 0, /* properties_destroyed */
1009 0, /* todo_flags_start */
1010 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
1014 struct gimple_opt_pass pass_tail_calls =
1017 GIMPLE_PASS,
1018 "tailc", /* name */
1019 gate_tail_calls, /* gate */
1020 execute_tail_calls, /* execute */
1021 NULL, /* sub */
1022 NULL, /* next */
1023 0, /* static_pass_number */
1024 0, /* tv_id */
1025 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1026 0, /* properties_provided */
1027 0, /* properties_destroyed */
1028 0, /* todo_flags_start */
1029 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */