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