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