VOP_FSYNC.9: Missing comma
[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
333         *m = build_int_cst (TREE_TYPE (op0), -1);
334
335       *ass_var = dest;
336       return true;
337
338     case MINUS_EXPR:
339       if (*ass_var == op0)
340         *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
341       else
342         {
343           if (FLOAT_TYPE_P (TREE_TYPE (non_ass_var)))
344             *m = build_real (TREE_TYPE (non_ass_var), dconstm1);
345           else
346             *m = build_int_cst (TREE_TYPE (non_ass_var), -1);
347
348           *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
349         }
350
351       *ass_var = dest;
352       return true;
353
354       /* TODO -- Handle POINTER_PLUS_EXPR.  */
355
356     default:
357       return false;
358     }
359 }
360
361 /* Propagate VAR through phis on edge E.  */
362
363 static tree
364 propagate_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
381 static void
382 find_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   tree var;
394   referenced_var_iterator rvi;
395
396   if (!single_succ_p (bb))
397     return;
398
399   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
400     {
401       stmt = gsi_stmt (gsi);
402
403       /* Ignore labels, returns, clobbers and debug stmts.  */
404       if (gimple_code (stmt) == GIMPLE_LABEL
405           || gimple_code (stmt) == GIMPLE_RETURN
406           || gimple_clobber_p (stmt)
407           || is_gimple_debug (stmt))
408         continue;
409
410       /* Check for a call.  */
411       if (is_gimple_call (stmt))
412         {
413           call = stmt;
414           ass_var = gimple_call_lhs (stmt);
415           break;
416         }
417
418       /* If the statement references memory or volatile operands, fail.  */
419       if (gimple_references_memory_p (stmt)
420           || gimple_has_volatile_ops (stmt))
421         return;
422     }
423
424   if (gsi_end_p (gsi))
425     {
426       edge_iterator ei;
427       /* Recurse to the predecessors.  */
428       FOR_EACH_EDGE (e, ei, bb->preds)
429         find_tail_calls (e->src, ret);
430
431       return;
432     }
433
434   /* If the LHS of our call is not just a simple register, we can't
435      transform this into a tail or sibling call.  This situation happens,
436      in (e.g.) "*p = foo()" where foo returns a struct.  In this case
437      we won't have a temporary here, but we need to carry out the side
438      effect anyway, so tailcall is impossible.
439
440      ??? In some situations (when the struct is returned in memory via
441      invisible argument) we could deal with this, e.g. by passing 'p'
442      itself as that argument to foo, but it's too early to do this here,
443      and expand_call() will not handle it anyway.  If it ever can, then
444      we need to revisit this here, to allow that situation.  */
445   if (ass_var && !is_gimple_reg (ass_var))
446     return;
447
448   /* We found the call, check whether it is suitable.  */
449   tail_recursion = false;
450   func = gimple_call_fndecl (call);
451   if (func == current_function_decl)
452     {
453       tree arg;
454
455       for (param = DECL_ARGUMENTS (func), idx = 0;
456            param && idx < gimple_call_num_args (call);
457            param = DECL_CHAIN (param), idx ++)
458         {
459           arg = gimple_call_arg (call, idx);
460           if (param != arg)
461             {
462               /* Make sure there are no problems with copying.  The parameter
463                  have a copyable type and the two arguments must have reasonably
464                  equivalent types.  The latter requirement could be relaxed if
465                  we emitted a suitable type conversion statement.  */
466               if (!is_gimple_reg_type (TREE_TYPE (param))
467                   || !useless_type_conversion_p (TREE_TYPE (param),
468                                                  TREE_TYPE (arg)))
469                 break;
470
471               /* The parameter should be a real operand, so that phi node
472                  created for it at the start of the function has the meaning
473                  of copying the value.  This test implies is_gimple_reg_type
474                  from the previous condition, however this one could be
475                  relaxed by being more careful with copying the new value
476                  of the parameter (emitting appropriate GIMPLE_ASSIGN and
477                  updating the virtual operands).  */
478               if (!is_gimple_reg (param))
479                 break;
480             }
481         }
482       if (idx == gimple_call_num_args (call) && !param)
483         tail_recursion = true;
484     }
485
486   /* Make sure the tail invocation of this function does not refer
487      to local variables.  */
488   FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
489     {
490       if (TREE_CODE (var) != PARM_DECL
491           && auto_var_in_fn_p (var, cfun->decl)
492           && (ref_maybe_used_by_stmt_p (call, var)
493               || call_may_clobber_ref_p (call, var)))
494         return;
495     }
496
497   /* Now check the statements after the call.  None of them has virtual
498      operands, so they may only depend on the call through its return
499      value.  The return value should also be dependent on each of them,
500      since we are running after dce.  */
501   m = NULL_TREE;
502   a = NULL_TREE;
503
504   abb = bb;
505   agsi = gsi;
506   while (1)
507     {
508       tree tmp_a = NULL_TREE;
509       tree tmp_m = NULL_TREE;
510       gsi_next (&agsi);
511
512       while (gsi_end_p (agsi))
513         {
514           ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
515           abb = single_succ (abb);
516           agsi = gsi_start_bb (abb);
517         }
518
519       stmt = gsi_stmt (agsi);
520
521       if (gimple_code (stmt) == GIMPLE_LABEL)
522         continue;
523
524       if (gimple_code (stmt) == GIMPLE_RETURN)
525         break;
526
527       if (gimple_clobber_p (stmt))
528         continue;
529
530       if (is_gimple_debug (stmt))
531         continue;
532
533       if (gimple_code (stmt) != GIMPLE_ASSIGN)
534         return;
535
536       /* This is a gimple assign. */
537       if (! process_assignment (stmt, gsi, &tmp_m, &tmp_a, &ass_var))
538         return;
539
540       if (tmp_a)
541         {
542           tree type = TREE_TYPE (tmp_a);
543           if (a)
544             a = fold_build2 (PLUS_EXPR, type, fold_convert (type, a), tmp_a);
545           else
546             a = tmp_a;
547         }
548       if (tmp_m)
549         {
550           tree type = TREE_TYPE (tmp_m);
551           if (m)
552             m = fold_build2 (MULT_EXPR, type, fold_convert (type, m), tmp_m);
553           else
554             m = tmp_m;
555
556           if (a)
557             a = fold_build2 (MULT_EXPR, type, fold_convert (type, a), tmp_m);
558         }
559     }
560
561   /* See if this is a tail call we can handle.  */
562   ret_var = gimple_return_retval (stmt);
563
564   /* We may proceed if there either is no return value, or the return value
565      is identical to the call's return.  */
566   if (ret_var
567       && (ret_var != ass_var))
568     return;
569
570   /* If this is not a tail recursive call, we cannot handle addends or
571      multiplicands.  */
572   if (!tail_recursion && (m || a))
573     return;
574
575   nw = XNEW (struct tailcall);
576
577   nw->call_gsi = gsi;
578
579   nw->tail_recursion = tail_recursion;
580
581   nw->mult = m;
582   nw->add = a;
583
584   nw->next = *ret;
585   *ret = nw;
586 }
587
588 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E.  */
589
590 static void
591 add_successor_phi_arg (edge e, tree var, tree phi_arg)
592 {
593   gimple_stmt_iterator gsi;
594
595   for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
596     if (PHI_RESULT (gsi_stmt (gsi)) == var)
597       break;
598
599   gcc_assert (!gsi_end_p (gsi));
600   add_phi_arg (gsi_stmt (gsi), phi_arg, e, UNKNOWN_LOCATION);
601 }
602
603 /* Creates a GIMPLE statement which computes the operation specified by
604    CODE, ACC and OP1 to a new variable with name LABEL and inserts the
605    statement in the position specified by GSI.  Returns the
606    tree node of the statement's result.  */
607
608 static tree
609 adjust_return_value_with_ops (enum tree_code code, const char *label,
610                               tree acc, tree op1, gimple_stmt_iterator gsi)
611 {
612
613   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
614   tree tmp = create_tmp_reg (ret_type, label);
615   gimple stmt;
616   tree result;
617
618   add_referenced_var (tmp);
619
620   if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
621     stmt = gimple_build_assign_with_ops (code, tmp, acc, op1);
622   else
623     {
624       tree rhs = fold_convert (TREE_TYPE (acc),
625                                fold_build2 (code,
626                                             TREE_TYPE (op1),
627                                             fold_convert (TREE_TYPE (op1), acc),
628                                             op1));
629       rhs = force_gimple_operand_gsi (&gsi, rhs,
630                                       false, NULL, true, GSI_SAME_STMT);
631       stmt = gimple_build_assign (NULL_TREE, rhs);
632     }
633
634   result = make_ssa_name (tmp, stmt);
635   gimple_assign_set_lhs (stmt, result);
636   update_stmt (stmt);
637   gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
638   return result;
639 }
640
641 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
642    the computation specified by CODE and OP1 and insert the statement
643    at the position specified by GSI as a new statement.  Returns new SSA name
644    of updated accumulator.  */
645
646 static tree
647 update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
648                              gimple_stmt_iterator gsi)
649 {
650   gimple stmt;
651   tree var;
652   if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
653     stmt = gimple_build_assign_with_ops (code, SSA_NAME_VAR (acc), acc, op1);
654   else
655     {
656       tree rhs = fold_convert (TREE_TYPE (acc),
657                                fold_build2 (code,
658                                             TREE_TYPE (op1),
659                                             fold_convert (TREE_TYPE (op1), acc),
660                                             op1));
661       rhs = force_gimple_operand_gsi (&gsi, rhs,
662                                       false, NULL, false, GSI_CONTINUE_LINKING);
663       stmt = gimple_build_assign (NULL_TREE, rhs);
664     }
665   var = make_ssa_name (SSA_NAME_VAR (acc), stmt);
666   gimple_assign_set_lhs (stmt, var);
667   update_stmt (stmt);
668   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
669   return var;
670 }
671
672 /* Adjust the accumulator values according to A and M after GSI, and update
673    the phi nodes on edge BACK.  */
674
675 static void
676 adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
677 {
678   tree var, a_acc_arg, m_acc_arg;
679
680   if (m)
681     m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT);
682   if (a)
683     a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT);
684
685   a_acc_arg = a_acc;
686   m_acc_arg = m_acc;
687   if (a)
688     {
689       if (m_acc)
690         {
691           if (integer_onep (a))
692             var = m_acc;
693           else
694             var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
695                                                 a, gsi);
696         }
697       else
698         var = a;
699
700       a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
701     }
702
703   if (m)
704     m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
705
706   if (a_acc)
707     add_successor_phi_arg (back, a_acc, a_acc_arg);
708
709   if (m_acc)
710     add_successor_phi_arg (back, m_acc, m_acc_arg);
711 }
712
713 /* Adjust value of the return at the end of BB according to M and A
714    accumulators.  */
715
716 static void
717 adjust_return_value (basic_block bb, tree m, tree a)
718 {
719   tree retval;
720   gimple ret_stmt = gimple_seq_last_stmt (bb_seq (bb));
721   gimple_stmt_iterator gsi = gsi_last_bb (bb);
722
723   gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
724
725   retval = gimple_return_retval (ret_stmt);
726   if (!retval || retval == error_mark_node)
727     return;
728
729   if (m)
730     retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
731                                            gsi);
732   if (a)
733     retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
734                                            gsi);
735   gimple_return_set_retval (ret_stmt, retval);
736   update_stmt (ret_stmt);
737 }
738
739 /* Subtract COUNT and FREQUENCY from the basic block and it's
740    outgoing edge.  */
741 static void
742 decrease_profile (basic_block bb, gcov_type count, int frequency)
743 {
744   edge e;
745   bb->count -= count;
746   if (bb->count < 0)
747     bb->count = 0;
748   bb->frequency -= frequency;
749   if (bb->frequency < 0)
750     bb->frequency = 0;
751   if (!single_succ_p (bb))
752     {
753       gcc_assert (!EDGE_COUNT (bb->succs));
754       return;
755     }
756   e = single_succ_edge (bb);
757   e->count -= count;
758   if (e->count < 0)
759     e->count = 0;
760 }
761
762 /* Returns true if argument PARAM of the tail recursive call needs to be copied
763    when the call is eliminated.  */
764
765 static bool
766 arg_needs_copy_p (tree param)
767 {
768   tree def;
769
770   if (!is_gimple_reg (param) || !var_ann (param))
771     return false;
772
773   /* Parameters that are only defined but never used need not be copied.  */
774   def = gimple_default_def (cfun, param);
775   if (!def)
776     return false;
777
778   return true;
779 }
780
781 /* Eliminates tail call described by T.  TMP_VARS is a list of
782    temporary variables used to copy the function arguments.  */
783
784 static void
785 eliminate_tail_call (struct tailcall *t)
786 {
787   tree param, rslt;
788   gimple stmt, call;
789   tree arg;
790   size_t idx;
791   basic_block bb, first;
792   edge e;
793   gimple phi;
794   gimple_stmt_iterator gsi;
795   gimple orig_stmt;
796
797   stmt = orig_stmt = gsi_stmt (t->call_gsi);
798   bb = gsi_bb (t->call_gsi);
799
800   if (dump_file && (dump_flags & TDF_DETAILS))
801     {
802       fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
803                bb->index);
804       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
805       fprintf (dump_file, "\n");
806     }
807
808   gcc_assert (is_gimple_call (stmt));
809
810   first = single_succ (ENTRY_BLOCK_PTR);
811
812   /* Remove the code after call_gsi that will become unreachable.  The
813      possibly unreachable code in other blocks is removed later in
814      cfg cleanup.  */
815   gsi = t->call_gsi;
816   gsi_next (&gsi);
817   while (!gsi_end_p (gsi))
818     {
819       gimple t = gsi_stmt (gsi);
820       /* Do not remove the return statement, so that redirect_edge_and_branch
821          sees how the block ends.  */
822       if (gimple_code (t) == GIMPLE_RETURN)
823         break;
824
825       gsi_remove (&gsi, true);
826       release_defs (t);
827     }
828
829   /* Number of executions of function has reduced by the tailcall.  */
830   e = single_succ_edge (gsi_bb (t->call_gsi));
831   decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
832   decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
833   if (e->dest != EXIT_BLOCK_PTR)
834     decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
835
836   /* Replace the call by a jump to the start of function.  */
837   e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)),
838                                 first);
839   gcc_assert (e);
840   PENDING_STMT (e) = NULL;
841
842   /* Add phi node entries for arguments.  The ordering of the phi nodes should
843      be the same as the ordering of the arguments.  */
844   for (param = DECL_ARGUMENTS (current_function_decl),
845          idx = 0, gsi = gsi_start_phis (first);
846        param;
847        param = DECL_CHAIN (param), idx++)
848     {
849       if (!arg_needs_copy_p (param))
850         continue;
851
852       arg = gimple_call_arg (stmt, idx);
853       phi = gsi_stmt (gsi);
854       gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
855
856       add_phi_arg (phi, arg, e, gimple_location (stmt));
857       gsi_next (&gsi);
858     }
859
860   /* Update the values of accumulators.  */
861   adjust_accumulator_values (t->call_gsi, t->mult, t->add, e);
862
863   call = gsi_stmt (t->call_gsi);
864   rslt = gimple_call_lhs (call);
865   if (rslt != NULL_TREE)
866     {
867       /* Result of the call will no longer be defined.  So adjust the
868          SSA_NAME_DEF_STMT accordingly.  */
869       SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
870     }
871
872   gsi_remove (&t->call_gsi, true);
873   release_defs (call);
874 }
875
876 /* Add phi nodes for the virtual operands defined in the function to the
877    header of the loop created by tail recursion elimination.
878
879    Originally, we used to add phi nodes only for call clobbered variables,
880    as the value of the non-call clobbered ones obviously cannot be used
881    or changed within the recursive call.  However, the local variables
882    from multiple calls now share the same location, so the virtual ssa form
883    requires us to say that the location dies on further iterations of the loop,
884    which requires adding phi nodes.
885 */
886 static void
887 add_virtual_phis (void)
888 {
889   referenced_var_iterator rvi;
890   tree var;
891
892   /* The problematic part is that there is no way how to know what
893      to put into phi nodes (there in fact does not have to be such
894      ssa name available).  A solution would be to have an artificial
895      use/kill for all virtual operands in EXIT node.  Unless we have
896      this, we cannot do much better than to rebuild the ssa form for
897      possibly affected virtual ssa names from scratch.  */
898
899   FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
900     {
901       if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
902         mark_sym_for_renaming (var);
903     }
904 }
905
906 /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
907    mark the tailcalls for the sibcall optimization.  */
908
909 static bool
910 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
911 {
912   if (t->tail_recursion)
913     {
914       eliminate_tail_call (t);
915       return true;
916     }
917
918   if (opt_tailcalls)
919     {
920       gimple stmt = gsi_stmt (t->call_gsi);
921
922       gimple_call_set_tail (stmt, true);
923       if (dump_file && (dump_flags & TDF_DETAILS))
924         {
925           fprintf (dump_file, "Found tail call ");
926           print_gimple_stmt (dump_file, stmt, 0, dump_flags);
927           fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
928         }
929     }
930
931   return false;
932 }
933
934 /* Creates a tail-call accumulator of the same type as the return type of the
935    current function.  LABEL is the name used to creating the temporary
936    variable for the accumulator.  The accumulator will be inserted in the
937    phis of a basic block BB with single predecessor with an initial value
938    INIT converted to the current function return type.  */
939
940 static tree
941 create_tailcall_accumulator (const char *label, basic_block bb, tree init)
942 {
943   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
944   tree tmp = create_tmp_reg (ret_type, label);
945   gimple phi;
946
947   add_referenced_var (tmp);
948   phi = create_phi_node (tmp, bb);
949   /* RET_TYPE can be a float when -ffast-maths is enabled.  */
950   add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb),
951                UNKNOWN_LOCATION);
952   return PHI_RESULT (phi);
953 }
954
955 /* Optimizes tail calls in the function, turning the tail recursion
956    into iteration.  */
957
958 static unsigned int
959 tree_optimize_tail_calls_1 (bool opt_tailcalls)
960 {
961   edge e;
962   bool phis_constructed = false;
963   struct tailcall *tailcalls = NULL, *act, *next;
964   bool changed = false;
965   basic_block first = single_succ (ENTRY_BLOCK_PTR);
966   tree param;
967   gimple stmt;
968   edge_iterator ei;
969
970   if (!suitable_for_tail_opt_p ())
971     return 0;
972   if (opt_tailcalls)
973     opt_tailcalls = suitable_for_tail_call_opt_p ();
974
975   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
976     {
977       /* Only traverse the normal exits, i.e. those that end with return
978          statement.  */
979       stmt = last_stmt (e->src);
980
981       if (stmt
982           && gimple_code (stmt) == GIMPLE_RETURN)
983         find_tail_calls (e->src, &tailcalls);
984     }
985
986   /* Construct the phi nodes and accumulators if necessary.  */
987   a_acc = m_acc = NULL_TREE;
988   for (act = tailcalls; act; act = act->next)
989     {
990       if (!act->tail_recursion)
991         continue;
992
993       if (!phis_constructed)
994         {
995           /* Ensure that there is only one predecessor of the block
996              or if there are existing degenerate PHI nodes.  */
997           if (!single_pred_p (first)
998               || !gimple_seq_empty_p (phi_nodes (first)))
999             first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
1000
1001           /* Copy the args if needed.  */
1002           for (param = DECL_ARGUMENTS (current_function_decl);
1003                param;
1004                param = DECL_CHAIN (param))
1005             if (arg_needs_copy_p (param))
1006               {
1007                 tree name = gimple_default_def (cfun, param);
1008                 tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
1009                 gimple phi;
1010
1011                 set_default_def (param, new_name);
1012                 phi = create_phi_node (name, first);
1013                 SSA_NAME_DEF_STMT (name) = phi;
1014                 add_phi_arg (phi, new_name, single_pred_edge (first),
1015                              EXPR_LOCATION (param));
1016               }
1017           phis_constructed = true;
1018         }
1019
1020       if (act->add && !a_acc)
1021         a_acc = create_tailcall_accumulator ("add_acc", first,
1022                                              integer_zero_node);
1023
1024       if (act->mult && !m_acc)
1025         m_acc = create_tailcall_accumulator ("mult_acc", first,
1026                                              integer_one_node);
1027     }
1028
1029   if (a_acc || m_acc)
1030     {
1031       /* When the tail call elimination using accumulators is performed,
1032          statements adding the accumulated value are inserted at all exits.
1033          This turns all other tail calls to non-tail ones.  */
1034       opt_tailcalls = false;
1035     }
1036
1037   for (; tailcalls; tailcalls = next)
1038     {
1039       next = tailcalls->next;
1040       changed |= optimize_tail_call (tailcalls, opt_tailcalls);
1041       free (tailcalls);
1042     }
1043
1044   if (a_acc || m_acc)
1045     {
1046       /* Modify the remaining return statements.  */
1047       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1048         {
1049           stmt = last_stmt (e->src);
1050
1051           if (stmt
1052               && gimple_code (stmt) == GIMPLE_RETURN)
1053             adjust_return_value (e->src, m_acc, a_acc);
1054         }
1055     }
1056
1057   if (changed)
1058     free_dominance_info (CDI_DOMINATORS);
1059
1060   if (phis_constructed)
1061     add_virtual_phis ();
1062   if (changed)
1063     return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
1064   return 0;
1065 }
1066
1067 static unsigned int
1068 execute_tail_recursion (void)
1069 {
1070   return tree_optimize_tail_calls_1 (false);
1071 }
1072
1073 static bool
1074 gate_tail_calls (void)
1075 {
1076   return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
1077 }
1078
1079 static unsigned int
1080 execute_tail_calls (void)
1081 {
1082   return tree_optimize_tail_calls_1 (true);
1083 }
1084
1085 struct gimple_opt_pass pass_tail_recursion =
1086 {
1087  {
1088   GIMPLE_PASS,
1089   "tailr",                              /* name */
1090   gate_tail_calls,                      /* gate */
1091   execute_tail_recursion,               /* execute */
1092   NULL,                                 /* sub */
1093   NULL,                                 /* next */
1094   0,                                    /* static_pass_number */
1095   TV_NONE,                              /* tv_id */
1096   PROP_cfg | PROP_ssa,                  /* properties_required */
1097   0,                                    /* properties_provided */
1098   0,                                    /* properties_destroyed */
1099   0,                                    /* todo_flags_start */
1100   TODO_verify_ssa                       /* todo_flags_finish */
1101  }
1102 };
1103
1104 struct gimple_opt_pass pass_tail_calls =
1105 {
1106  {
1107   GIMPLE_PASS,
1108   "tailc",                              /* name */
1109   gate_tail_calls,                      /* gate */
1110   execute_tail_calls,                   /* execute */
1111   NULL,                                 /* sub */
1112   NULL,                                 /* next */
1113   0,                                    /* static_pass_number */
1114   TV_NONE,                              /* tv_id */
1115   PROP_cfg | PROP_ssa,                  /* properties_required */
1116   0,                                    /* properties_provided */
1117   0,                                    /* properties_destroyed */
1118   0,                                    /* todo_flags_start */
1119   TODO_verify_ssa                       /* todo_flags_finish */
1120  }
1121 };