OSDN Git Service

* targhooks.c (default_unwind_emit, default_scalar_mode_supported_p):
[pf3gnuchains/gcc-fork.git] / gcc / tree-tailcall.c
1 /* Tail call optimization on trees.
2    Copyright (C) 2003 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
10
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING.  If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.  */
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
39 /* The file implements the tail recursion elimination.  It is also used to
40    analyze the tail calls in general, passing the results to the rtl level
41    where they are used for sibcall optimization.
42
43    In addition to the standard tail recursion elimination, we handle the most
44    trivial cases of making the call tail recursive by creating accumulators.
45    For example the following function
46
47    int sum (int n)
48    {
49      if (n > 0)
50        return n + sum (n - 1);
51      else
52        return 0;
53    }
54
55    is transformed into
56
57    int sum (int n)
58    {
59      int acc = 0;
60
61      while (n > 0)
62        acc += n--;
63
64      return acc;
65    }
66
67    To do this, we maintain two accumulators (a_acc and m_acc) that indicate 
68    when we reach the return x statement, we should return a_acc + x * m_acc
69    instead.  They are initially initialized to 0 and 1, respectively,
70    so the semantics of the function is obviously preserved.  If we are
71    guaranteed that the value of the accumulator never change, we
72    omit the accumulator.
73
74    There are three cases how the function may exit.  The first one is
75    handled in adjust_return_value, the other two in adjust_accumulator_values
76    (the second case is actually a special case of the third one and we
77    present it separately just for clarity):
78
79    1) Just return x, where x is not in any of the remaining special shapes.
80       We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
81       
82    2) return f (...), where f is the current function, is rewritten in a
83       classical tail-recursion elimination way, into assignment of arguments
84       and jump to the start of the function.  Values of the accumulators
85       are unchanged.
86                
87    3) return a + m * f(...), where a and m do not depend on call to f.
88       To preserve the semantics described before we want this to be rewritten
89       in such a way that we finally return
90
91       a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
92
93       I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
94       eliminate the tail call to f.  Special cases when the value is just
95       added or just multiplied are obtained by setting a = 0 or m = 1.
96
97    TODO -- it is possible to do similar tricks for other operations.  */
98
99 /* A structure that describes the tailcall.  */
100
101 struct tailcall
102 {
103   /* The block in that the call occur.  */
104   basic_block call_block;
105
106   /* The iterator pointing to the call statement.  */
107   block_stmt_iterator call_bsi;
108
109   /* True if it is a call to the current function.  */
110   bool tail_recursion;
111
112   /* The return value of the caller is mult * f + add, where f is the return
113      value of the call.  */
114   tree mult, add;
115
116   /* Next tailcall in the chain.  */
117   struct tailcall *next;
118 };
119
120 /* The variables holding the value of multiplicative and additive
121    accumulator.  */
122 static tree m_acc, a_acc;
123
124 static bool suitable_for_tail_opt_p (void);
125 static bool optimize_tail_call (struct tailcall *, bool);
126 static void eliminate_tail_call (struct tailcall *);
127 static void find_tail_calls (basic_block, struct tailcall **);
128
129 /* Returns false when the function is not suitable for tail call optimization
130    from some reason (e.g. if it takes variable number of arguments).  */
131
132 static bool
133 suitable_for_tail_opt_p (void)
134 {
135   int i;
136
137   if (current_function_stdarg)
138     return false;
139
140   /* No local variable should be call-clobbered.  We ignore any kind
141      of memory tag, as these are not real variables.  */
142   for (i = 0; i < (int) VARRAY_ACTIVE_SIZE (referenced_vars); i++)
143     {
144       tree var = VARRAY_TREE (referenced_vars, i);
145
146       if (!(TREE_STATIC (var) || DECL_EXTERNAL (var))
147           && var_ann (var)->mem_tag_kind == NOT_A_TAG
148           && is_call_clobbered (var))
149         return false;
150     }
151
152   return true;
153 }
154 /* Returns false when the function is not suitable for tail call optimization
155    from some reason (e.g. if it takes variable number of arguments).
156    This test must pass in addition to suitable_for_tail_opt_p in order to make
157    tail call discovery happen.  */
158
159 static bool
160 suitable_for_tail_call_opt_p (void)
161 {
162   /* alloca (until we have stack slot life analysis) inhibits
163      sibling call optimizations, but not tail recursion.  */
164   if (current_function_calls_alloca)
165     return false;
166
167   /* If we are using sjlj exceptions, we may need to add a call to
168      _Unwind_SjLj_Unregister at exit of the function.  Which means
169      that we cannot do any sibcall transformations.  */
170   if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ())
171     return false;
172
173   /* Any function that calls setjmp might have longjmp called from
174      any called function.  ??? We really should represent this
175      properly in the CFG so that this needn't be special cased.  */
176   if (current_function_calls_setjmp)
177     return false;
178
179   return true;
180 }
181
182 /* Checks whether the expression EXPR in stmt AT is independent of the
183    statement pointed by BSI (in a sense that we already know EXPR's value
184    at BSI).  We use the fact that we are only called from the chain of
185    basic blocks that have only single successor.  Returns the expression
186    containing the value of EXPR at BSI.  */
187
188 static tree
189 independent_of_stmt_p (tree expr, tree at, block_stmt_iterator bsi)
190 {
191   basic_block bb, call_bb, at_bb;
192   edge e;
193
194   if (is_gimple_min_invariant (expr))
195     return expr;
196
197   if (TREE_CODE (expr) != SSA_NAME)
198     return NULL_TREE;
199
200   /* Mark the blocks in the chain leading to the end.  */
201   at_bb = bb_for_stmt (at);
202   call_bb = bb_for_stmt (bsi_stmt (bsi));
203   for (bb = call_bb; bb != at_bb; bb = bb->succ->dest)
204     bb->aux = &bb->aux;
205   bb->aux = &bb->aux;
206
207   while (1)
208     { 
209       at = SSA_NAME_DEF_STMT (expr);
210       bb = bb_for_stmt (at);
211
212       /* The default definition or defined before the chain.  */
213       if (!bb || !bb->aux)
214         break;
215
216       if (bb == call_bb)
217         {
218           for (; !bsi_end_p (bsi); bsi_next (&bsi))
219             if (bsi_stmt (bsi) == at)
220               break;
221
222           if (!bsi_end_p (bsi))
223             expr = NULL_TREE;
224           break;
225         }
226
227       if (TREE_CODE (at) != PHI_NODE)
228         {
229           expr = NULL_TREE;
230           break;
231         }
232
233       for (e = bb->pred; e; e = e->pred_next)
234         if (e->src->aux)
235           break;
236       gcc_assert (e);
237
238       expr = PHI_ARG_DEF_FROM_EDGE (at, e);
239       if (TREE_CODE (expr) != SSA_NAME)
240         {
241           /* The value is a constant.  */
242           break;
243         }
244     }
245
246   /* Unmark the blocks.  */
247   for (bb = call_bb; bb != at_bb; bb = bb->succ->dest)
248     bb->aux = NULL;
249   bb->aux = NULL;
250
251   return expr;
252 }
253
254 /* Simulates the effect of an assignment of ASS in STMT on the return value
255    of the tail recursive CALL passed in ASS_VAR.  M and A are the
256    multiplicative and the additive factor for the real return value.  */
257
258 static bool
259 process_assignment (tree ass, tree stmt, block_stmt_iterator call, tree *m,
260                     tree *a, tree *ass_var)
261 {
262   tree op0, op1, non_ass_var;
263   tree dest = TREE_OPERAND (ass, 0);
264   tree src = TREE_OPERAND (ass, 1);
265   enum tree_code code = TREE_CODE (src);
266   tree src_var = src;
267
268   /* See if this is a simple copy operation of an SSA name to the function
269      result.  In that case we may have a simple tail call.  Ignore type
270      conversions that can never produce extra code between the function
271      call and the function return.  */
272   STRIP_NOPS (src_var);
273   if (TREE_CODE (src_var) == SSA_NAME)
274     {
275       if (src_var != *ass_var)
276         return false;
277
278       *ass_var = dest;
279       return true;
280     }
281
282   if (TREE_CODE_CLASS (code) != '2')
283     return false;
284
285   /* We only handle the code like
286
287      x = call ();
288      y = m * x;
289      z = y + a;
290      return z;
291
292      TODO -- Extend it for cases where the linear transformation of the output
293      is expressed in a more complicated way.  */
294
295   op0 = TREE_OPERAND (src, 0);
296   op1 = TREE_OPERAND (src, 1);
297
298   if (op0 == *ass_var
299       && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
300     ;
301   else if (op1 == *ass_var
302            && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
303     ;
304   else
305     return false;
306
307   switch (code)
308     {
309     case PLUS_EXPR:
310       /* There should be no previous addition.  TODO -- it should be fairly
311          straightforward to lift this restriction -- just allow storing
312          more complicated expressions in *A, and gimplify it in
313          adjust_accumulator_values.  */
314       if (*a)
315         return false;
316       *a = non_ass_var;
317       *ass_var = dest;
318       return true;
319
320     case MULT_EXPR:
321       /* Similar remark applies here.  Handling multiplication after addition
322          is just slightly more complicated -- we need to multiply both *A and
323          *M.  */
324       if (*a || *m)
325         return false;
326       *m = non_ass_var;
327       *ass_var = dest;
328       return true;
329
330       /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR).  */
331
332     default:
333       return false;
334     }
335 }
336
337 /* Propagate VAR through phis on edge E.  */
338
339 static tree
340 propagate_through_phis (tree var, edge e)
341 {
342   basic_block dest = e->dest;
343   tree phi;
344
345   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
346     if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
347       return PHI_RESULT (phi);
348
349   return var;
350 }
351
352 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
353    added to the start of RET.  */
354
355 static void
356 find_tail_calls (basic_block bb, struct tailcall **ret)
357 {
358   tree ass_var, ret_var, stmt, func, param, args, call = NULL_TREE;
359   block_stmt_iterator bsi, absi;
360   bool tail_recursion;
361   struct tailcall *nw;
362   edge e;
363   tree m, a;
364   basic_block abb;
365   stmt_ann_t ann;
366
367   if (bb->succ->succ_next)
368     return;
369
370   for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
371     {
372       stmt = bsi_stmt (bsi);
373
374       /* Ignore labels.  */
375       if (TREE_CODE (stmt) == LABEL_EXPR)
376         continue;
377
378       get_stmt_operands (stmt);
379
380       /* Check for a call.  */
381       if (TREE_CODE (stmt) == MODIFY_EXPR)
382         {
383           ass_var = TREE_OPERAND (stmt, 0);
384           call = TREE_OPERAND (stmt, 1);
385           if (TREE_CODE (call) == WITH_SIZE_EXPR)
386             call = TREE_OPERAND (call, 0);
387         }
388       else
389         {
390           ass_var = NULL_TREE;
391           call = stmt;
392         }
393
394       if (TREE_CODE (call) == CALL_EXPR)
395         break;
396
397       /* If the statement has virtual or volatile operands, fail.  */
398       ann = stmt_ann (stmt);
399       if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann))
400           || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann))
401           || NUM_VUSES (VUSE_OPS (ann))
402           || ann->has_volatile_ops)
403         return;
404     }
405
406   if (bsi_end_p (bsi))
407     {
408       /* Recurse to the predecessors.  */
409       for (e = bb->pred; e; e = e->pred_next)
410         find_tail_calls (e->src, ret);
411
412       return;
413     }
414
415   /* We found the call, check whether it is suitable.  */
416   tail_recursion = false;
417   func = get_callee_fndecl (call);
418   if (func == current_function_decl)
419     {
420       for (param = DECL_ARGUMENTS (func), args = TREE_OPERAND (call, 1);
421            param && args;
422            param = TREE_CHAIN (param), args = TREE_CHAIN (args))
423         {
424           tree arg = TREE_VALUE (args);
425           if (param != arg
426               /* Make sure there are no problems with copying.  Note we must
427                  have a copyable type and the two arguments must have reasonably
428                  equivalent types.  The latter requirement could be relaxed if
429                  we emitted a suitable type conversion statement.  */
430               && (!is_gimple_reg_type (TREE_TYPE (param))
431                   || !lang_hooks.types_compatible_p (TREE_TYPE (param),
432                                                      TREE_TYPE (arg))))
433             break;
434         }
435       if (!args && !param)
436         tail_recursion = true;
437     }
438
439   /* Now check the statements after the call.  None of them has virtual
440      operands, so they may only depend on the call through its return
441      value.  The return value should also be dependent on each of them,
442      since we are running after dce.  */
443   m = NULL_TREE;
444   a = NULL_TREE;
445
446   abb = bb;
447   absi = bsi;
448   while (1)
449     {
450       bsi_next (&absi);
451
452       while (bsi_end_p (absi))
453         {
454           ass_var = propagate_through_phis (ass_var, abb->succ);
455           abb = abb->succ->dest;
456           absi = bsi_start (abb);
457         }
458
459       stmt = bsi_stmt (absi);
460
461       if (TREE_CODE (stmt) == LABEL_EXPR)
462         continue;
463
464       if (TREE_CODE (stmt) == RETURN_EXPR)
465         break;
466
467       if (TREE_CODE (stmt) != MODIFY_EXPR)
468         return;
469
470       if (!process_assignment (stmt, stmt, bsi, &m, &a, &ass_var))
471         return;
472     }
473
474   /* See if this is a tail call we can handle.  */
475   ret_var = TREE_OPERAND (stmt, 0);
476   if (ret_var
477       && TREE_CODE (ret_var) == MODIFY_EXPR)
478     {
479       tree ret_op = TREE_OPERAND (ret_var, 1);
480       STRIP_NOPS (ret_op);
481       if (!tail_recursion
482           && TREE_CODE (ret_op) != SSA_NAME)
483         return;
484
485       if (!process_assignment (ret_var, stmt, bsi, &m, &a, &ass_var))
486         return;
487       ret_var = TREE_OPERAND (ret_var, 0);
488     }
489
490   /* We may proceed if there either is no return value, or the return value
491      is identical to the call's return.  */
492   if (ret_var
493       && (ret_var != ass_var))
494     return;
495
496   /* If this is not a tail recursive call, we cannot handle addends or
497      multiplicands.  */
498   if (!tail_recursion && (m || a))
499     return;
500
501   nw = xmalloc (sizeof (struct tailcall));
502
503   nw->call_block = bb;
504   nw->call_bsi = bsi;
505
506   nw->tail_recursion = tail_recursion;
507
508   nw->mult = m;
509   nw->add = a;
510
511   nw->next = *ret;
512   *ret = nw;
513 }
514
515 /* Adjust the accumulator values according to A and M after BSI, and update
516    the phi nodes on edge BACK.  */
517
518 static void
519 adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back)
520 {
521   tree stmt, var, phi, tmp;
522   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
523   tree a_acc_arg = a_acc, m_acc_arg = m_acc;
524
525   if (a)
526     {
527       if (m_acc)
528         {
529           if (integer_onep (a))
530             var = m_acc;
531           else
532             {
533               stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
534                             build (MULT_EXPR, ret_type, m_acc, a));
535
536               tmp = create_tmp_var (ret_type, "acc_tmp");
537               add_referenced_tmp_var (tmp);
538
539               var = make_ssa_name (tmp, stmt);
540               TREE_OPERAND (stmt, 0) = var;
541               bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
542             }
543         }
544       else
545         var = a;
546
547       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
548                     build (PLUS_EXPR, ret_type, a_acc, var));
549       var = make_ssa_name (SSA_NAME_VAR (a_acc), stmt);
550       TREE_OPERAND (stmt, 0) = var;
551       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
552       a_acc_arg = var;
553     }
554
555   if (m)
556     {
557       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
558                     build (MULT_EXPR, ret_type, m_acc, m));
559       var = make_ssa_name (SSA_NAME_VAR (m_acc), stmt);
560       TREE_OPERAND (stmt, 0) = var;
561       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
562       m_acc_arg = var;
563     }
564
565   if (a_acc)
566     {
567       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
568         if (PHI_RESULT (phi) == a_acc)
569           break;
570
571       add_phi_arg (&phi, a_acc_arg, back);
572     }
573
574   if (m_acc)
575     {
576       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
577         if (PHI_RESULT (phi) == m_acc)
578           break;
579
580       add_phi_arg (&phi, m_acc_arg, back);
581     }
582 }
583
584 /* Adjust value of the return at the end of BB according to M and A
585    accumulators.  */
586
587 static void
588 adjust_return_value (basic_block bb, tree m, tree a)
589 {
590   tree ret_stmt = last_stmt (bb), ret_var, var, stmt, tmp;
591   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
592   block_stmt_iterator bsi = bsi_last (bb);
593
594   gcc_assert (TREE_CODE (ret_stmt) == RETURN_EXPR);
595
596   ret_var = TREE_OPERAND (ret_stmt, 0);
597   if (!ret_var)
598     return;
599
600   if (TREE_CODE (ret_var) == MODIFY_EXPR)
601     {
602       ret_var->common.ann = (tree_ann_t) stmt_ann (ret_stmt);
603       bsi_replace (&bsi, ret_var, true);
604       SSA_NAME_DEF_STMT (TREE_OPERAND (ret_var, 0)) = ret_var;
605       ret_var = TREE_OPERAND (ret_var, 0);
606       ret_stmt = build1 (RETURN_EXPR, TREE_TYPE (ret_stmt), ret_var);
607       bsi_insert_after (&bsi, ret_stmt, BSI_NEW_STMT);
608     }
609
610   if (m)
611     {
612       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
613                     build (MULT_EXPR, ret_type, m_acc, ret_var));
614
615       tmp = create_tmp_var (ret_type, "acc_tmp");
616       add_referenced_tmp_var (tmp);
617
618       var = make_ssa_name (tmp, stmt);
619       TREE_OPERAND (stmt, 0) = var;
620       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
621     }
622   else
623     var = ret_var;
624
625   if (a)
626     {
627       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
628                     build (PLUS_EXPR, ret_type, a_acc, var));
629
630       tmp = create_tmp_var (ret_type, "acc_tmp");
631       add_referenced_tmp_var (tmp);
632
633       var = make_ssa_name (tmp, stmt);
634       TREE_OPERAND (stmt, 0) = var;
635       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
636     }
637
638   TREE_OPERAND (ret_stmt, 0) = var;
639   modify_stmt (ret_stmt);
640 }
641
642 /* Eliminates tail call described by T.  TMP_VARS is a list of
643    temporary variables used to copy the function arguments.  */
644
645 static void
646 eliminate_tail_call (struct tailcall *t)
647 {
648   tree param, stmt, args, rslt, call;
649   basic_block bb, first;
650   edge e;
651   tree phi;
652   stmt_ann_t ann;
653   v_may_def_optype v_may_defs;
654   unsigned i;
655   block_stmt_iterator bsi;
656
657   stmt = bsi_stmt (t->call_bsi);
658   get_stmt_operands (stmt);
659   ann = stmt_ann (stmt);
660   bb = t->call_block;
661
662   if (dump_file && (dump_flags & TDF_DETAILS))
663     {
664       fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
665                bb->index);
666       print_generic_stmt (dump_file, stmt, TDF_SLIM);
667       fprintf (dump_file, "\n");
668     }
669
670   if (TREE_CODE (stmt) == MODIFY_EXPR)
671     stmt = TREE_OPERAND (stmt, 1);
672
673   first = ENTRY_BLOCK_PTR->succ->dest;
674
675   /* Remove the code after call_bsi that will become unreachable.  The
676      possibly unreachable code in other blocks is removed later in
677      cfg cleanup.  */
678   bsi = t->call_bsi;
679   bsi_next (&bsi);
680   while (!bsi_end_p (bsi))
681     {
682       /* Do not remove the return statement, so that redirect_edge_and_branch
683          sees how the block ends.  */
684       if (TREE_CODE (bsi_stmt (bsi)) == RETURN_EXPR)
685         break;
686
687       bsi_remove (&bsi);
688     }
689
690   /* Replace the call by a jump to the start of function.  */
691   e = redirect_edge_and_branch (t->call_block->succ, first);
692   gcc_assert (e);
693   PENDING_STMT (e) = NULL_TREE;
694
695   /* Add phi node entries for arguments.  Not every PHI node corresponds to
696      a function argument (there may be PHI nodes for virtual definitions of the
697      eliminated calls), so we search for a PHI corresponding to each argument
698      rather than searching for which argument a PHI node corresponds to.  */
699   
700   for (param = DECL_ARGUMENTS (current_function_decl),
701        args = TREE_OPERAND (stmt, 1);
702        param;
703        param = TREE_CHAIN (param),
704        args = TREE_CHAIN (args))
705     {
706       
707       for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi))
708         if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
709           break;
710
711       /* The phi node indeed does not have to be there, in case the operand is
712          invariant in the function.  */
713       if (!phi)
714         continue;
715
716       add_phi_arg (&phi, TREE_VALUE (args), e);
717     }
718
719   /* Add phi nodes for the call clobbered variables.  */
720   v_may_defs = V_MAY_DEF_OPS (ann);
721   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
722     {
723       param = SSA_NAME_VAR (V_MAY_DEF_RESULT (v_may_defs, i));
724       for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi))
725         if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
726           break;
727
728       if (!phi)
729         {
730           tree name = var_ann (param)->default_def;
731           tree new_name;
732
733           if (!name)
734             {
735               /* It may happen that the tag does not have a default_def in case
736                  when all uses of it are dominated by a MUST_DEF.  This however
737                  means that it is not necessary to add a phi node for this
738                  tag.  */
739               continue;
740             }
741           new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
742
743           var_ann (param)->default_def = new_name;
744           phi = create_phi_node (name, first);
745           SSA_NAME_DEF_STMT (name) = phi;
746           add_phi_arg (&phi, new_name, ENTRY_BLOCK_PTR->succ);
747
748           /* For all calls the same set of variables should be clobbered.  This
749              means that there always should be the appropriate phi node except
750              for the first time we eliminate the call.  */
751           gcc_assert (!first->pred->pred_next->pred_next);
752         }
753
754       add_phi_arg (&phi, V_MAY_DEF_OP (v_may_defs, i), e);
755     }
756
757   /* Update the values of accumulators.  */
758   adjust_accumulator_values (t->call_bsi, t->mult, t->add, e);
759
760   call = bsi_stmt (t->call_bsi);
761   if (TREE_CODE (call) == MODIFY_EXPR)
762     {
763       rslt = TREE_OPERAND (call, 0);
764
765       /* Result of the call will no longer be defined.  So adjust the
766          SSA_NAME_DEF_STMT accordingly.  */
767       SSA_NAME_DEF_STMT (rslt) = build_empty_stmt ();
768     }
769
770   bsi_remove (&t->call_bsi);
771 }
772
773 /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
774    mark the tailcalls for the sibcall optimization.  */
775
776 static bool
777 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
778 {
779   if (t->tail_recursion)
780     {
781       eliminate_tail_call (t);
782       return true;
783     }
784
785   if (opt_tailcalls)
786     {
787       tree stmt = bsi_stmt (t->call_bsi);
788
789       stmt = get_call_expr_in (stmt);
790       CALL_EXPR_TAILCALL (stmt) = 1;
791       if (dump_file && (dump_flags & TDF_DETAILS))
792         {
793           fprintf (dump_file, "Found tail call ");
794           print_generic_expr (dump_file, stmt, dump_flags);
795           fprintf (dump_file, " in bb %i\n", t->call_block->index);
796         }
797     }
798
799   return false;
800 }
801
802 /* Optimizes tail calls in the function, turning the tail recursion
803    into iteration.  */
804
805 static void
806 tree_optimize_tail_calls_1 (bool opt_tailcalls)
807 {
808   edge e;
809   bool phis_constructed = false;
810   struct tailcall *tailcalls = NULL, *act, *next;
811   bool changed = false;
812   basic_block first = ENTRY_BLOCK_PTR->succ->dest;
813   tree stmt, param, ret_type, tmp, phi;
814
815   if (!suitable_for_tail_opt_p ())
816     return;
817   if (opt_tailcalls)
818     opt_tailcalls = suitable_for_tail_call_opt_p ();
819
820   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
821     {
822       /* Only traverse the normal exits, i.e. those that end with return
823          statement.  */
824       stmt = last_stmt (e->src);
825
826       if (stmt
827           && TREE_CODE (stmt) == RETURN_EXPR)
828         find_tail_calls (e->src, &tailcalls);
829     }
830
831   /* Construct the phi nodes and accumulators if necessary.  */
832   a_acc = m_acc = NULL_TREE;
833   for (act = tailcalls; act; act = act->next)
834     {
835       if (!act->tail_recursion)
836         continue;
837
838       if (!phis_constructed)
839         {
840           /* Ensure that there is only one predecessor of the block.  */
841           if (first->pred->pred_next)
842             first = split_edge (ENTRY_BLOCK_PTR->succ);
843
844           /* Copy the args if needed.  */
845           for (param = DECL_ARGUMENTS (current_function_decl);
846                param;
847                param = TREE_CHAIN (param))
848             if (var_ann (param)
849                 /* Also parameters that are only defined but never used need not
850                    be copied.  */
851                 && (var_ann (param)->default_def
852                     && TREE_CODE (var_ann (param)->default_def) == SSA_NAME))
853             {
854               tree name = var_ann (param)->default_def;
855               tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
856               tree phi;
857
858               var_ann (param)->default_def = new_name;
859               phi = create_phi_node (name, first);
860               SSA_NAME_DEF_STMT (name) = phi;
861               add_phi_arg (&phi, new_name, first->pred);
862             }
863           phis_constructed = true;
864         }
865
866       if (act->add && !a_acc)
867         {
868           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
869
870           tmp = create_tmp_var (ret_type, "add_acc");
871           add_referenced_tmp_var (tmp);
872
873           phi = create_phi_node (tmp, first);
874           add_phi_arg (&phi, build_int_cst (ret_type, 0), first->pred);
875           a_acc = PHI_RESULT (phi);
876         }
877
878       if (act->mult && !m_acc)
879         {
880           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
881
882           tmp = create_tmp_var (ret_type, "mult_acc");
883           add_referenced_tmp_var (tmp);
884
885           phi = create_phi_node (tmp, first);
886           add_phi_arg (&phi, build_int_cst (ret_type, 1), first->pred);
887           m_acc = PHI_RESULT (phi);
888         }
889     }
890
891   for (; tailcalls; tailcalls = next)
892     {
893       next = tailcalls->next;
894       changed |= optimize_tail_call (tailcalls, opt_tailcalls);
895       free (tailcalls);
896     }
897
898   if (a_acc || m_acc)
899     {
900       /* Modify the remaining return statements.  */
901       for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
902         {
903           stmt = last_stmt (e->src);
904
905           if (stmt
906               && TREE_CODE (stmt) == RETURN_EXPR)
907             adjust_return_value (e->src, m_acc, a_acc);
908         }
909     }
910
911   if (changed)
912     {
913       free_dominance_info (CDI_DOMINATORS);
914       cleanup_tree_cfg ();
915     }
916 }
917
918 static void
919 execute_tail_recursion (void)
920 {
921   tree_optimize_tail_calls_1 (false);
922 }
923
924 static bool
925 gate_tail_calls (void)
926 {
927   return flag_optimize_sibling_calls != 0;
928 }
929
930 static void
931 execute_tail_calls (void)
932 {
933   tree_optimize_tail_calls_1 (true);
934 }
935
936 struct tree_opt_pass pass_tail_recursion = 
937 {
938   "tailr",                              /* name */
939   NULL,                                 /* gate */
940   execute_tail_recursion,               /* execute */
941   NULL,                                 /* sub */
942   NULL,                                 /* next */
943   0,                                    /* static_pass_number */
944   0,                                    /* tv_id */
945   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
946   0,                                    /* properties_provided */
947   0,                                    /* properties_destroyed */
948   0,                                    /* todo_flags_start */
949   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
950   0                                     /* letter */
951 };
952
953 struct tree_opt_pass pass_tail_calls = 
954 {
955   "tailc",                              /* name */
956   gate_tail_calls,                      /* gate */
957   execute_tail_calls,                   /* execute */
958   NULL,                                 /* sub */
959   NULL,                                 /* next */
960   0,                                    /* static_pass_number */
961   0,                                    /* tv_id */
962   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
963   0,                                    /* properties_provided */
964   0,                                    /* properties_destroyed */
965   0,                                    /* todo_flags_start */
966   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
967   0                                     /* letter */
968 };