CommitLineData
SS
1/* Tail call optimization on trees.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
3 Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "tm.h"
25#include "tree.h"
26#include "rtl.h"
27#include "tm_p.h"
28#include "hard-reg-set.h"
29#include "basic-block.h"
30#include "function.h"
31#include "tree-flow.h"
32#include "tree-dump.h"
33#include "diagnostic.h"
34#include "except.h"
35#include "tree-pass.h"
36#include "flags.h"
37#include "langhooks.h"
38#include "dbgcnt.h"
39
40/* The file implements the tail recursion elimination. It is also used to
41 analyze the tail calls in general, passing the results to the rtl level
42 where they are used for sibcall optimization.
43
44 In addition to the standard tail recursion elimination, we handle the most
45 trivial cases of making the call tail recursive by creating accumulators.
46 For example the following function
47
48 int sum (int n)
49 {
50 if (n > 0)
51 return n + sum (n - 1);
52 else
53 return 0;
54 }
55
56 is transformed into
57
58 int sum (int n)
59 {
60 int acc = 0;
61
62 while (n > 0)
63 acc += n--;
64
65 return acc;
66 }
67
68 To do this, we maintain two accumulators (a_acc and m_acc) that indicate
69 when we reach the return x statement, we should return a_acc + x * m_acc
70 instead. They are initially initialized to 0 and 1, respectively,
71 so the semantics of the function is obviously preserved. If we are
72 guaranteed that the value of the accumulator never change, we
73 omit the accumulator.
74
75 There are three cases how the function may exit. The first one is
77 (the second case is actually a special case of the third one and we
78 present it separately just for clarity):
79
80 1) Just return x, where x is not in any of the remaining special shapes.
81 We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
82
83 2) return f (...), where f is the current function, is rewritten in a
84 classical tail-recursion elimination way, into assignment of arguments
85 and jump to the start of the function. Values of the accumulators
86 are unchanged.
87
88 3) return a + m * f(...), where a and m do not depend on call to f.
89 To preserve the semantics described before we want this to be rewritten
90 in such a way that we finally return
91
92 a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
93
94 I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
95 eliminate the tail call to f. Special cases when the value is just
96 added or just multiplied are obtained by setting a = 0 or m = 1.
97
98 TODO -- it is possible to do similar tricks for other operations. */
99
100/* A structure that describes the tailcall. */
101
102struct tailcall
103{
104 /* The iterator pointing to the call statement. */
105 gimple_stmt_iterator call_gsi;
106
107 /* True if it is a call to the current function. */
108 bool tail_recursion;
109
110 /* The return value of the caller is mult * f + add, where f is the return
111 value of the call. */
113
114 /* Next tailcall in the chain. */
115 struct tailcall *next;
116};
117
118/* The variables holding the value of multiplicative and additive
119 accumulator. */
120static tree m_acc, a_acc;
121
122static bool suitable_for_tail_opt_p (void);
123static bool optimize_tail_call (struct tailcall *, bool);
124static void eliminate_tail_call (struct tailcall *);
125static void find_tail_calls (basic_block, struct tailcall **);
126
127/* Returns false when the function is not suitable for tail call optimization
128 from some reason (e.g. if it takes variable number of arguments). */
129
130static bool
131suitable_for_tail_opt_p (void)
132{
133 referenced_var_iterator rvi;
134 tree var;
135
136 if (cfun->stdarg)
137 return false;
138
139 /* No local variable nor structure field should be call-used. We
140 ignore any kind of memory tag, as these are not real variables. */
141
142 FOR_EACH_REFERENCED_VAR (var, rvi)
143 {
144 if (!is_global_var (var)
145 && !MTAG_P (var)
146 && (gimple_aliases_computed_p (cfun)? is_call_used (var)
148 return false;
149 }
150
151 return true;
152}
153/* Returns false when the function is not suitable for tail call optimization
154 from some reason (e.g. if it takes variable number of arguments).
155 This test must pass in addition to suitable_for_tail_opt_p in order to make
156 tail call discovery happen. */
157
158static bool
159suitable_for_tail_call_opt_p (void)
160{
161 tree param;
162
163 /* alloca (until we have stack slot life analysis) inhibits
164 sibling call optimizations, but not tail recursion. */
165 if (cfun->calls_alloca)
166 return false;
167
168 /* If we are using sjlj exceptions, we may need to add a call to
169 _Unwind_SjLj_Unregister at exit of the function. Which means
170 that we cannot do any sibcall transformations. */
171 if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ())
172 return false;
173
174 /* Any function that calls setjmp might have longjmp called from
175 any called function. ??? We really should represent this
176 properly in the CFG so that this needn't be special cased. */
177 if (cfun->calls_setjmp)
178 return false;
179
180 /* ??? It is OK if the argument of a function is taken in some cases,
181 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
182 for (param = DECL_ARGUMENTS (current_function_decl);
183 param;
184 param = TREE_CHAIN (param))
186 return false;
187
188 return true;
189}
190
191/* Checks whether the expression EXPR in stmt AT is independent of the
192 statement pointed to by GSI (in a sense that we already know EXPR's value
193 at GSI). We use the fact that we are only called from the chain of
194 basic blocks that have only single successor. Returns the expression
195 containing the value of EXPR at GSI. */
196
197static tree
198independent_of_stmt_p (tree expr, gimple at, gimple_stmt_iterator gsi)
199{
200 basic_block bb, call_bb, at_bb;
201 edge e;
202 edge_iterator ei;
203
204 if (is_gimple_min_invariant (expr))
205 return expr;
206
207 if (TREE_CODE (expr) != SSA_NAME)
208 return NULL_TREE;
209
210 /* Mark the blocks in the chain leading to the end. */
211 at_bb = gimple_bb (at);
212 call_bb = gimple_bb (gsi_stmt (gsi));
213 for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
214 bb->aux = &bb->aux;
215 bb->aux = &bb->aux;
216
217 while (1)
218 {
219 at = SSA_NAME_DEF_STMT (expr);
220 bb = gimple_bb (at);
221
222 /* The default definition or defined before the chain. */
223 if (!bb || !bb->aux)
224 break;
225
226 if (bb == call_bb)
227 {
228 for (; !gsi_end_p (gsi); gsi_next (&gsi))
229 if (gsi_stmt (gsi) == at)
230 break;
231
232 if (!gsi_end_p (gsi))
233 expr = NULL_TREE;
234 break;
235 }
236
237 if (gimple_code (at) != GIMPLE_PHI)
238 {
239 expr = NULL_TREE;
240 break;
241 }
242
243 FOR_EACH_EDGE (e, ei, bb->preds)
244 if (e->src->aux)
245 break;
246 gcc_assert (e);
247
248 expr = PHI_ARG_DEF_FROM_EDGE (at, e);
249 if (TREE_CODE (expr) != SSA_NAME)
250 {
251 /* The value is a constant. */
252 break;
253 }
254 }
255
256 /* Unmark the blocks. */
257 for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
258 bb->aux = NULL;
259 bb->aux = NULL;
260
261 return expr;
262}
263
264/* Simulates the effect of an assignment STMT on the return value of the tail
265 recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
266 additive factor for the real return value. */
267
268static bool
269process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
270 tree *a, tree *ass_var)
271{
272 tree op0, op1, non_ass_var;
273 tree dest = gimple_assign_lhs (stmt);
274 enum tree_code code = gimple_assign_rhs_code (stmt);
275 enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
276 tree src_var = gimple_assign_rhs1 (stmt);
277
278 /* See if this is a simple copy operation of an SSA name to the function
279 result. In that case we may have a simple tail call. Ignore type
280 conversions that can never produce extra code between the function
281 call and the function return. */
282 if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt))
283 && (TREE_CODE (src_var) == SSA_NAME))
284 {
285 /* Reject a tailcall if the type conversion might need
287 if (gimple_assign_cast_p (stmt)
288 && TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var)))
289 return false;
290
291 if (src_var != *ass_var)
292 return false;
293
294 *ass_var = dest;
295 return true;
296 }
297
298 if (rhs_class != GIMPLE_BINARY_RHS)
299 return false;
300
301 /* Accumulator optimizations will reverse the order of operations.
302 We can only do that for floating-point types if we're assuming
303 that addition and multiplication are associative. */
304 if (!flag_associative_math)
305 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
306 return false;
307
308 /* We only handle the code like
309
310 x = call ();
311 y = m * x;
312 z = y + a;
313 return z;
314
315 TODO -- Extend it for cases where the linear transformation of the output
316 is expressed in a more complicated way. */
317
318 op0 = gimple_assign_rhs1 (stmt);
319 op1 = gimple_assign_rhs2 (stmt);
320
321 if (op0 == *ass_var
322 && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
323 ;
324 else if (op1 == *ass_var
325 && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
326 ;
327 else
328 return false;
329
330 switch (code)
331 {
332 case PLUS_EXPR:
333 /* There should be no previous addition. TODO -- it should be fairly
334 straightforward to lift this restriction -- just allow storing
335 more complicated expressions in *A, and gimplify it in
337 if (*a)
338 return false;
339 *a = non_ass_var;
340 *ass_var = dest;
341 return true;
342
343 case MULT_EXPR:
344 /* Similar remark applies here. Handling multiplication after addition
345 is just slightly more complicated -- we need to multiply both *A and
346 *M. */
347 if (*a || *m)
348 return false;
349 *m = non_ass_var;
350 *ass_var = dest;
351 return true;
352
353 /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR,
354 POINTER_PLUS_EXPR). */
355
356 default:
357 return false;
358 }
359}
360
361/* Propagate VAR through phis on edge E. */
362
363static tree
364propagate_through_phis (tree var, edge e)
365{
366 basic_block dest = e->dest;
367 gimple_stmt_iterator gsi;
368
369 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
370 {
371 gimple phi = gsi_stmt (gsi);
372 if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
373 return PHI_RESULT (phi);
374 }
375 return var;
376}
377
378/* Finds tailcalls falling into basic block BB. The list of found tailcalls is
379 added to the start of RET. */
380
381static void
382find_tail_calls (basic_block bb, struct tailcall **ret)
383{
384 tree ass_var = NULL_TREE, ret_var, func, param;
385 gimple stmt, call = NULL;
386 gimple_stmt_iterator gsi, agsi;
387 bool tail_recursion;
388 struct tailcall *nw;
389 edge e;
390 tree m, a;
391 basic_block abb;
392 size_t idx;
393
394 if (!single_succ_p (bb))
395 return;
396
397 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
398 {
399 stmt = gsi_stmt (gsi);
400
401 /* Ignore labels. */
402 if (gimple_code (stmt) == GIMPLE_LABEL)
403 continue;
404
405 /* Check for a call. */
406 if (is_gimple_call (stmt))
407 {
408 call = stmt;
409 ass_var = gimple_call_lhs (stmt);
410 break;
411 }
412
413 /* If the statement has virtual or volatile operands, fail. */
414 if (!ZERO_SSA_OPERANDS (stmt, (SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS))
415 || gimple_has_volatile_ops (stmt)
416 || (!gimple_aliases_computed_p (cfun)
417 && gimple_references_memory_p (stmt)))
418 return;
419 }
420
421 if (gsi_end_p (gsi))
422 {
423 edge_iterator ei;
424 /* Recurse to the predecessors. */
425 FOR_EACH_EDGE (e, ei, bb->preds)
426 find_tail_calls (e->src, ret);
427
428 return;
429 }
430
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.
436
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))
443 return;
444
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)
449 {
450 tree arg;
451 for (param = DECL_ARGUMENTS (func), idx = 0;
452 param && idx < gimple_call_num_args (call);
453 param = TREE_CHAIN (param), idx ++)
454 {
455 arg = gimple_call_arg (call, idx);
456 if (param != arg)
457 {
458 /* Make sure there are no problems with copying. The parameter
459 have a copyable type and the two arguments must have reasonably
460 equivalent types. The latter requirement could be relaxed if
461 we emitted a suitable type conversion statement. */
462 if (!is_gimple_reg_type (TREE_TYPE (param))
463 || !useless_type_conversion_p (TREE_TYPE (param),
464 TREE_TYPE (arg)))
465 break;
466
467 /* The parameter should be a real operand, so that phi node
468 created for it at the start of the function has the meaning
469 of copying the value. This test implies is_gimple_reg_type
470 from the previous condition, however this one could be
471 relaxed by being more careful with copying the new value
472 of the parameter (emitting appropriate GIMPLE_ASSIGN and
473 updating the virtual operands). */
474 if (!is_gimple_reg (param))
475 break;
476 }
477 }
478 if (idx == gimple_call_num_args (call) && !param)
479 tail_recursion = true;
480 }
481
482 /* Now check the statements after the call. None of them has virtual
483 operands, so they may only depend on the call through its return
484 value. The return value should also be dependent on each of them,
485 since we are running after dce. */
486 m = NULL_TREE;
487 a = NULL_TREE;
488
489 abb = bb;
490 agsi = gsi;
491 while (1)
492 {
493 gsi_next (&agsi);
494
495 while (gsi_end_p (agsi))
496 {
497 ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
498 abb = single_succ (abb);
499 agsi = gsi_start_bb (abb);
500 }
501
502 stmt = gsi_stmt (agsi);
503
504 if (gimple_code (stmt) == GIMPLE_LABEL)
505 continue;
506
507 if (gimple_code (stmt) == GIMPLE_RETURN)
508 break;
509
510 if (gimple_code (stmt) != GIMPLE_ASSIGN)
511 return;
512
513 /* This is a gimple assign. */
514 if (! process_assignment (stmt, gsi, &m, &a, &ass_var))
515 return;
516 }
517
518 /* See if this is a tail call we can handle. */
519 ret_var = gimple_return_retval (stmt);
520
521 /* We may proceed if there either is no return value, or the return value
522 is identical to the call's return. */
523 if (ret_var
524 && (ret_var != ass_var))
525 return;
526
527 /* If this is not a tail recursive call, we cannot handle addends or
528 multiplicands. */
529 if (!tail_recursion && (m || a))
530 return;
531
532 nw = XNEW (struct tailcall);
533
534 nw->call_gsi = gsi;
535
536 nw->tail_recursion = tail_recursion;
537
538 nw->mult = m;
540
541 nw->next = *ret;
542 *ret = nw;
543}
544
545/* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
546
547static void
548add_successor_phi_arg (edge e, tree var, tree phi_arg)
549{
550 gimple_stmt_iterator gsi;
551
552 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
553 if (PHI_RESULT (gsi_stmt (gsi)) == var)
554 break;
555
556 gcc_assert (!gsi_end_p (gsi));
557 add_phi_arg (gsi_stmt (gsi), phi_arg, e);
558}
559
560/* Creates a GIMPLE statement which computes the operation specified by
561 CODE, OP0 and OP1 to a new variable with name LABEL and inserts the
562 statement in the position specified by GSI and UPDATE. Returns the
563 tree node of the statement's result. */
564
565static tree
566adjust_return_value_with_ops (enum tree_code code, const char *label,
567 tree op0, tree op1, gimple_stmt_iterator gsi,
568 enum gsi_iterator_update update)
569{
570
571 tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
572 tree tmp = create_tmp_var (ret_type, label);
573 gimple stmt = gimple_build_assign_with_ops (code, tmp, op0, op1);
574 tree result;
575
576 if (TREE_CODE (ret_type) == COMPLEX_TYPE
577 || TREE_CODE (ret_type) == VECTOR_TYPE)
578 DECL_GIMPLE_REG_P (tmp) = 1;
580 result = make_ssa_name (tmp, stmt);
581 gimple_assign_set_lhs (stmt, result);
582 update_stmt (stmt);
583 gsi_insert_before (&gsi, stmt, update);
584 return result;
585}
586
587/* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
588 the computation specified by CODE and OP1 and insert the statement
589 at the position specified by GSI as a new statement. Returns new SSA name
590 of updated accumulator. */
591
592static tree
593update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
594 gimple_stmt_iterator gsi)
595{
596 gimple stmt = gimple_build_assign_with_ops (code, SSA_NAME_VAR (acc), acc,
597 op1);
598 tree var = make_ssa_name (SSA_NAME_VAR (acc), stmt);
599 gimple_assign_set_lhs (stmt, var);
600 update_stmt (stmt);
601 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
602 return var;
603}
604
605/* Adjust the accumulator values according to A and M after GSI, and update
606 the phi nodes on edge BACK. */
607
608static void
609adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
610{
611 tree var, a_acc_arg = a_acc, m_acc_arg = m_acc;
612
613 if (a)
614 {
615 if (m_acc)
616 {
617 if (integer_onep (a))
618 var = m_acc;
619 else
620 var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
621 a, gsi, GSI_NEW_STMT);
622 }
623 else
624 var = a;
625
626 a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
627 }
628
629 if (m)
630 m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
631
632 if (a_acc)
634
635 if (m_acc)
637}
638
639/* Adjust value of the return at the end of BB according to M and A
640 accumulators. */
641
642static void
643adjust_return_value (basic_block bb, tree m, tree a)
644{
645 tree retval;
646 gimple ret_stmt = gimple_seq_last_stmt (bb_seq (bb));
647 gimple_stmt_iterator gsi = gsi_last_bb (bb);
648
649 gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
650
651 retval = gimple_return_retval (ret_stmt);
652 if (!retval || retval == error_mark_node)
653 return;
654
655 if (m)
656 retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
657 gsi, GSI_SAME_STMT);
658 if (a)
659 retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
660 gsi, GSI_SAME_STMT);
661 gimple_return_set_retval (ret_stmt, retval);
662 update_stmt (ret_stmt);
663}
664
665/* Subtract COUNT and FREQUENCY from the basic block and it's
666 outgoing edge. */
667static void
668decrease_profile (basic_block bb, gcov_type count, int frequency)
669{
670 edge e;
671 bb->count -= count;
672 if (bb->count < 0)
673 bb->count = 0;
674 bb->frequency -= frequency;
675 if (bb->frequency < 0)
676 bb->frequency = 0;
677 if (!single_succ_p (bb))
678 {
679 gcc_assert (!EDGE_COUNT (bb->succs));
680 return;
681 }
682 e = single_succ_edge (bb);
683 e->count -= count;
684 if (e->count < 0)
685 e->count = 0;
686}
687
688/* Returns true if argument PARAM of the tail recursive call needs to be copied
689 when the call is eliminated. */
690
691static bool
692arg_needs_copy_p (tree param)
693{
694 tree def;
695
696 if (!is_gimple_reg (param) || !var_ann (param))
697 return false;
698
699 /* Parameters that are only defined but never used need not be copied. */
700 def = gimple_default_def (cfun, param);
701 if (!def)
702 return false;
703
704 return true;
705}
706
707/* Eliminates tail call described by T. TMP_VARS is a list of
708 temporary variables used to copy the function arguments. */
709
710static void
711eliminate_tail_call (struct tailcall *t)
712{
713 tree param, rslt;
714 gimple stmt, call;
715 tree arg;
716 size_t idx;
717 basic_block bb, first;
718 edge e;
719 gimple phi;
720 gimple_stmt_iterator gsi;
721 gimple orig_stmt;
722
723 stmt = orig_stmt = gsi_stmt (t->call_gsi);
724 bb = gsi_bb (t->call_gsi);
725
726 if (dump_file && (dump_flags & TDF_DETAILS))
727 {
728 fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
729 bb->index);
730 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
731 fprintf (dump_file, "\n");
732 }
733
734 gcc_assert (is_gimple_call (stmt));
735
736 first = single_succ (ENTRY_BLOCK_PTR);
737
738 /* Remove the code after call_gsi that will become unreachable. The
739 possibly unreachable code in other blocks is removed later in
740 cfg cleanup. */
741 gsi = t->call_gsi;
742 gsi_next (&gsi);
743 while (!gsi_end_p (gsi))
744 {
745 gimple t = gsi_stmt (gsi);
746 /* Do not remove the return statement, so that redirect_edge_and_branch
747 sees how the block ends. */
748 if (gimple_code (t) == GIMPLE_RETURN)
749 break;
750
751 gsi_remove (&gsi, true);
752 release_defs (t);
753 }
754
755 /* Number of executions of function has reduced by the tailcall. */
756 e = single_succ_edge (gsi_bb (t->call_gsi));
757 decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
758 decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
759 if (e->dest != EXIT_BLOCK_PTR)
760 decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
761
762 /* Replace the call by a jump to the start of function. */
763 e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)),
764 first);
765 gcc_assert (e);
766 PENDING_STMT (e) = NULL;
767
768 /* Add phi node entries for arguments. The ordering of the phi nodes should
769 be the same as the ordering of the arguments. */
770 for (param = DECL_ARGUMENTS (current_function_decl),
771 idx = 0, gsi = gsi_start_phis (first);
772 param;
773 param = TREE_CHAIN (param), idx++)
774 {
775 if (!arg_needs_copy_p (param))
776 continue;
777
778 arg = gimple_call_arg (stmt, idx);
779 phi = gsi_stmt (gsi);
780 gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
781
783 gsi_next (&gsi);
784 }
785
786 /* Update the values of accumulators. */
788
789 call = gsi_stmt (t->call_gsi);
790 rslt = gimple_call_lhs (call);
791 if (rslt != NULL_TREE)
792 {
793 /* Result of the call will no longer be defined. So adjust the
794 SSA_NAME_DEF_STMT accordingly. */
795 SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
796 }
797
798 gsi_remove (&t->call_gsi, true);
799 release_defs (call);
800}
801
802/* Add phi nodes for the virtual operands defined in the function to the
803 header of the loop created by tail recursion elimination.
804
805 Originally, we used to add phi nodes only for call clobbered variables,
806 as the value of the non-call clobbered ones obviously cannot be used
807 or changed within the recursive call. However, the local variables
808 from multiple calls now share the same location, so the virtual ssa form
809 requires us to say that the location dies on further iterations of the loop,
810 which requires adding phi nodes.
811*/
812static void
814{
815 referenced_var_iterator rvi;
816 tree var;
817
818 /* The problematic part is that there is no way how to know what
819 to put into phi nodes (there in fact does not have to be such
820 ssa name available). A solution would be to have an artificial
821 use/kill for all virtual operands in EXIT node. Unless we have
822 this, we cannot do much better than to rebuild the ssa form for
823 possibly affected virtual ssa names from scratch. */
824
825 FOR_EACH_REFERENCED_VAR (var, rvi)
826 {
827 if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
828 mark_sym_for_renaming (var);
829 }
830}
831
832/* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
833 mark the tailcalls for the sibcall optimization. */
834
835static bool
836optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
837{
838 if (t->tail_recursion)
839 {
840 eliminate_tail_call (t);
841 return true;
842 }
843
844 if (opt_tailcalls)
845 {
846 gimple stmt = gsi_stmt (t->call_gsi);
847
848 gimple_call_set_tail (stmt, true);
849 if (dump_file && (dump_flags & TDF_DETAILS))
850 {
851 fprintf (dump_file, "Found tail call ");
852 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
853 fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
854 }
855 }
856
857 return false;
858}
859
860/* Creates a tail-call accumulator of the same type as the return type of the
861 current function. LABEL is the name used to creating the temporary
862 variable for the accumulator. The accumulator will be inserted in the
863 phis of a basic block BB with single predecessor with an initial value
864 INIT converted to the current function return type. */
865
866static tree
867create_tailcall_accumulator (const char *label, basic_block bb, tree init)
868{
869 tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
870 tree tmp = create_tmp_var (ret_type, label);
871 gimple phi;
872
873 if (TREE_CODE (ret_type) == COMPLEX_TYPE
874 || TREE_CODE (ret_type) == VECTOR_TYPE)
875 DECL_GIMPLE_REG_P (tmp) = 1;
877 phi = create_phi_node (tmp, bb);
878 /* RET_TYPE can be a float when -ffast-maths is enabled. */
879 add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb));
880 return PHI_RESULT (phi);
881}
882
883/* Optimizes tail calls in the function, turning the tail recursion
884 into iteration. */
885
886static unsigned int
887tree_optimize_tail_calls_1 (bool opt_tailcalls)
888{
889 edge e;
890 bool phis_constructed = false;
891 struct tailcall *tailcalls = NULL, *act, *next;
892 bool changed = false;
893 basic_block first = single_succ (ENTRY_BLOCK_PTR);
894 tree param;
895 gimple stmt;
896 edge_iterator ei;
897
898 if (!suitable_for_tail_opt_p ())
899 return 0;
900 if (opt_tailcalls)
901 opt_tailcalls = suitable_for_tail_call_opt_p ();
902
903 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
904 {
905 /* Only traverse the normal exits, i.e. those that end with return
906 statement. */
907 stmt = last_stmt (e->src);
908
909 if (stmt
910 && gimple_code (stmt) == GIMPLE_RETURN)
911 find_tail_calls (e->src, &tailcalls);
912 }
913
914 /* Construct the phi nodes and accumulators if necessary. */
915 a_acc = m_acc = NULL_TREE;
916 for (act = tailcalls; act; act = act->next)
917 {
918 if (!act->tail_recursion)
919 continue;
920
921 if (!phis_constructed)
922 {
4b1e227d
SW
923 /* Ensure that there is only one predecessor of the block
924 or if there are existing degenerate PHI nodes. */
925 if (!single_pred_p (first)
926 || !gimple_seq_empty_p (phi_nodes (first)))
SS
927 first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
928
929 /* Copy the args if needed. */
930 for (param = DECL_ARGUMENTS (current_function_decl);
931 param;
932 param = TREE_CHAIN (param))
933 if (arg_needs_copy_p (param))
934 {
935 tree name = gimple_default_def (cfun, param);
936 tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
937 gimple phi;
938
939 set_default_def (param, new_name);
940 phi = create_phi_node (name, first);
941 SSA_NAME_DEF_STMT (name) = phi;
942 add_phi_arg (phi, new_name, single_pred_edge (first));
943 }
944 phis_constructed = true;
945 }
946
948 a_acc = create_tailcall_accumulator ("add_acc", first,
949 integer_zero_node);
950
951 if (act->mult && !m_acc)
952 m_acc = create_tailcall_accumulator ("mult_acc", first,
953 integer_one_node);
954 }
955
956 for (; tailcalls; tailcalls = next)
957 {
958 next = tailcalls->next;
959 changed |= optimize_tail_call (tailcalls, opt_tailcalls);
960 free (tailcalls);
961 }
962
963 if (a_acc || m_acc)
964 {
965 /* Modify the remaining return statements. */
966 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
967 {
968 stmt = last_stmt (e->src);
969
970 if (stmt
971 && gimple_code (stmt) == GIMPLE_RETURN)
973 }
974 }
975
976 if (changed)
977 free_dominance_info (CDI_DOMINATORS);
978
979 if (phis_constructed)
981 if (changed)
983 return 0;
984}
985
986static unsigned int
987execute_tail_recursion (void)
988{
989 return tree_optimize_tail_calls_1 (false);
990}
991
992static bool
993gate_tail_calls (void)
994{
995 return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
996}
997
998static unsigned int
999execute_tail_calls (void)
1000{
1001 return tree_optimize_tail_calls_1 (true);
1002}
1003
1004struct gimple_opt_pass pass_tail_recursion =
1005{
1006 {
1007 GIMPLE_PASS,
1008 "tailr", /* name */
1009 gate_tail_calls, /* gate */
1010 execute_tail_recursion, /* execute */
1011 NULL, /* sub */
1012 NULL, /* next */
1013 0, /* static_pass_number */
1014 0, /* tv_id */
1015 PROP_cfg | PROP_ssa, /* properties_required */
1016 0, /* properties_provided */
1017 0, /* properties_destroyed */
1018 0, /* todo_flags_start */
1019 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
1020 }
1021};
1022
1023struct gimple_opt_pass pass_tail_calls =
1024{
1025 {
1026 GIMPLE_PASS,
1027 "tailc", /* name */
1028 gate_tail_calls, /* gate */
1029 execute_tail_calls, /* execute */
1030 NULL, /* sub */
1031 NULL, /* next */
1032 0, /* static_pass_number */
1033 0, /* tv_id */
1034 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1035 0, /* properties_provided */
1036 0, /* properties_destroyed */
1037 0, /* todo_flags_start */
1038 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
1039 }
1040};