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