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