OSDN Git Service

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