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