Branch data Line data Source code
1 : : /* Tail call optimization on trees.
2 : : Copyright (C) 2003-2025 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 "intl.h"
44 : : #include "common/common-target.h"
45 : : #include "ipa-utils.h"
46 : : #include "tree-ssa-live.h"
47 : : #include "diagnostic-core.h"
48 : : #include "gimple-range.h"
49 : : #include "alloc-pool.h"
50 : : #include "sreal.h"
51 : : #include "symbol-summary.h"
52 : : #include "ipa-cp.h"
53 : : #include "ipa-prop.h"
54 : :
55 : : /* The file implements the tail recursion elimination. It is also used to
56 : : analyze the tail calls in general, passing the results to the rtl level
57 : : where they are used for sibcall optimization.
58 : :
59 : : In addition to the standard tail recursion elimination, we handle the most
60 : : trivial cases of making the call tail recursive by creating accumulators.
61 : : For example the following function
62 : :
63 : : int sum (int n)
64 : : {
65 : : if (n > 0)
66 : : return n + sum (n - 1);
67 : : else
68 : : return 0;
69 : : }
70 : :
71 : : is transformed into
72 : :
73 : : int sum (int n)
74 : : {
75 : : int acc = 0;
76 : :
77 : : while (n > 0)
78 : : acc += n--;
79 : :
80 : : return acc;
81 : : }
82 : :
83 : : To do this, we maintain two accumulators (a_acc and m_acc) that indicate
84 : : when we reach the return x statement, we should return a_acc + x * m_acc
85 : : instead. They are initially initialized to 0 and 1, respectively,
86 : : so the semantics of the function is obviously preserved. If we are
87 : : guaranteed that the value of the accumulator never change, we
88 : : omit the accumulator.
89 : :
90 : : There are three cases how the function may exit. The first one is
91 : : handled in adjust_return_value, the other two in adjust_accumulator_values
92 : : (the second case is actually a special case of the third one and we
93 : : present it separately just for clarity):
94 : :
95 : : 1) Just return x, where x is not in any of the remaining special shapes.
96 : : We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
97 : :
98 : : 2) return f (...), where f is the current function, is rewritten in a
99 : : classical tail-recursion elimination way, into assignment of arguments
100 : : and jump to the start of the function. Values of the accumulators
101 : : are unchanged.
102 : :
103 : : 3) return a + m * f(...), where a and m do not depend on call to f.
104 : : To preserve the semantics described before we want this to be rewritten
105 : : in such a way that we finally return
106 : :
107 : : a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
108 : :
109 : : I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
110 : : eliminate the tail call to f. Special cases when the value is just
111 : : added or just multiplied are obtained by setting a = 0 or m = 1.
112 : :
113 : : TODO -- it is possible to do similar tricks for other operations. */
114 : :
115 : : /* A structure that describes the tailcall. */
116 : :
117 : : struct tailcall
118 : : {
119 : : /* The iterator pointing to the call statement. */
120 : : gimple_stmt_iterator call_gsi;
121 : :
122 : : /* True if it is a call to the current function. */
123 : : bool tail_recursion;
124 : :
125 : : /* The return value of the caller is mult * f + add, where f is the return
126 : : value of the call. */
127 : : tree mult, add;
128 : :
129 : : /* Next tailcall in the chain. */
130 : : struct tailcall *next;
131 : : };
132 : :
133 : : /* The variables holding the value of multiplicative and additive
134 : : accumulator. */
135 : : static tree m_acc, a_acc;
136 : :
137 : : /* Bitmap with a bit for each function parameter which is set to true if we
138 : : have to copy the parameter for conversion of tail-recursive calls. */
139 : :
140 : : static bitmap tailr_arg_needs_copy;
141 : :
142 : : static void maybe_error_musttail (gcall *call, const char *err);
143 : :
144 : : /* Returns false when the function is not suitable for tail call optimization
145 : : from some reason (e.g. if it takes variable number of arguments). CALL
146 : : is call to report for. */
147 : :
148 : : static bool
149 : 1477437 : suitable_for_tail_opt_p (gcall *call)
150 : : {
151 : 1477437 : if (cfun->stdarg)
152 : : {
153 : 18284 : maybe_error_musttail (call, _("caller uses stdargs"));
154 : 18284 : return false;
155 : : }
156 : :
157 : : return true;
158 : : }
159 : :
160 : : /* Returns false when the function is not suitable for tail call optimization
161 : : for some reason (e.g. if it takes variable number of arguments).
162 : : This test must pass in addition to suitable_for_tail_opt_p in order to make
163 : : tail call discovery happen. CALL is call to report error for. */
164 : :
165 : : static bool
166 : 1459153 : suitable_for_tail_call_opt_p (gcall *call)
167 : : {
168 : 1459153 : tree param;
169 : :
170 : : /* alloca (until we have stack slot life analysis) inhibits
171 : : sibling call optimizations, but not tail recursion. */
172 : 1459153 : if (cfun->calls_alloca)
173 : : {
174 : 14325 : maybe_error_musttail (call, _("caller uses alloca"));
175 : 14325 : return false;
176 : : }
177 : :
178 : : /* If we are using sjlj exceptions, we may need to add a call to
179 : : _Unwind_SjLj_Unregister at exit of the function. Which means
180 : : that we cannot do any sibcall transformations. */
181 : 1444828 : if (targetm_common.except_unwind_info (&global_options) == UI_SJLJ
182 : 1444828 : && current_function_has_exception_handlers ())
183 : : {
184 : 0 : maybe_error_musttail (call, _("caller uses sjlj exceptions"));
185 : 0 : return false;
186 : : }
187 : :
188 : : /* Any function that calls setjmp might have longjmp called from
189 : : any called function. ??? We really should represent this
190 : : properly in the CFG so that this needn't be special cased. */
191 : 1444828 : if (cfun->calls_setjmp)
192 : : {
193 : 140 : maybe_error_musttail (call, _("caller uses setjmp"));
194 : 140 : return false;
195 : : }
196 : :
197 : : /* Various targets don't handle tail calls correctly in functions
198 : : that call __builtin_eh_return. */
199 : 1444688 : if (cfun->calls_eh_return)
200 : : {
201 : 8 : maybe_error_musttail (call, _("caller uses __builtin_eh_return"));
202 : 8 : return false;
203 : : }
204 : :
205 : : /* ??? It is OK if the argument of a function is taken in some cases,
206 : : but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
207 : 1444680 : for (param = DECL_ARGUMENTS (current_function_decl);
208 : 4246977 : param;
209 : 2802297 : param = DECL_CHAIN (param))
210 : 2815677 : if (TREE_ADDRESSABLE (param))
211 : : {
212 : 13380 : maybe_error_musttail (call, _("address of caller arguments taken"));
213 : 13380 : return false;
214 : : }
215 : :
216 : : return true;
217 : : }
218 : :
219 : : /* Checks whether the expression EXPR in stmt AT is independent of the
220 : : statement pointed to by GSI (in a sense that we already know EXPR's value
221 : : at GSI). We use the fact that we are only called from the chain of
222 : : basic blocks that have only single successor. Returns the expression
223 : : containing the value of EXPR at GSI. */
224 : :
225 : : static tree
226 : 21899 : independent_of_stmt_p (tree expr, gimple *at, gimple_stmt_iterator gsi,
227 : : bitmap to_move)
228 : : {
229 : 21899 : basic_block bb, call_bb, at_bb;
230 : 21899 : edge e;
231 : 21899 : edge_iterator ei;
232 : :
233 : 21899 : if (is_gimple_min_invariant (expr))
234 : : return expr;
235 : :
236 : 5585 : if (TREE_CODE (expr) != SSA_NAME)
237 : : return NULL_TREE;
238 : :
239 : 5585 : if (bitmap_bit_p (to_move, SSA_NAME_VERSION (expr)))
240 : : return expr;
241 : :
242 : : /* Mark the blocks in the chain leading to the end. */
243 : 5564 : at_bb = gimple_bb (at);
244 : 5564 : call_bb = gimple_bb (gsi_stmt (gsi));
245 : 6376 : for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
246 : 812 : bb->aux = &bb->aux;
247 : 5564 : bb->aux = &bb->aux;
248 : :
249 : 5682 : while (1)
250 : : {
251 : 5682 : at = SSA_NAME_DEF_STMT (expr);
252 : 5682 : bb = gimple_bb (at);
253 : :
254 : : /* The default definition or defined before the chain. */
255 : 5682 : if (!bb || !bb->aux)
256 : : break;
257 : :
258 : 3091 : if (bb == call_bb)
259 : : {
260 : 18517 : for (; !gsi_end_p (gsi); gsi_next (&gsi))
261 : 15732 : if (gsi_stmt (gsi) == at)
262 : : break;
263 : :
264 : 2951 : if (!gsi_end_p (gsi))
265 : 166 : expr = NULL_TREE;
266 : : break;
267 : : }
268 : :
269 : 140 : if (gimple_code (at) != GIMPLE_PHI)
270 : : {
271 : : expr = NULL_TREE;
272 : : break;
273 : : }
274 : :
275 : 162 : FOR_EACH_EDGE (e, ei, bb->preds)
276 : 162 : if (e->src->aux)
277 : : break;
278 : 140 : gcc_assert (e);
279 : :
280 : 140 : expr = PHI_ARG_DEF_FROM_EDGE (at, e);
281 : 140 : if (TREE_CODE (expr) != SSA_NAME)
282 : : {
283 : : /* The value is a constant. */
284 : : break;
285 : : }
286 : : }
287 : :
288 : : /* Unmark the blocks. */
289 : 6376 : for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
290 : 812 : bb->aux = NULL;
291 : 5564 : bb->aux = NULL;
292 : :
293 : 5564 : return expr;
294 : : }
295 : :
296 : : enum par { FAIL, OK, TRY_MOVE };
297 : :
298 : : /* Simulates the effect of an assignment STMT on the return value of the tail
299 : : recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
300 : : additive factor for the real return value. */
301 : :
302 : : static par
303 : 109850 : process_assignment (gassign *stmt,
304 : : gimple_stmt_iterator call, tree *m,
305 : : tree *a, tree *ass_var, bitmap to_move)
306 : : {
307 : 109850 : tree op0, op1 = NULL_TREE, non_ass_var = NULL_TREE;
308 : 109850 : tree dest = gimple_assign_lhs (stmt);
309 : 109850 : enum tree_code code = gimple_assign_rhs_code (stmt);
310 : 109850 : enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
311 : 109850 : tree src_var = gimple_assign_rhs1 (stmt);
312 : :
313 : : /* See if this is a simple copy operation of an SSA name to the function
314 : : result. In that case we may have a simple tail call. Ignore type
315 : : conversions that can never produce extra code between the function
316 : : call and the function return. */
317 : 53750 : if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt))
318 : 130290 : && src_var == *ass_var)
319 : : {
320 : : /* Reject a tailcall if the type conversion might need
321 : : additional code. */
322 : 20437 : if (gimple_assign_cast_p (stmt))
323 : : {
324 : 17972 : if (TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var)))
325 : : return FAIL;
326 : :
327 : : /* Even if the type modes are the same, if the precision of the
328 : : type is smaller than mode's precision,
329 : : reduce_to_bit_field_precision would generate additional code. */
330 : 16392 : if (INTEGRAL_TYPE_P (TREE_TYPE (dest))
331 : 15901 : && !type_has_mode_precision_p (TREE_TYPE (dest)))
332 : : return FAIL;
333 : : }
334 : :
335 : 10628 : *ass_var = dest;
336 : 10628 : return OK;
337 : : }
338 : :
339 : 89413 : switch (rhs_class)
340 : : {
341 : 30605 : case GIMPLE_BINARY_RHS:
342 : 30605 : op1 = gimple_assign_rhs2 (stmt);
343 : :
344 : : /* Fall through. */
345 : :
346 : 35407 : case GIMPLE_UNARY_RHS:
347 : 35407 : op0 = gimple_assign_rhs1 (stmt);
348 : 35407 : break;
349 : :
350 : : default:
351 : : return FAIL;
352 : : }
353 : :
354 : : /* Accumulator optimizations will reverse the order of operations.
355 : : We can only do that for floating-point types if we're assuming
356 : : that addition and multiplication are associative. */
357 : 35407 : if (!flag_associative_math)
358 : 35065 : if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
359 : : return FAIL;
360 : :
361 : 31420 : if (rhs_class == GIMPLE_UNARY_RHS
362 : 4483 : && op0 == *ass_var)
363 : : ;
364 : 29396 : else if (op0 == *ass_var
365 : 29396 : && (non_ass_var = independent_of_stmt_p (op1, stmt, call,
366 : : to_move)))
367 : : ;
368 : 13315 : else if (*ass_var
369 : 6581 : && op1 == *ass_var
370 : 18995 : && (non_ass_var = independent_of_stmt_p (op0, stmt, call,
371 : : to_move)))
372 : : ;
373 : : else
374 : 7717 : return TRY_MOVE;
375 : :
376 : 23703 : switch (code)
377 : : {
378 : 6482 : case PLUS_EXPR:
379 : 6482 : *a = non_ass_var;
380 : 6482 : *ass_var = dest;
381 : 6482 : return OK;
382 : :
383 : 324 : case POINTER_PLUS_EXPR:
384 : 324 : if (op0 != *ass_var)
385 : : return FAIL;
386 : 83 : *a = non_ass_var;
387 : 83 : *ass_var = dest;
388 : 83 : return OK;
389 : :
390 : 368 : case MULT_EXPR:
391 : 368 : *m = non_ass_var;
392 : 368 : *ass_var = dest;
393 : 368 : return OK;
394 : :
395 : 113 : case NEGATE_EXPR:
396 : 113 : *m = build_minus_one_cst (TREE_TYPE (op0));
397 : 113 : *ass_var = dest;
398 : 113 : return OK;
399 : :
400 : 1526 : case MINUS_EXPR:
401 : 1526 : if (*ass_var == op0)
402 : 114 : *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
403 : : else
404 : : {
405 : 1412 : *m = build_minus_one_cst (TREE_TYPE (non_ass_var));
406 : 1412 : *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
407 : : }
408 : :
409 : 1526 : *ass_var = dest;
410 : 1526 : return OK;
411 : :
412 : : default:
413 : : return FAIL;
414 : : }
415 : : }
416 : :
417 : : /* Propagate VAR through phis on edge E. */
418 : :
419 : : static tree
420 : 495618 : propagate_through_phis (tree var, edge e)
421 : : {
422 : 495618 : basic_block dest = e->dest;
423 : 495618 : gphi_iterator gsi;
424 : :
425 : 940696 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
426 : : {
427 : 506221 : gphi *phi = gsi.phi ();
428 : 506221 : if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
429 : 61143 : return PHI_RESULT (phi);
430 : : }
431 : : return var;
432 : : }
433 : :
434 : : /* Report an error for failing to tail convert must call CALL
435 : : with error message ERR. Also clear the flag to prevent further
436 : : errors. */
437 : :
438 : : static void
439 : 714686 : maybe_error_musttail (gcall *call, const char *err)
440 : : {
441 : 714686 : if (gimple_call_must_tail_p (call))
442 : : {
443 : 27 : error_at (call->location, "cannot tail-call: %s", err);
444 : : /* Avoid another error. ??? If there are multiple reasons why tail
445 : : calls fail it might be useful to report them all to avoid
446 : : whack-a-mole for the user. But currently there is too much
447 : : redundancy in the reporting, so keep it simple. */
448 : 27 : gimple_call_set_must_tail (call, false); /* Avoid another error. */
449 : 27 : gimple_call_set_tail (call, false);
450 : : }
451 : 714686 : if (dump_file)
452 : : {
453 : 45 : print_gimple_stmt (dump_file, call, 0, TDF_SLIM);
454 : 45 : fprintf (dump_file, "Cannot convert: %s\n", err);
455 : : }
456 : 714686 : }
457 : :
458 : : /* Argument for compute_live_vars/live_vars_at_stmt and what compute_live_vars
459 : : returns. Computed lazily, but just once for the function. */
460 : : static live_vars_map *live_vars;
461 : : static vec<bitmap_head> live_vars_vec;
462 : :
463 : : /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
464 : : added to the start of RET. When ONLY_MUSTTAIL is set only handle musttail.
465 : : Update OPT_TAILCALLS as output parameter. */
466 : :
467 : : static void
468 : 6751752 : find_tail_calls (basic_block bb, struct tailcall **ret, bool only_musttail,
469 : : bool &opt_tailcalls)
470 : : {
471 : 6751752 : tree ass_var = NULL_TREE, ret_var, func, param;
472 : 6751752 : gimple *stmt;
473 : 6751752 : gcall *call = NULL;
474 : 6751752 : gimple_stmt_iterator gsi, agsi;
475 : 6751752 : bool tail_recursion;
476 : 6751752 : struct tailcall *nw;
477 : 6751752 : edge e;
478 : 6751752 : tree m, a;
479 : 6751752 : basic_block abb;
480 : 6751752 : size_t idx;
481 : 6751752 : tree var;
482 : :
483 : 6751752 : if (!single_succ_p (bb))
484 : : {
485 : : /* If there is an abnormal edge assume it's the only extra one.
486 : : Tolerate that case so that we can give better error messages
487 : : for musttail later. */
488 : 1704571 : if (!has_abnormal_or_eh_outgoing_edge_p (bb))
489 : : {
490 : 1646143 : if (dump_file)
491 : 106 : fprintf (dump_file, "Basic block %d has extra exit edges\n",
492 : : bb->index);
493 : 5961161 : return;
494 : : }
495 : 58428 : if (!cfun->has_musttail)
496 : : return;
497 : : }
498 : :
499 : 5047186 : bool bad_stmt = false;
500 : 5047186 : gimple *last_stmt = nullptr;
501 : 21687138 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
502 : : {
503 : 14119353 : stmt = gsi_stmt (gsi);
504 : :
505 : : /* Ignore labels, returns, nops, clobbers and debug stmts. */
506 : 14119353 : if (gimple_code (stmt) == GIMPLE_LABEL
507 : : || gimple_code (stmt) == GIMPLE_RETURN
508 : : || gimple_code (stmt) == GIMPLE_NOP
509 : : || gimple_code (stmt) == GIMPLE_PREDICT
510 : 10577674 : || gimple_clobber_p (stmt)
511 : 9656438 : || is_gimple_debug (stmt))
512 : 10642177 : continue;
513 : :
514 : 3477176 : if (!last_stmt)
515 : 2854844 : last_stmt = stmt;
516 : : /* Check for a call. */
517 : 3477176 : if (is_gimple_call (stmt))
518 : : {
519 : 1477440 : call = as_a <gcall *> (stmt);
520 : : /* Handle only musttail calls when not optimizing. */
521 : 1477440 : if (only_musttail && !gimple_call_must_tail_p (call))
522 : : return;
523 : 1477438 : if (bad_stmt)
524 : : {
525 : 2 : maybe_error_musttail (call,
526 : 1 : _("memory reference or volatile after "
527 : : "call"));
528 : 1 : return;
529 : : }
530 : 1477437 : ass_var = gimple_call_lhs (call);
531 : 1477437 : break;
532 : : }
533 : :
534 : : /* Allow simple copies between local variables, even if they're
535 : : aggregates. */
536 : 1999736 : if (is_gimple_assign (stmt)
537 : 1978966 : && auto_var_in_fn_p (gimple_assign_lhs (stmt), cfun->decl)
538 : 2050438 : && auto_var_in_fn_p (gimple_assign_rhs1 (stmt), cfun->decl))
539 : 24710 : continue;
540 : :
541 : : /* If the statement references memory or volatile operands, fail. */
542 : 1975026 : if (gimple_references_memory_p (stmt)
543 : 13444493 : || gimple_has_volatile_ops (stmt))
544 : : {
545 : 1049154 : if (dump_file)
546 : : {
547 : 25 : fprintf (dump_file, "Cannot handle ");
548 : 25 : print_gimple_stmt (dump_file, stmt, 0);
549 : : }
550 : 1049154 : bad_stmt = true;
551 : 1049154 : if (!cfun->has_musttail)
552 : : break;
553 : : }
554 : : }
555 : :
556 : 5047183 : if (bad_stmt)
557 : : return;
558 : :
559 : 3998033 : if (gsi_end_p (gsi))
560 : : {
561 : 2520596 : edge_iterator ei;
562 : : /* Recurse to the predecessors. */
563 : 6068188 : FOR_EACH_EDGE (e, ei, bb->preds)
564 : 3547592 : find_tail_calls (e->src, ret, only_musttail, opt_tailcalls);
565 : :
566 : 2520596 : return;
567 : : }
568 : :
569 : 1477437 : if (!suitable_for_tail_opt_p (call))
570 : : return;
571 : :
572 : 1459153 : if (!suitable_for_tail_call_opt_p (call))
573 : 27853 : opt_tailcalls = false;
574 : :
575 : : /* If the LHS of our call is not just a simple register or local
576 : : variable, we can't transform this into a tail or sibling call.
577 : : This situation happens, in (e.g.) "*p = foo()" where foo returns a
578 : : struct. In this case we won't have a temporary here, but we need
579 : : to carry out the side effect anyway, so tailcall is impossible.
580 : :
581 : : ??? In some situations (when the struct is returned in memory via
582 : : invisible argument) we could deal with this, e.g. by passing 'p'
583 : : itself as that argument to foo, but it's too early to do this here,
584 : : and expand_call() will not handle it anyway. If it ever can, then
585 : : we need to revisit this here, to allow that situation. */
586 : 1459153 : if (ass_var
587 : 404459 : && !is_gimple_reg (ass_var)
588 : 1498585 : && !auto_var_in_fn_p (ass_var, cfun->decl))
589 : : {
590 : 6916 : maybe_error_musttail (call, _("return value in memory"));
591 : 6916 : return;
592 : : }
593 : :
594 : 1452237 : if (cfun->calls_setjmp)
595 : : {
596 : 160 : maybe_error_musttail (call, _("caller uses setjmp"));
597 : 160 : return;
598 : : }
599 : :
600 : : /* If the call might throw an exception that wouldn't propagate out of
601 : : cfun, we can't transform to a tail or sibling call (82081). */
602 : 1452077 : if ((stmt_could_throw_p (cfun, stmt)
603 : 2886325 : && !stmt_can_throw_external (cfun, stmt)) || !single_succ_p (bb))
604 : : {
605 : 17829 : if (stmt == last_stmt)
606 : 17721 : maybe_error_musttail (call,
607 : 17721 : _("call may throw exception that does not "
608 : : "propagate"));
609 : : else
610 : 108 : maybe_error_musttail (call, _("code between call and return"));
611 : 17829 : return;
612 : : }
613 : :
614 : : /* If the function returns a value, then at present, the tail call
615 : : must return the same type of value. There is conceptually a copy
616 : : between the object returned by the tail call candidate and the
617 : : object returned by CFUN itself.
618 : :
619 : : This means that if we have:
620 : :
621 : : lhs = f (&<retval>); // f reads from <retval>
622 : : // (lhs is usually also <retval>)
623 : :
624 : : there is a copy between the temporary object returned by f and lhs,
625 : : meaning that any use of <retval> in f occurs before the assignment
626 : : to lhs begins. Thus the <retval> that is live on entry to the call
627 : : to f is really an independent local variable V that happens to be
628 : : stored in the RESULT_DECL rather than a local VAR_DECL.
629 : :
630 : : Turning this into a tail call would remove the copy and make the
631 : : lifetimes of the return value and V overlap. The same applies to
632 : : tail recursion, since if f can read from <retval>, we have to assume
633 : : that CFUN might already have written to <retval> before the call.
634 : :
635 : : The problem doesn't apply when <retval> is passed by value, but that
636 : : isn't a case we handle anyway. */
637 : 1434248 : tree result_decl = DECL_RESULT (cfun->decl);
638 : 1434248 : if (result_decl
639 : 1434248 : && may_be_aliased (result_decl)
640 : 1438171 : && ref_maybe_used_by_stmt_p (call, result_decl, false))
641 : : {
642 : 948 : maybe_error_musttail (call, _("return value used after call"));
643 : 948 : return;
644 : : }
645 : :
646 : : /* We found the call, check whether it is suitable. */
647 : 1433300 : tail_recursion = false;
648 : 1433300 : func = gimple_call_fndecl (call);
649 : 1433300 : if (func
650 : 1359981 : && !fndecl_built_in_p (func)
651 : 1024746 : && recursive_call_p (current_function_decl, func)
652 : 1436353 : && !only_musttail)
653 : : {
654 : 3046 : tree arg;
655 : :
656 : 3046 : for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
657 : 9327 : param && idx < gimple_call_num_args (call);
658 : 6281 : param = DECL_CHAIN (param), idx ++)
659 : : {
660 : 6636 : arg = gimple_call_arg (call, idx);
661 : 6636 : if (param != arg)
662 : : {
663 : : /* Make sure there are no problems with copying. The parameter
664 : : have a copyable type and the two arguments must have reasonably
665 : : equivalent types. The latter requirement could be relaxed if
666 : : we emitted a suitable type conversion statement. */
667 : 6627 : if (!is_gimple_reg_type (TREE_TYPE (param))
668 : 13083 : || !useless_type_conversion_p (TREE_TYPE (param),
669 : 6456 : TREE_TYPE (arg)))
670 : : break;
671 : :
672 : : /* The parameter should be a real operand, so that phi node
673 : : created for it at the start of the function has the meaning
674 : : of copying the value. This test implies is_gimple_reg_type
675 : : from the previous condition, however this one could be
676 : : relaxed by being more careful with copying the new value
677 : : of the parameter (emitting appropriate GIMPLE_ASSIGN and
678 : : updating the virtual operands). */
679 : 6299 : if (!is_gimple_reg (param))
680 : : break;
681 : : }
682 : : }
683 : 3046 : if (idx == gimple_call_num_args (call) && !param)
684 : 1433300 : tail_recursion = true;
685 : : }
686 : :
687 : : /* Compute live vars if not computed yet. */
688 : 1433300 : if (live_vars == NULL)
689 : : {
690 : 1394850 : unsigned int cnt = 0;
691 : 12089512 : FOR_EACH_LOCAL_DECL (cfun, idx, var)
692 : 9491068 : if (VAR_P (var)
693 : 9491068 : && auto_var_in_fn_p (var, cfun->decl)
694 : 18861967 : && may_be_aliased (var))
695 : : {
696 : 788091 : if (live_vars == NULL)
697 : 195032 : live_vars = new live_vars_map;
698 : 788091 : live_vars->put (DECL_UID (var), cnt++);
699 : : }
700 : 1394850 : if (live_vars)
701 : 195032 : live_vars_vec = compute_live_vars (cfun, live_vars);
702 : : }
703 : :
704 : : /* Determine a bitmap of variables which are still in scope after the
705 : : call. */
706 : 1433300 : bitmap local_live_vars = NULL;
707 : 1433300 : if (live_vars)
708 : 233482 : local_live_vars = live_vars_at_stmt (live_vars_vec, live_vars, call);
709 : :
710 : : /* Make sure the tail invocation of this function does not indirectly
711 : : refer to local variables. (Passing variables directly by value
712 : : is OK.) */
713 : 12478694 : FOR_EACH_LOCAL_DECL (cfun, idx, var)
714 : : {
715 : 9984053 : if (TREE_CODE (var) != PARM_DECL
716 : 9984053 : && auto_var_in_fn_p (var, cfun->decl)
717 : 9907875 : && may_be_aliased (var)
718 : 10693520 : && (ref_maybe_used_by_stmt_p (call, var, false)
719 : 313484 : || call_may_clobber_ref_p (call, var, false)))
720 : : {
721 : 454408 : if (!VAR_P (var))
722 : : {
723 : 0 : if (local_live_vars)
724 : 0 : BITMAP_FREE (local_live_vars);
725 : 0 : maybe_error_musttail (call,
726 : 0 : _("call invocation refers to locals"));
727 : 0 : return;
728 : : }
729 : : else
730 : : {
731 : 454408 : unsigned int *v = live_vars->get (DECL_UID (var));
732 : 454408 : if (bitmap_bit_p (local_live_vars, *v))
733 : : {
734 : 180703 : BITMAP_FREE (local_live_vars);
735 : 361406 : maybe_error_musttail (call,
736 : 180703 : _("call invocation refers to locals"));
737 : 180703 : return;
738 : : }
739 : : }
740 : : }
741 : : }
742 : :
743 : 1252597 : if (local_live_vars)
744 : 52779 : BITMAP_FREE (local_live_vars);
745 : :
746 : : /* Now check the statements after the call. None of them has virtual
747 : : operands, so they may only depend on the call through its return
748 : : value. The return value should also be dependent on each of them,
749 : : since we are running after dce. */
750 : 1252597 : m = NULL_TREE;
751 : 1252597 : a = NULL_TREE;
752 : 1252597 : auto_bitmap to_move_defs;
753 : 1252597 : auto_vec<gimple *> to_move_stmts;
754 : :
755 : 1252597 : abb = bb;
756 : 1252597 : agsi = gsi;
757 : 2913226 : while (1)
758 : : {
759 : 2913226 : tree tmp_a = NULL_TREE;
760 : 2913226 : tree tmp_m = NULL_TREE;
761 : 2913226 : gsi_next (&agsi);
762 : :
763 : 3408844 : while (gsi_end_p (agsi))
764 : : {
765 : 495618 : ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
766 : 495618 : abb = single_succ (abb);
767 : 991236 : agsi = gsi_start_bb (abb);
768 : : }
769 : :
770 : 2913226 : stmt = gsi_stmt (agsi);
771 : 2913226 : if (gimple_code (stmt) == GIMPLE_RETURN)
772 : : break;
773 : :
774 : 3392914 : if (gimple_code (stmt) == GIMPLE_LABEL
775 : 1725579 : || gimple_code (stmt) == GIMPLE_NOP
776 : 1725579 : || gimple_code (stmt) == GIMPLE_PREDICT
777 : 1707594 : || gimple_clobber_p (stmt)
778 : 3307995 : || is_gimple_debug (stmt))
779 : 1641429 : continue;
780 : :
781 : 110110 : if (gimple_code (stmt) != GIMPLE_ASSIGN)
782 : : {
783 : 260 : maybe_error_musttail (call, _("unhandled code after call"));
784 : 91143 : return;
785 : : }
786 : :
787 : : /* This is a gimple assign. */
788 : 109850 : par ret = process_assignment (as_a <gassign *> (stmt), gsi,
789 : : &tmp_m, &tmp_a, &ass_var, to_move_defs);
790 : 109850 : if (ret == FAIL || (ret == TRY_MOVE && !tail_recursion))
791 : : {
792 : 90609 : maybe_error_musttail (call, _("return value changed after call"));
793 : 90609 : return;
794 : : }
795 : 19241 : else if (ret == TRY_MOVE)
796 : : {
797 : : /* Do not deal with checking dominance, the real fix is to
798 : : do path isolation for the transform phase anyway, removing
799 : : the need to compute the accumulators with new stmts. */
800 : 41 : if (abb != bb)
801 : : return;
802 : 81 : for (unsigned opno = 1; opno < gimple_num_ops (stmt); ++opno)
803 : : {
804 : 54 : tree op = gimple_op (stmt, opno);
805 : 54 : if (independent_of_stmt_p (op, stmt, gsi, to_move_defs) != op)
806 : : return;
807 : : }
808 : 54 : bitmap_set_bit (to_move_defs,
809 : 27 : SSA_NAME_VERSION (gimple_assign_lhs (stmt)));
810 : 27 : to_move_stmts.safe_push (stmt);
811 : 27 : continue;
812 : 27 : }
813 : :
814 : 19200 : if (tmp_a)
815 : : {
816 : 8091 : tree type = TREE_TYPE (tmp_a);
817 : 8091 : if (a)
818 : 297 : a = fold_build2 (PLUS_EXPR, type, fold_convert (type, a), tmp_a);
819 : : else
820 : : a = tmp_a;
821 : : }
822 : 19200 : if (tmp_m)
823 : : {
824 : 1893 : tree type = TREE_TYPE (tmp_m);
825 : 1893 : if (m)
826 : 75 : m = fold_build2 (MULT_EXPR, type, fold_convert (type, m), tmp_m);
827 : : else
828 : : m = tmp_m;
829 : :
830 : 1893 : if (a)
831 : 1422 : a = fold_build2 (MULT_EXPR, type, fold_convert (type, a), tmp_m);
832 : : }
833 : : }
834 : :
835 : : /* See if this is a tail call we can handle. */
836 : 1161714 : ret_var = gimple_return_retval (as_a <greturn *> (stmt));
837 : :
838 : : /* We may proceed if there either is no return value, or the return value
839 : : is identical to the call's return or if the return decl is an empty type
840 : : variable and the call's return was not assigned. */
841 : 1161714 : if (ret_var
842 : 1161714 : && (ret_var != ass_var
843 : 369290 : && !(is_empty_type (TREE_TYPE (ret_var)) && !ass_var)))
844 : : {
845 : 368472 : bool ok = false;
846 : 368472 : value_range val;
847 : 368472 : tree valr;
848 : : /* If IPA-VRP proves called function always returns a singleton range,
849 : : the return value is replaced by the only value in that range.
850 : : For tail call purposes, pretend such replacement didn't happen. */
851 : 368472 : if (ass_var == NULL_TREE
852 : 368468 : && !tail_recursion
853 : 736841 : && TREE_CONSTANT (ret_var))
854 : 193733 : if (tree type = gimple_range_type (call))
855 : 11958 : if (tree callee = gimple_call_fndecl (call))
856 : 11684 : if ((INTEGRAL_TYPE_P (type) || SCALAR_FLOAT_TYPE_P (type))
857 : 10518 : && useless_type_conversion_p (TREE_TYPE (TREE_TYPE (callee)),
858 : : type)
859 : 10510 : && useless_type_conversion_p (TREE_TYPE (ret_var), type)
860 : 8456 : && ipa_return_value_range (val, callee)
861 : 5116 : && val.singleton_p (&valr)
862 : 16641 : && operand_equal_p (ret_var, valr, 0))
863 : 4774 : ok = true;
864 : 4774 : if (!ok)
865 : : {
866 : 363698 : maybe_error_musttail (call,
867 : 363698 : _("call and return value are different"));
868 : 363698 : return;
869 : : }
870 : 368472 : }
871 : :
872 : : /* If this is not a tail recursive call, we cannot handle addends or
873 : : multiplicands. */
874 : 798016 : if (!tail_recursion && (m || a))
875 : : {
876 : 14850 : maybe_error_musttail (call,
877 : 7425 : _("operations after non tail recursive call"));
878 : 7425 : return;
879 : : }
880 : :
881 : : /* For pointers only allow additions. */
882 : 2023 : if (m && POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
883 : : {
884 : 0 : maybe_error_musttail (call,
885 : 0 : _("tail recursion with pointers can only use "
886 : : "additions"));
887 : 0 : return;
888 : : }
889 : :
890 : : /* Move queued defs. */
891 : 790591 : if (tail_recursion)
892 : : {
893 : : unsigned i;
894 : 2026 : FOR_EACH_VEC_ELT (to_move_stmts, i, stmt)
895 : : {
896 : 3 : gimple_stmt_iterator mgsi = gsi_for_stmt (stmt);
897 : 3 : gsi_move_before (&mgsi, &gsi);
898 : : }
899 : 2023 : if (!tailr_arg_needs_copy)
900 : 992 : tailr_arg_needs_copy = BITMAP_ALLOC (NULL);
901 : 2023 : for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
902 : 6928 : param;
903 : 4905 : param = DECL_CHAIN (param), idx++)
904 : : {
905 : 4905 : tree ddef, arg = gimple_call_arg (call, idx);
906 : 4905 : if (is_gimple_reg (param)
907 : 4896 : && (ddef = ssa_default_def (cfun, param))
908 : 9783 : && (arg != ddef))
909 : 2032 : bitmap_set_bit (tailr_arg_needs_copy, idx);
910 : : }
911 : : }
912 : :
913 : 790591 : nw = XNEW (struct tailcall);
914 : :
915 : 790591 : nw->call_gsi = gsi;
916 : :
917 : 790591 : nw->tail_recursion = tail_recursion;
918 : :
919 : 790591 : nw->mult = m;
920 : 790591 : nw->add = a;
921 : :
922 : 790591 : nw->next = *ret;
923 : 790591 : *ret = nw;
924 : 1252597 : }
925 : :
926 : : /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
927 : :
928 : : static void
929 : 199 : add_successor_phi_arg (edge e, tree var, tree phi_arg)
930 : : {
931 : 199 : gphi_iterator gsi;
932 : :
933 : 412 : for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
934 : 412 : if (PHI_RESULT (gsi.phi ()) == var)
935 : : break;
936 : :
937 : 199 : gcc_assert (!gsi_end_p (gsi));
938 : 199 : add_phi_arg (gsi.phi (), phi_arg, e, UNKNOWN_LOCATION);
939 : 199 : }
940 : :
941 : : /* Creates a GIMPLE statement which computes the operation specified by
942 : : CODE, ACC and OP1 to a new variable with name LABEL and inserts the
943 : : statement in the position specified by GSI. Returns the
944 : : tree node of the statement's result. */
945 : :
946 : : static tree
947 : 175 : adjust_return_value_with_ops (enum tree_code code, const char *label,
948 : : tree acc, tree op1, gimple_stmt_iterator gsi)
949 : : {
950 : :
951 : 175 : tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
952 : 175 : tree result = make_temp_ssa_name (ret_type, NULL, label);
953 : 175 : gassign *stmt;
954 : :
955 : 175 : if (POINTER_TYPE_P (ret_type))
956 : : {
957 : 6 : gcc_assert (code == PLUS_EXPR && TREE_TYPE (acc) == sizetype);
958 : : code = POINTER_PLUS_EXPR;
959 : : }
960 : 175 : if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1))
961 : 175 : && code != POINTER_PLUS_EXPR)
962 : 164 : stmt = gimple_build_assign (result, code, acc, op1);
963 : : else
964 : : {
965 : 11 : tree tem;
966 : 11 : if (code == POINTER_PLUS_EXPR)
967 : 6 : tem = fold_build2 (code, TREE_TYPE (op1), op1, acc);
968 : : else
969 : 5 : tem = fold_build2 (code, TREE_TYPE (op1),
970 : : fold_convert (TREE_TYPE (op1), acc), op1);
971 : 11 : tree rhs = fold_convert (ret_type, tem);
972 : 11 : rhs = force_gimple_operand_gsi (&gsi, rhs,
973 : : false, NULL, true, GSI_SAME_STMT);
974 : 11 : stmt = gimple_build_assign (result, rhs);
975 : : }
976 : :
977 : 175 : gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
978 : 175 : return result;
979 : : }
980 : :
981 : : /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
982 : : the computation specified by CODE and OP1 and insert the statement
983 : : at the position specified by GSI as a new statement. Returns new SSA name
984 : : of updated accumulator. */
985 : :
986 : : static tree
987 : 196 : update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
988 : : gimple_stmt_iterator gsi)
989 : : {
990 : 196 : gassign *stmt;
991 : 196 : tree var = copy_ssa_name (acc);
992 : 196 : if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
993 : 182 : stmt = gimple_build_assign (var, code, acc, op1);
994 : : else
995 : : {
996 : 14 : tree rhs = fold_convert (TREE_TYPE (acc),
997 : : fold_build2 (code,
998 : : TREE_TYPE (op1),
999 : : fold_convert (TREE_TYPE (op1), acc),
1000 : : op1));
1001 : 14 : rhs = force_gimple_operand_gsi (&gsi, rhs,
1002 : : false, NULL, false, GSI_CONTINUE_LINKING);
1003 : 14 : stmt = gimple_build_assign (var, rhs);
1004 : : }
1005 : 196 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1006 : 196 : return var;
1007 : : }
1008 : :
1009 : : /* Adjust the accumulator values according to A and M after GSI, and update
1010 : : the phi nodes on edge BACK. */
1011 : :
1012 : : static void
1013 : 2023 : adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
1014 : : {
1015 : 2023 : tree var, a_acc_arg, m_acc_arg;
1016 : :
1017 : 2023 : if (m)
1018 : 105 : m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT);
1019 : 2023 : if (a)
1020 : 91 : a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT);
1021 : :
1022 : 2023 : a_acc_arg = a_acc;
1023 : 2023 : m_acc_arg = m_acc;
1024 : 2023 : if (a)
1025 : : {
1026 : 91 : if (m_acc)
1027 : : {
1028 : 18 : if (integer_onep (a))
1029 : 1 : var = m_acc;
1030 : : else
1031 : 17 : var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
1032 : : a, gsi);
1033 : : }
1034 : : else
1035 : : var = a;
1036 : :
1037 : 91 : a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
1038 : : }
1039 : :
1040 : 2023 : if (m)
1041 : 105 : m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
1042 : :
1043 : 2023 : if (a_acc)
1044 : 94 : add_successor_phi_arg (back, a_acc, a_acc_arg);
1045 : :
1046 : 2023 : if (m_acc)
1047 : 105 : add_successor_phi_arg (back, m_acc, m_acc_arg);
1048 : 2023 : }
1049 : :
1050 : : /* Adjust value of the return at the end of BB according to M and A
1051 : : accumulators. */
1052 : :
1053 : : static void
1054 : 145 : adjust_return_value (basic_block bb, tree m, tree a)
1055 : : {
1056 : 145 : tree retval;
1057 : 290 : greturn *ret_stmt = as_a <greturn *> (gimple_seq_last_stmt (bb_seq (bb)));
1058 : 145 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
1059 : :
1060 : 145 : gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
1061 : :
1062 : 145 : retval = gimple_return_retval (ret_stmt);
1063 : 145 : if (!retval || retval == error_mark_node)
1064 : 0 : return;
1065 : :
1066 : 145 : if (m)
1067 : 85 : retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
1068 : : gsi);
1069 : 145 : if (a)
1070 : 73 : retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
1071 : : gsi);
1072 : 145 : gimple_return_set_retval (ret_stmt, retval);
1073 : 145 : update_stmt (ret_stmt);
1074 : : }
1075 : :
1076 : : /* Subtract COUNT and FREQUENCY from the basic block and it's
1077 : : outgoing edge. */
1078 : : static void
1079 : 5839 : decrease_profile (basic_block bb, profile_count count)
1080 : : {
1081 : 5839 : bb->count = bb->count - count;
1082 : 5839 : if (!single_succ_p (bb))
1083 : : {
1084 : 2023 : gcc_assert (!EDGE_COUNT (bb->succs));
1085 : : return;
1086 : : }
1087 : : }
1088 : :
1089 : : /* Eliminates tail call described by T. TMP_VARS is a list of
1090 : : temporary variables used to copy the function arguments.
1091 : : Allocates *NEW_LOOP if not already done and initializes it. */
1092 : :
1093 : : static void
1094 : 2023 : eliminate_tail_call (struct tailcall *t, class loop *&new_loop)
1095 : : {
1096 : 2023 : tree param, rslt;
1097 : 2023 : gimple *stmt, *call;
1098 : 2023 : tree arg;
1099 : 2023 : size_t idx;
1100 : 2023 : basic_block bb, first;
1101 : 2023 : edge e;
1102 : 2023 : gphi *phi;
1103 : 2023 : gphi_iterator gpi;
1104 : 2023 : gimple_stmt_iterator gsi;
1105 : 2023 : gimple *orig_stmt;
1106 : :
1107 : 2023 : stmt = orig_stmt = gsi_stmt (t->call_gsi);
1108 : 2023 : bb = gsi_bb (t->call_gsi);
1109 : :
1110 : 2023 : if (dump_file && (dump_flags & TDF_DETAILS))
1111 : : {
1112 : 7 : fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
1113 : : bb->index);
1114 : 7 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1115 : 7 : fprintf (dump_file, "\n");
1116 : : }
1117 : :
1118 : 2023 : gcc_assert (is_gimple_call (stmt));
1119 : :
1120 : 2023 : first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1121 : :
1122 : : /* Remove the code after call_gsi that will become unreachable. The
1123 : : possibly unreachable code in other blocks is removed later in
1124 : : cfg cleanup. */
1125 : 2023 : gsi = t->call_gsi;
1126 : 2023 : gimple_stmt_iterator gsi2 = gsi_last_bb (gimple_bb (gsi_stmt (gsi)));
1127 : 2856 : while (gsi_stmt (gsi2) != gsi_stmt (gsi))
1128 : : {
1129 : 833 : gimple *t = gsi_stmt (gsi2);
1130 : : /* Do not remove the return statement, so that redirect_edge_and_branch
1131 : : sees how the block ends. */
1132 : 833 : if (gimple_code (t) != GIMPLE_RETURN)
1133 : : {
1134 : 603 : gimple_stmt_iterator gsi3 = gsi2;
1135 : 603 : gsi_prev (&gsi2);
1136 : 603 : gsi_remove (&gsi3, true);
1137 : 603 : release_defs (t);
1138 : : }
1139 : : else
1140 : 3086 : gsi_prev (&gsi2);
1141 : : }
1142 : :
1143 : : /* Number of executions of function has reduced by the tailcall. */
1144 : 2023 : e = single_succ_edge (gsi_bb (t->call_gsi));
1145 : :
1146 : 2023 : profile_count count = e->count ();
1147 : :
1148 : : /* When profile is inconsistent and the recursion edge is more frequent
1149 : : than number of executions of functions, scale it down, so we do not end
1150 : : up with 0 executions of entry block. */
1151 : 2023 : if (count >= ENTRY_BLOCK_PTR_FOR_FN (cfun)->count)
1152 : 40 : count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.apply_scale (7, 8);
1153 : 2023 : decrease_profile (EXIT_BLOCK_PTR_FOR_FN (cfun), count);
1154 : 2023 : decrease_profile (ENTRY_BLOCK_PTR_FOR_FN (cfun), count);
1155 : 2023 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1156 : 1793 : decrease_profile (e->dest, count);
1157 : :
1158 : : /* Replace the call by a jump to the start of function. */
1159 : 2023 : e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)),
1160 : : first);
1161 : 2023 : gcc_assert (e);
1162 : 2023 : PENDING_STMT (e) = NULL;
1163 : :
1164 : : /* Add the new loop. */
1165 : 2023 : if (!new_loop)
1166 : : {
1167 : 992 : new_loop = alloc_loop ();
1168 : 992 : new_loop->header = first;
1169 : 992 : new_loop->finite_p = true;
1170 : : }
1171 : : else
1172 : 1031 : gcc_assert (new_loop->header == first);
1173 : :
1174 : : /* Add phi node entries for arguments. The ordering of the phi nodes should
1175 : : be the same as the ordering of the arguments. */
1176 : 2023 : for (param = DECL_ARGUMENTS (current_function_decl),
1177 : 2023 : idx = 0, gpi = gsi_start_phis (first);
1178 : 6928 : param;
1179 : 4905 : param = DECL_CHAIN (param), idx++)
1180 : : {
1181 : 4905 : if (!bitmap_bit_p (tailr_arg_needs_copy, idx))
1182 : 2864 : continue;
1183 : :
1184 : 2041 : arg = gimple_call_arg (stmt, idx);
1185 : 2041 : phi = gpi.phi ();
1186 : 2041 : gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
1187 : :
1188 : 2041 : add_phi_arg (phi, arg, e, gimple_location (stmt));
1189 : 2041 : gsi_next (&gpi);
1190 : : }
1191 : :
1192 : : /* Update the values of accumulators. */
1193 : 2023 : adjust_accumulator_values (t->call_gsi, t->mult, t->add, e);
1194 : :
1195 : 2023 : call = gsi_stmt (t->call_gsi);
1196 : 2023 : rslt = gimple_call_lhs (call);
1197 : 2023 : if (rslt != NULL_TREE && TREE_CODE (rslt) == SSA_NAME)
1198 : : {
1199 : : /* Result of the call will no longer be defined. So adjust the
1200 : : SSA_NAME_DEF_STMT accordingly. */
1201 : 512 : SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
1202 : : }
1203 : :
1204 : 2023 : gsi_remove (&t->call_gsi, true);
1205 : 2023 : release_defs (call);
1206 : 2023 : }
1207 : :
1208 : : /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
1209 : : mark the tailcalls for the sibcall optimization. */
1210 : :
1211 : : static bool
1212 : 790591 : optimize_tail_call (struct tailcall *t, bool opt_tailcalls,
1213 : : class loop *&new_loop)
1214 : : {
1215 : 790591 : if (t->tail_recursion)
1216 : : {
1217 : 2023 : eliminate_tail_call (t, new_loop);
1218 : 2023 : return true;
1219 : : }
1220 : :
1221 : 788568 : if (opt_tailcalls)
1222 : : {
1223 : 168042 : gcall *stmt = as_a <gcall *> (gsi_stmt (t->call_gsi));
1224 : :
1225 : 168042 : gimple_call_set_tail (stmt, true);
1226 : 168042 : cfun->tail_call_marked = true;
1227 : 168042 : if (dump_file && (dump_flags & TDF_DETAILS))
1228 : : {
1229 : 21 : fprintf (dump_file, "Found tail call ");
1230 : 21 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1231 : 21 : fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
1232 : : }
1233 : : }
1234 : :
1235 : : return false;
1236 : : }
1237 : :
1238 : : /* Creates a tail-call accumulator of the same type as the return type of the
1239 : : current function. LABEL is the name used to creating the temporary
1240 : : variable for the accumulator. The accumulator will be inserted in the
1241 : : phis of a basic block BB with single predecessor with an initial value
1242 : : INIT converted to the current function return type. */
1243 : :
1244 : : static tree
1245 : 191 : create_tailcall_accumulator (const char *label, basic_block bb, tree init)
1246 : : {
1247 : 191 : tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
1248 : 191 : if (POINTER_TYPE_P (ret_type))
1249 : 6 : ret_type = sizetype;
1250 : :
1251 : 191 : tree tmp = make_temp_ssa_name (ret_type, NULL, label);
1252 : 191 : gphi *phi;
1253 : :
1254 : 191 : phi = create_phi_node (tmp, bb);
1255 : 191 : add_phi_arg (phi, init, single_pred_edge (bb),
1256 : : UNKNOWN_LOCATION);
1257 : 191 : return PHI_RESULT (phi);
1258 : : }
1259 : :
1260 : : /* Optimizes tail calls in the function, turning the tail recursion
1261 : : into iteration. When ONLY_MUSTCALL is true only optimize mustcall
1262 : : marked calls. */
1263 : :
1264 : : static unsigned int
1265 : 3269987 : tree_optimize_tail_calls_1 (bool opt_tailcalls, bool only_mustcall)
1266 : : {
1267 : 3269987 : edge e;
1268 : 3269987 : bool phis_constructed = false;
1269 : 3269987 : struct tailcall *tailcalls = NULL, *act, *next;
1270 : 3269987 : bool changed = false;
1271 : 3269987 : basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1272 : 3269987 : tree param;
1273 : 3269987 : edge_iterator ei;
1274 : :
1275 : 6474994 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
1276 : : {
1277 : : /* Only traverse the normal exits, i.e. those that end with return
1278 : : statement. */
1279 : 9614174 : if (safe_is_a <greturn *> (*gsi_last_bb (e->src)))
1280 : 3204160 : find_tail_calls (e->src, &tailcalls, only_mustcall, opt_tailcalls);
1281 : : }
1282 : :
1283 : 3269987 : if (live_vars)
1284 : : {
1285 : 195032 : destroy_live_vars (live_vars_vec);
1286 : 390064 : delete live_vars;
1287 : 195032 : live_vars = NULL;
1288 : : }
1289 : :
1290 : : /* Construct the phi nodes and accumulators if necessary. */
1291 : 3269987 : a_acc = m_acc = NULL_TREE;
1292 : 4060578 : for (act = tailcalls; act; act = act->next)
1293 : : {
1294 : 790591 : if (!act->tail_recursion)
1295 : 788568 : continue;
1296 : :
1297 : 2023 : if (!phis_constructed)
1298 : : {
1299 : : /* Ensure that there is only one predecessor of the block
1300 : : or if there are existing degenerate PHI nodes. */
1301 : 992 : if (!single_pred_p (first)
1302 : 992 : || !gimple_seq_empty_p (phi_nodes (first)))
1303 : 0 : first =
1304 : 0 : split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1305 : :
1306 : : /* Copy the args if needed. */
1307 : 992 : unsigned idx;
1308 : 992 : for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
1309 : 3024 : param;
1310 : 2032 : param = DECL_CHAIN (param), idx++)
1311 : 2032 : if (bitmap_bit_p (tailr_arg_needs_copy, idx))
1312 : : {
1313 : 1036 : tree name = ssa_default_def (cfun, param);
1314 : 1036 : tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
1315 : 1036 : gphi *phi;
1316 : :
1317 : 1036 : set_ssa_default_def (cfun, param, new_name);
1318 : 1036 : phi = create_phi_node (name, first);
1319 : 1036 : add_phi_arg (phi, new_name, single_pred_edge (first),
1320 : 1036 : EXPR_LOCATION (param));
1321 : : }
1322 : : phis_constructed = true;
1323 : : }
1324 : 2023 : tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
1325 : 2023 : if (POINTER_TYPE_P (ret_type))
1326 : 173 : ret_type = sizetype;
1327 : :
1328 : 2023 : if (act->add && !a_acc)
1329 : 86 : a_acc = create_tailcall_accumulator ("add_acc", first,
1330 : : build_zero_cst (ret_type));
1331 : :
1332 : 2023 : if (act->mult && !m_acc)
1333 : 105 : m_acc = create_tailcall_accumulator ("mult_acc", first,
1334 : : build_one_cst (ret_type));
1335 : : }
1336 : :
1337 : 3269987 : if (a_acc || m_acc)
1338 : : {
1339 : : /* When the tail call elimination using accumulators is performed,
1340 : : statements adding the accumulated value are inserted at all exits.
1341 : : This turns all other tail calls to non-tail ones. */
1342 : 173 : opt_tailcalls = false;
1343 : : }
1344 : :
1345 : 3269987 : class loop *new_loop = NULL;
1346 : 4060578 : for (; tailcalls; tailcalls = next)
1347 : : {
1348 : 790591 : next = tailcalls->next;
1349 : 790591 : changed |= optimize_tail_call (tailcalls, opt_tailcalls, new_loop);
1350 : 790591 : free (tailcalls);
1351 : : }
1352 : 3269987 : if (new_loop)
1353 : 992 : add_loop (new_loop, loops_for_fn (cfun)->tree_root);
1354 : :
1355 : 3269987 : if (a_acc || m_acc)
1356 : : {
1357 : : /* Modify the remaining return statements. */
1358 : 318 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
1359 : : {
1360 : 435 : if (safe_is_a <greturn *> (*gsi_last_bb (e->src)))
1361 : 145 : adjust_return_value (e->src, m_acc, a_acc);
1362 : : }
1363 : : }
1364 : :
1365 : 3269987 : if (changed)
1366 : 992 : free_dominance_info (CDI_DOMINATORS);
1367 : :
1368 : : /* Add phi nodes for the virtual operands defined in the function to the
1369 : : header of the loop created by tail recursion elimination. Do so
1370 : : by triggering the SSA renamer. */
1371 : 3269987 : if (phis_constructed)
1372 : 992 : mark_virtual_operands_for_renaming (cfun);
1373 : :
1374 : 3269987 : if (tailr_arg_needs_copy)
1375 : 992 : BITMAP_FREE (tailr_arg_needs_copy);
1376 : :
1377 : 3269987 : if (changed)
1378 : 992 : return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
1379 : : return 0;
1380 : : }
1381 : :
1382 : : static bool
1383 : 4256418 : gate_tail_calls (void)
1384 : : {
1385 : 4256418 : return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
1386 : : }
1387 : :
1388 : : static unsigned int
1389 : 688332 : execute_tail_calls (void)
1390 : : {
1391 : 0 : return tree_optimize_tail_calls_1 (true, false);
1392 : : }
1393 : :
1394 : : namespace {
1395 : :
1396 : : const pass_data pass_data_tail_recursion =
1397 : : {
1398 : : GIMPLE_PASS, /* type */
1399 : : "tailr", /* name */
1400 : : OPTGROUP_NONE, /* optinfo_flags */
1401 : : TV_NONE, /* tv_id */
1402 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
1403 : : 0, /* properties_provided */
1404 : : 0, /* properties_destroyed */
1405 : : 0, /* todo_flags_start */
1406 : : 0, /* todo_flags_finish */
1407 : : };
1408 : :
1409 : : class pass_tail_recursion : public gimple_opt_pass
1410 : : {
1411 : : public:
1412 : 565732 : pass_tail_recursion (gcc::context *ctxt)
1413 : 1131464 : : gimple_opt_pass (pass_data_tail_recursion, ctxt)
1414 : : {}
1415 : :
1416 : : /* opt_pass methods: */
1417 : 282866 : opt_pass * clone () final override
1418 : : {
1419 : 282866 : return new pass_tail_recursion (m_ctxt);
1420 : : }
1421 : 3255444 : bool gate (function *) final override { return gate_tail_calls (); }
1422 : 2581592 : unsigned int execute (function *) final override
1423 : : {
1424 : 2581592 : return tree_optimize_tail_calls_1 (false, false);
1425 : : }
1426 : :
1427 : : }; // class pass_tail_recursion
1428 : :
1429 : : } // anon namespace
1430 : :
1431 : : gimple_opt_pass *
1432 : 282866 : make_pass_tail_recursion (gcc::context *ctxt)
1433 : : {
1434 : 282866 : return new pass_tail_recursion (ctxt);
1435 : : }
1436 : :
1437 : : namespace {
1438 : :
1439 : : const pass_data pass_data_tail_calls =
1440 : : {
1441 : : GIMPLE_PASS, /* type */
1442 : : "tailc", /* name */
1443 : : OPTGROUP_NONE, /* optinfo_flags */
1444 : : TV_NONE, /* tv_id */
1445 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
1446 : : 0, /* properties_provided */
1447 : : 0, /* properties_destroyed */
1448 : : 0, /* todo_flags_start */
1449 : : 0, /* todo_flags_finish */
1450 : : };
1451 : :
1452 : : class pass_tail_calls : public gimple_opt_pass
1453 : : {
1454 : : public:
1455 : 282866 : pass_tail_calls (gcc::context *ctxt)
1456 : 565732 : : gimple_opt_pass (pass_data_tail_calls, ctxt)
1457 : : {}
1458 : :
1459 : : /* opt_pass methods: */
1460 : 1000974 : bool gate (function *) final override { return gate_tail_calls (); }
1461 : 688332 : unsigned int execute (function *) final override
1462 : : {
1463 : 688332 : return execute_tail_calls ();
1464 : : }
1465 : :
1466 : : }; // class pass_tail_calls
1467 : :
1468 : : } // anon namespace
1469 : :
1470 : : gimple_opt_pass *
1471 : 282866 : make_pass_tail_calls (gcc::context *ctxt)
1472 : : {
1473 : 282866 : return new pass_tail_calls (ctxt);
1474 : : }
1475 : :
1476 : : namespace {
1477 : :
1478 : : const pass_data pass_data_musttail =
1479 : : {
1480 : : GIMPLE_PASS, /* type */
1481 : : "musttail", /* name */
1482 : : OPTGROUP_NONE, /* optinfo_flags */
1483 : : TV_NONE, /* tv_id */
1484 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
1485 : : 0, /* properties_provided */
1486 : : 0, /* properties_destroyed */
1487 : : 0, /* todo_flags_start */
1488 : : 0, /* todo_flags_finish */
1489 : : };
1490 : :
1491 : : class pass_musttail : public gimple_opt_pass
1492 : : {
1493 : : public:
1494 : 282866 : pass_musttail (gcc::context *ctxt)
1495 : 565732 : : gimple_opt_pass (pass_data_musttail, ctxt)
1496 : : {}
1497 : :
1498 : : /* opt_pass methods: */
1499 : : /* This pass is only used when the other tail call pass
1500 : : doesn't run to make [[musttail]] still work. But only
1501 : : run it when there is actually a musttail in the function. */
1502 : 1432365 : bool gate (function *f) final override
1503 : : {
1504 : 1432365 : return !flag_optimize_sibling_calls && f->has_musttail;
1505 : : }
1506 : 63 : unsigned int execute (function *) final override
1507 : : {
1508 : 63 : return tree_optimize_tail_calls_1 (true, true);
1509 : : }
1510 : :
1511 : : }; // class pass_musttail
1512 : :
1513 : : } // anon namespace
1514 : :
1515 : : gimple_opt_pass *
1516 : 282866 : make_pass_musttail (gcc::context *ctxt)
1517 : : {
1518 : 282866 : return new pass_musttail (ctxt);
1519 : : }
|
