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 : : #include "attribs.h"
55 : : #include "asan.h"
56 : :
57 : : /* The file implements the tail recursion elimination. It is also used to
58 : : analyze the tail calls in general, passing the results to the rtl level
59 : : where they are used for sibcall optimization.
60 : :
61 : : In addition to the standard tail recursion elimination, we handle the most
62 : : trivial cases of making the call tail recursive by creating accumulators.
63 : : For example the following function
64 : :
65 : : int sum (int n)
66 : : {
67 : : if (n > 0)
68 : : return n + sum (n - 1);
69 : : else
70 : : return 0;
71 : : }
72 : :
73 : : is transformed into
74 : :
75 : : int sum (int n)
76 : : {
77 : : int acc = 0;
78 : :
79 : : while (n > 0)
80 : : acc += n--;
81 : :
82 : : return acc;
83 : : }
84 : :
85 : : To do this, we maintain two accumulators (a_acc and m_acc) that indicate
86 : : when we reach the return x statement, we should return a_acc + x * m_acc
87 : : instead. They are initially initialized to 0 and 1, respectively,
88 : : so the semantics of the function is obviously preserved. If we are
89 : : guaranteed that the value of the accumulator never change, we
90 : : omit the accumulator.
91 : :
92 : : There are three cases how the function may exit. The first one is
93 : : handled in adjust_return_value, the other two in adjust_accumulator_values
94 : : (the second case is actually a special case of the third one and we
95 : : present it separately just for clarity):
96 : :
97 : : 1) Just return x, where x is not in any of the remaining special shapes.
98 : : We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
99 : :
100 : : 2) return f (...), where f is the current function, is rewritten in a
101 : : classical tail-recursion elimination way, into assignment of arguments
102 : : and jump to the start of the function. Values of the accumulators
103 : : are unchanged.
104 : :
105 : : 3) return a + m * f(...), where a and m do not depend on call to f.
106 : : To preserve the semantics described before we want this to be rewritten
107 : : in such a way that we finally return
108 : :
109 : : a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
110 : :
111 : : I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
112 : : eliminate the tail call to f. Special cases when the value is just
113 : : added or just multiplied are obtained by setting a = 0 or m = 1.
114 : :
115 : : TODO -- it is possible to do similar tricks for other operations. */
116 : :
117 : : /* A structure that describes the tailcall. */
118 : :
119 : : struct tailcall
120 : : {
121 : : /* The iterator pointing to the call statement. */
122 : : gimple_stmt_iterator call_gsi;
123 : :
124 : : /* True if it is a call to the current function. */
125 : : bool tail_recursion;
126 : :
127 : : /* True if there is __tsan_func_exit call after the call. */
128 : : bool has_tsan_func_exit;
129 : :
130 : : /* The return value of the caller is mult * f + add, where f is the return
131 : : value of the call. */
132 : : tree mult, add;
133 : :
134 : : /* Next tailcall in the chain. */
135 : : struct tailcall *next;
136 : : };
137 : :
138 : : /* The variables holding the value of multiplicative and additive
139 : : accumulator. */
140 : : static tree m_acc, a_acc;
141 : :
142 : : /* Bitmap with a bit for each function parameter which is set to true if we
143 : : have to copy the parameter for conversion of tail-recursive calls. */
144 : :
145 : : static bitmap tailr_arg_needs_copy;
146 : :
147 : : static void maybe_error_musttail (gcall *call, const char *err, bool);
148 : :
149 : : /* Returns false when the function is not suitable for tail call optimization
150 : : from some reason (e.g. if it takes variable number of arguments). CALL
151 : : is call to report for. */
152 : :
153 : : static bool
154 : 1532396 : suitable_for_tail_opt_p (gcall *call, bool diag_musttail)
155 : : {
156 : 1532396 : if (cfun->stdarg)
157 : : {
158 : 18384 : maybe_error_musttail (call, _("caller uses stdargs"), diag_musttail);
159 : 18384 : return false;
160 : : }
161 : :
162 : : return true;
163 : : }
164 : :
165 : : /* Returns false when the function is not suitable for tail call optimization
166 : : for some reason (e.g. if it takes variable number of arguments).
167 : : This test must pass in addition to suitable_for_tail_opt_p in order to make
168 : : tail call discovery happen. CALL is call to report error for. */
169 : :
170 : : static bool
171 : 1514012 : suitable_for_tail_call_opt_p (gcall *call, bool diag_musttail)
172 : : {
173 : : /* alloca (until we have stack slot life analysis) inhibits
174 : : sibling call optimizations, but not tail recursion. */
175 : 1514012 : if (cfun->calls_alloca)
176 : : {
177 : 15040 : maybe_error_musttail (call, _("caller uses alloca"), diag_musttail);
178 : 15040 : return false;
179 : : }
180 : :
181 : : /* If we are using sjlj exceptions, we may need to add a call to
182 : : _Unwind_SjLj_Unregister at exit of the function. Which means
183 : : that we cannot do any sibcall transformations. */
184 : 1498972 : if (targetm_common.except_unwind_info (&global_options) == UI_SJLJ
185 : 1498972 : && current_function_has_exception_handlers ())
186 : : {
187 : 0 : maybe_error_musttail (call, _("caller uses sjlj exceptions"),
188 : : diag_musttail);
189 : 0 : return false;
190 : : }
191 : :
192 : : /* Any function that calls setjmp might have longjmp called from
193 : : any called function. ??? We really should represent this
194 : : properly in the CFG so that this needn't be special cased. */
195 : 1498972 : if (cfun->calls_setjmp)
196 : : {
197 : 144 : maybe_error_musttail (call, _("caller uses setjmp"), diag_musttail);
198 : 144 : return false;
199 : : }
200 : :
201 : : /* Various targets don't handle tail calls correctly in functions
202 : : that call __builtin_eh_return. */
203 : 1498828 : if (cfun->calls_eh_return)
204 : : {
205 : 8 : maybe_error_musttail (call, _("caller uses __builtin_eh_return"),
206 : : diag_musttail);
207 : 8 : return false;
208 : : }
209 : :
210 : 1498820 : if (diag_musttail
211 : 363732 : && gimple_call_must_tail_p (call)
212 : 1499514 : && warn_musttail_local_addr)
213 : 1663 : for (unsigned int i = 0; i < gimple_call_num_args (call); i++)
214 : : {
215 : 969 : tree arg = gimple_call_arg (call, i);
216 : 969 : if (!POINTER_TYPE_P (TREE_TYPE (arg)))
217 : 496 : continue;
218 : 473 : if (TREE_CODE (arg) == ADDR_EXPR)
219 : : {
220 : 179 : arg = get_base_address (TREE_OPERAND (arg, 0));
221 : 179 : if (auto_var_in_fn_p (arg, current_function_decl))
222 : : {
223 : 179 : if (TREE_CODE (arg) == LABEL_DECL)
224 : 16 : warning_at (gimple_location (call), OPT_Wmusttail_local_addr,
225 : : "address of label passed to %<musttail%> "
226 : : "call argument");
227 : 163 : else if (TREE_CODE (arg) == PARM_DECL)
228 : 25 : warning_at (gimple_location (call), OPT_Wmusttail_local_addr,
229 : : "address of parameter %qD passed to "
230 : : "%<musttail%> call argument", arg);
231 : 138 : else if (!DECL_ARTIFICIAL (arg) && DECL_NAME (arg))
232 : 129 : warning_at (gimple_location (call), OPT_Wmusttail_local_addr,
233 : : "address of automatic variable %qD passed to "
234 : : "%<musttail%> call argument", arg);
235 : : else
236 : 9 : warning_at (gimple_location (call), OPT_Wmusttail_local_addr,
237 : : "address of local variable passed to "
238 : : "%<musttail%> call argument");
239 : 179 : suppress_warning (call, OPT_Wmaybe_musttail_local_addr);
240 : : }
241 : : }
242 : : }
243 : :
244 : : return true;
245 : : }
246 : :
247 : : /* Return single successor edge ignoring EDGE_EH edges. */
248 : :
249 : : static edge
250 : 524981 : single_non_eh_succ_edge (basic_block bb)
251 : : {
252 : 524981 : edge e, ret = NULL;
253 : 524981 : edge_iterator ei;
254 : 1050122 : FOR_EACH_EDGE (e, ei, bb->succs)
255 : 525141 : if ((e->flags & EDGE_EH) == 0)
256 : : {
257 : 524981 : gcc_assert (ret == NULL);
258 : : ret = e;
259 : : }
260 : 524981 : gcc_assert (ret);
261 : 524981 : return ret;
262 : : }
263 : :
264 : : /* Checks whether the expression EXPR in stmt AT is independent of the
265 : : statement pointed to by GSI (in a sense that we already know EXPR's value
266 : : at GSI). We use the fact that we are only called from the chain of
267 : : basic blocks that have only single successor. Returns the expression
268 : : containing the value of EXPR at GSI. */
269 : :
270 : : static tree
271 : 23130 : independent_of_stmt_p (tree expr, gimple *at, gimple_stmt_iterator gsi,
272 : : bitmap to_move)
273 : : {
274 : 23130 : basic_block bb, call_bb, at_bb;
275 : 23130 : edge e;
276 : 23130 : edge_iterator ei;
277 : :
278 : 23130 : if (is_gimple_min_invariant (expr))
279 : : return expr;
280 : :
281 : 6103 : if (TREE_CODE (expr) != SSA_NAME)
282 : : return NULL_TREE;
283 : :
284 : 6103 : if (bitmap_bit_p (to_move, SSA_NAME_VERSION (expr)))
285 : : return expr;
286 : :
287 : : /* Mark the blocks in the chain leading to the end. */
288 : 6082 : at_bb = gimple_bb (at);
289 : 6082 : call_bb = gimple_bb (gsi_stmt (gsi));
290 : 6882 : for (bb = call_bb; bb != at_bb; bb = single_non_eh_succ_edge (bb)->dest)
291 : 800 : bb->aux = &bb->aux;
292 : 6082 : bb->aux = &bb->aux;
293 : :
294 : 6189 : while (1)
295 : : {
296 : 6189 : at = SSA_NAME_DEF_STMT (expr);
297 : 6189 : bb = gimple_bb (at);
298 : :
299 : : /* The default definition or defined before the chain. */
300 : 6189 : if (!bb || !bb->aux)
301 : : break;
302 : :
303 : 3074 : if (bb == call_bb)
304 : : {
305 : 18510 : for (; !gsi_end_p (gsi); gsi_next (&gsi))
306 : 15731 : if (gsi_stmt (gsi) == at)
307 : : break;
308 : :
309 : 2945 : if (!gsi_end_p (gsi))
310 : 166 : expr = NULL_TREE;
311 : : break;
312 : : }
313 : :
314 : 129 : if (gimple_code (at) != GIMPLE_PHI)
315 : : {
316 : : expr = NULL_TREE;
317 : : break;
318 : : }
319 : :
320 : 142 : FOR_EACH_EDGE (e, ei, bb->preds)
321 : 142 : if (e->src->aux)
322 : : break;
323 : 129 : gcc_assert (e);
324 : :
325 : 129 : expr = PHI_ARG_DEF_FROM_EDGE (at, e);
326 : 129 : if (TREE_CODE (expr) != SSA_NAME)
327 : : {
328 : : /* The value is a constant. */
329 : : break;
330 : : }
331 : : }
332 : :
333 : : /* Unmark the blocks. */
334 : 6882 : for (bb = call_bb; bb != at_bb; bb = single_non_eh_succ_edge (bb)->dest)
335 : 800 : bb->aux = NULL;
336 : 6082 : bb->aux = NULL;
337 : :
338 : 6082 : return expr;
339 : : }
340 : :
341 : : enum par { FAIL, OK, TRY_MOVE };
342 : :
343 : : /* Simulates the effect of an assignment STMT on the return value of the tail
344 : : recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
345 : : additive factor for the real return value. */
346 : :
347 : : static par
348 : 112657 : process_assignment (gassign *stmt,
349 : : gimple_stmt_iterator call, tree *m,
350 : : tree *a, tree *ass_var, bitmap to_move)
351 : : {
352 : 112657 : tree op0, op1 = NULL_TREE, non_ass_var = NULL_TREE;
353 : 112657 : tree dest = gimple_assign_lhs (stmt);
354 : 112657 : enum tree_code code = gimple_assign_rhs_code (stmt);
355 : 112657 : enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
356 : 112657 : tree src_var = gimple_assign_rhs1 (stmt);
357 : :
358 : : /* See if this is a simple copy operation of an SSA name to the function
359 : : result. In that case we may have a simple tail call. Ignore type
360 : : conversions that can never produce extra code between the function
361 : : call and the function return. */
362 : 54770 : if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt))
363 : 133140 : && src_var == *ass_var)
364 : : {
365 : : /* Reject a tailcall if the type conversion might need
366 : : additional code. */
367 : 22821 : if (gimple_assign_cast_p (stmt))
368 : : {
369 : 18374 : if (TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var)))
370 : : return FAIL;
371 : :
372 : : /* Even if the type modes are the same, if the precision of the
373 : : type is smaller than mode's precision,
374 : : reduce_to_bit_field_precision would generate additional code. */
375 : 16916 : if (INTEGRAL_TYPE_P (TREE_TYPE (dest))
376 : 16409 : && !type_has_mode_precision_p (TREE_TYPE (dest)))
377 : : return FAIL;
378 : : }
379 : :
380 : 12872 : *ass_var = dest;
381 : 12872 : return OK;
382 : : }
383 : :
384 : 89836 : switch (rhs_class)
385 : : {
386 : 31555 : case GIMPLE_BINARY_RHS:
387 : 31555 : op1 = gimple_assign_rhs2 (stmt);
388 : :
389 : : /* Fall through. */
390 : :
391 : 36025 : case GIMPLE_UNARY_RHS:
392 : 36025 : op0 = gimple_assign_rhs1 (stmt);
393 : 36025 : break;
394 : :
395 : : default:
396 : : return FAIL;
397 : : }
398 : :
399 : : /* Accumulator optimizations will reverse the order of operations.
400 : : We can only do that for floating-point types if we're assuming
401 : : that addition and multiplication are associative. */
402 : 36025 : if (!flag_associative_math)
403 : 35677 : if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
404 : : return FAIL;
405 : :
406 : : /* We at least cannot build -1 for all fixed point types. */
407 : 32022 : if (FIXED_POINT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
408 : : return FAIL;
409 : :
410 : 32022 : if (rhs_class == GIMPLE_UNARY_RHS
411 : 4146 : && op0 == *ass_var)
412 : : ;
413 : 29967 : else if (op0 == *ass_var
414 : 29967 : && (non_ass_var = independent_of_stmt_p (op1, stmt, call,
415 : : to_move)))
416 : : ;
417 : 13405 : else if (*ass_var
418 : 6729 : && op1 == *ass_var
419 : 19835 : && (non_ass_var = independent_of_stmt_p (op0, stmt, call,
420 : : to_move)))
421 : : ;
422 : : else
423 : 7057 : return TRY_MOVE;
424 : :
425 : 24965 : switch (code)
426 : : {
427 : 6510 : case PLUS_EXPR:
428 : 6510 : *a = non_ass_var;
429 : 6510 : *ass_var = dest;
430 : 6510 : return OK;
431 : :
432 : 324 : case POINTER_PLUS_EXPR:
433 : 324 : if (op0 != *ass_var)
434 : : return FAIL;
435 : 83 : *a = non_ass_var;
436 : 83 : *ass_var = dest;
437 : 83 : return OK;
438 : :
439 : 376 : case MULT_EXPR:
440 : 376 : *m = non_ass_var;
441 : 376 : *ass_var = dest;
442 : 376 : return OK;
443 : :
444 : 110 : case NEGATE_EXPR:
445 : 110 : *m = build_minus_one_cst (TREE_TYPE (op0));
446 : 110 : *ass_var = dest;
447 : 110 : return OK;
448 : :
449 : 1753 : case MINUS_EXPR:
450 : 1753 : if (*ass_var == op0)
451 : 114 : *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
452 : : else
453 : : {
454 : 1639 : *m = build_minus_one_cst (TREE_TYPE (non_ass_var));
455 : 1639 : *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
456 : : }
457 : :
458 : 1753 : *ass_var = dest;
459 : 1753 : return OK;
460 : :
461 : : default:
462 : : return FAIL;
463 : : }
464 : : }
465 : :
466 : : /* Propagate VAR through phis on edge E. */
467 : :
468 : : static tree
469 : 521270 : propagate_through_phis (tree var, edge e)
470 : : {
471 : 521270 : basic_block dest = e->dest;
472 : 521270 : gphi_iterator gsi;
473 : :
474 : 989355 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
475 : : {
476 : 532517 : gphi *phi = gsi.phi ();
477 : 532517 : if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
478 : 64432 : return PHI_RESULT (phi);
479 : : }
480 : : return var;
481 : : }
482 : :
483 : : /* Report an error for failing to tail convert must call CALL
484 : : with error message ERR. Also clear the flag to prevent further
485 : : errors. */
486 : :
487 : : static void
488 : 740543 : maybe_error_musttail (gcall *call, const char *err, bool diag_musttail)
489 : : {
490 : 740543 : if (gimple_call_must_tail_p (call) && diag_musttail)
491 : : {
492 : 39 : error_at (gimple_location (call), "cannot tail-call: %s", err);
493 : : /* Avoid another error. ??? If there are multiple reasons why tail
494 : : calls fail it might be useful to report them all to avoid
495 : : whack-a-mole for the user. But currently there is too much
496 : : redundancy in the reporting, so keep it simple. */
497 : 39 : gimple_call_set_must_tail (call, false); /* Avoid another error. */
498 : 39 : gimple_call_set_tail (call, false);
499 : : }
500 : 740543 : if (dump_file && (dump_flags & TDF_DETAILS))
501 : : {
502 : 13 : fprintf (dump_file, "Cannot tail-call: %s: ", err);
503 : 13 : print_gimple_stmt (dump_file, call, 0, TDF_SLIM);
504 : : }
505 : 740543 : }
506 : :
507 : : /* Return true if there is no real work performed in the exception
508 : : path starting at BB and it will in the end result in external exception.
509 : : Search at most CNT basic blocks (so that we don't need to do trivial
510 : : loop discovery). */
511 : : static bool
512 : 206 : empty_eh_cleanup (basic_block bb, int *eh_has_tsan_func_exit, int cnt)
513 : : {
514 : 299 : if (EDGE_COUNT (bb->succs) > 1)
515 : : return false;
516 : :
517 : 466 : for (gimple_stmt_iterator gsi = gsi_after_labels (bb); !gsi_end_p (gsi);
518 : 167 : gsi_next (&gsi))
519 : : {
520 : 406 : gimple *g = gsi_stmt (gsi);
521 : 406 : if (is_gimple_debug (g) || gimple_clobber_p (g))
522 : 55 : continue;
523 : 355 : if (eh_has_tsan_func_exit
524 : 276 : && !*eh_has_tsan_func_exit
525 : 272 : && sanitize_flags_p (SANITIZE_THREAD)
526 : 355 : && gimple_call_builtin_p (g, BUILT_IN_TSAN_FUNC_EXIT))
527 : : {
528 : 4 : *eh_has_tsan_func_exit = 1;
529 : 4 : continue;
530 : : }
531 : 455 : if (eh_has_tsan_func_exit
532 : 272 : && sanitize_flags_p (SANITIZE_ADDRESS)
533 : 515 : && asan_mark_p (g, ASAN_MARK_POISON))
534 : 108 : continue;
535 : 239 : if (is_gimple_resx (g))
536 : : {
537 : 239 : if (stmt_can_throw_external (cfun, g))
538 : 206 : return true;
539 : 239 : if (single_succ_p (bb)
540 : 33 : && (single_succ_edge (bb)->flags & EDGE_EH)
541 : 66 : && cnt > 1)
542 : 33 : return empty_eh_cleanup (single_succ (bb), eh_has_tsan_func_exit,
543 : 33 : cnt - 1);
544 : : }
545 : : return false;
546 : : }
547 : 60 : if (!single_succ_p (bb))
548 : : return false;
549 : 60 : if (cnt == 1)
550 : : return false;
551 : 60 : return empty_eh_cleanup (single_succ (bb), eh_has_tsan_func_exit, cnt - 1);
552 : : }
553 : :
554 : : /* Argument for compute_live_vars/live_vars_at_stmt and what compute_live_vars
555 : : returns. Computed lazily, but just once for the function. */
556 : : static live_vars_map *live_vars;
557 : : static vec<bitmap_head> live_vars_vec;
558 : :
559 : : /* Finds tailcalls falling into basic block BB when coming from edge ESUCC (or
560 : : NULL). The list of found tailcalls is added to the start of RET.
561 : : When ONLY_MUSTTAIL is set only handle musttail.
562 : : Update OPT_TAILCALLS as output parameter. If DIAG_MUSTTAIL, diagnose
563 : : failures for musttail calls. RETRY_TSAN_FUNC_EXIT is initially 0 and
564 : : in that case the last call is attempted to be tail called, including
565 : : __tsan_func_exit with -fsanitize=thread. It is set to -1 if we
566 : : detect __tsan_func_exit call and in that case tree_optimize_tail_calls_1
567 : : will retry with it set to 1 (regardless of whether turning the
568 : : __tsan_func_exit was successfully detected as tail call or not) and that
569 : : will allow turning musttail calls before that call into tail calls as well
570 : : by adding __tsan_func_exit call before the call.
571 : : IGNORED_EDGES and MUST_SEE_BBS are used in recursive calls when handling
572 : : GIMPLE_CONDs for cleanups. */
573 : :
574 : : static void
575 : 7207208 : find_tail_calls (basic_block bb, edge esucc, struct tailcall **ret,
576 : : bool only_musttail, bool &opt_tailcalls, bool diag_musttail,
577 : : int &retry_tsan_func_exit, hash_set<edge> *ignored_edges,
578 : : hash_set<basic_block> *must_see_bbs)
579 : : {
580 : 7207208 : tree ass_var = NULL_TREE, ret_var, func, param;
581 : 7207208 : gimple *stmt;
582 : 7207208 : gcall *call = NULL;
583 : 7207208 : gimple_stmt_iterator gsi, agsi;
584 : 7207208 : bool tail_recursion;
585 : 7207208 : struct tailcall *nw;
586 : 7207208 : edge e;
587 : 7207208 : tree m, a;
588 : 7207208 : basic_block abb;
589 : 7207208 : size_t idx;
590 : 7207208 : tree var;
591 : 7207208 : bool only_tailr = false;
592 : 7207208 : bool has_tsan_func_exit = false;
593 : 7207208 : int eh_has_tsan_func_exit = -1;
594 : 7207208 : bool delete_ignored_edges = false;
595 : :
596 : 7207208 : if (!single_succ_p (bb)
597 : 7207208 : && (EDGE_COUNT (bb->succs) || !cfun->has_musttail || !diag_musttail))
598 : : {
599 : 1802390 : if (EDGE_COUNT (bb->succs) == 2
600 : 1763213 : && esucc
601 : 1763213 : && cfun->has_musttail
602 : 451 : && diag_musttail
603 : 314 : && (EDGE_SUCC (bb, 0)->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
604 : 159 : && (EDGE_SUCC (bb, 1)->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
605 : 159 : && (stmt = last_nondebug_stmt (bb))
606 : 1802549 : && gimple_code (stmt) == GIMPLE_COND)
607 : : ;
608 : : /* If there is an abnormal edge assume it's the only extra one.
609 : : Tolerate that case so that we can give better error messages
610 : : for musttail later. */
611 : 1802231 : else if (!has_abnormal_or_eh_outgoing_edge_p (bb))
612 : : {
613 : 1731146 : if (dump_file)
614 : 108 : fprintf (dump_file, "Basic block %d has extra exit edges\n",
615 : : bb->index);
616 : 6371584 : return;
617 : : }
618 : 71244 : if (!cfun->has_musttail)
619 : : return;
620 : : }
621 : :
622 : 5405201 : bool bad_stmt = false;
623 : 5405201 : gimple *last_stmt = nullptr;
624 : 23466848 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
625 : : {
626 : 15356470 : stmt = gsi_stmt (gsi);
627 : :
628 : : /* Ignore labels, returns, nops, clobbers and debug stmts. */
629 : 15356470 : if (gimple_code (stmt) == GIMPLE_LABEL
630 : : || gimple_code (stmt) == GIMPLE_RETURN
631 : : || gimple_code (stmt) == GIMPLE_NOP
632 : : || gimple_code (stmt) == GIMPLE_PREDICT
633 : 11579643 : || gimple_clobber_p (stmt)
634 : 10565178 : || is_gimple_debug (stmt))
635 : 11678603 : continue;
636 : :
637 : 3677867 : if (cfun->has_musttail
638 : 2395 : && sanitize_flags_p (SANITIZE_THREAD)
639 : 44 : && gimple_call_builtin_p (stmt, BUILT_IN_TSAN_FUNC_EXIT)
640 : 3677883 : && diag_musttail)
641 : : {
642 : 16 : if (retry_tsan_func_exit == 0)
643 : 8 : retry_tsan_func_exit = -1;
644 : 8 : else if (retry_tsan_func_exit == 1)
645 : 8 : continue;
646 : : }
647 : :
648 : 3678111 : if (cfun->has_musttail
649 : 2387 : && sanitize_flags_p (SANITIZE_ADDRESS)
650 : 553 : && asan_mark_p (stmt, ASAN_MARK_POISON)
651 : 3678255 : && diag_musttail)
652 : 252 : continue;
653 : :
654 : : /* Especially at -O0 with -fsanitize=address we can end up with
655 : : code like
656 : : _26 = foo (x_24(D)); [must tail call]
657 : : finally_tmp.3_27 = 0;
658 : : goto <bb 5>; [INV]
659 : :
660 : : ...
661 : :
662 : : <bb 5> :
663 : : # _6 = PHI <_26(3), _23(D)(4)>
664 : : # finally_tmp.3_8 = PHI <finally_tmp.3_27(3), finally_tmp.3_22(4)>
665 : : .ASAN_MARK (POISON, &c, 4);
666 : : if (finally_tmp.3_8 == 1)
667 : : goto <bb 7>; [INV]
668 : : else
669 : : goto <bb 6>; [INV]
670 : : When walking backwards, ESUCC is the edge we are coming from,
671 : : depending on its EDGE_TRUE_FLAG, == vs. != for the comparison
672 : : and value compared against try to find out through which edge
673 : : we need to go and which edge should be ignored. The code handles
674 : : both INTEGER_CST PHI arguments and SSA_NAMEs set to constants
675 : : (for -O0 where those aren't propagated). */
676 : 3677607 : if (cfun->has_musttail
677 : : && diag_musttail
678 : 2135 : && esucc
679 : 1287 : && gimple_code (stmt) == GIMPLE_COND
680 : 159 : && (gimple_cond_code (stmt) == EQ_EXPR
681 : 8 : || gimple_cond_code (stmt) == NE_EXPR)
682 : 155 : && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
683 : 155 : && TREE_CODE (gimple_cond_rhs (stmt)) == INTEGER_CST
684 : 155 : && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
685 : 3677762 : && (integer_zerop (gimple_cond_rhs (stmt))
686 : 151 : || integer_onep (gimple_cond_rhs (stmt))))
687 : : {
688 : 36 : tree lhs = gimple_cond_lhs (stmt);
689 : 36 : bool rhsv = integer_onep (gimple_cond_rhs (stmt));
690 : 72 : if (((esucc->flags & EDGE_TRUE_VALUE) != 0)
691 : 36 : ^ (gimple_cond_code (stmt) == EQ_EXPR))
692 : 36 : rhsv = !rhsv;
693 : 36 : if (!ignored_edges)
694 : : {
695 : 22 : ignored_edges = new hash_set<edge>;
696 : 22 : must_see_bbs = new hash_set<basic_block>;
697 : 22 : delete_ignored_edges = true;
698 : : }
699 : 36 : if (is_gimple_assign (SSA_NAME_DEF_STMT (lhs))
700 : 36 : && (gimple_assign_rhs_code (SSA_NAME_DEF_STMT (lhs))
701 : : == INTEGER_CST))
702 : : {
703 : 0 : tree rhs = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (lhs));
704 : 0 : if (rhsv ? integer_onep (rhs) : integer_zerop (rhs))
705 : 0 : continue;
706 : : }
707 : 36 : else if (gimple_code (SSA_NAME_DEF_STMT (lhs)) == GIMPLE_PHI)
708 : : {
709 : 12 : gimple *phi = SSA_NAME_DEF_STMT (lhs);
710 : 12 : basic_block pbb = gimple_bb (phi);
711 : 12 : must_see_bbs->add (pbb);
712 : 12 : edge_iterator ei;
713 : 36 : FOR_EACH_EDGE (e, ei, pbb->preds)
714 : : {
715 : 24 : tree rhs = gimple_phi_arg_def_from_edge (phi, e);
716 : 24 : if (TREE_CODE (rhs) == SSA_NAME
717 : 24 : && is_gimple_assign (SSA_NAME_DEF_STMT (rhs))
718 : 48 : && (gimple_assign_rhs_code (SSA_NAME_DEF_STMT (rhs))
719 : : == INTEGER_CST))
720 : 24 : rhs = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (rhs));
721 : 24 : if (!(rhsv ? integer_onep (rhs) : integer_zerop (rhs)))
722 : 12 : ignored_edges->add (e);
723 : : }
724 : : }
725 : : }
726 : :
727 : 3677607 : if (!last_stmt)
728 : 3047092 : last_stmt = stmt;
729 : : /* Check for a call. */
730 : 3677607 : if (is_gimple_call (stmt))
731 : : {
732 : 1532427 : call = as_a <gcall *> (stmt);
733 : : /* Handle only musttail calls when not optimizing. */
734 : 1532427 : if (only_musttail && !gimple_call_must_tail_p (call))
735 : : {
736 : 3872805 : maybe_delete_ignored_edges:
737 : 3872805 : if (delete_ignored_edges)
738 : : {
739 : 44 : delete ignored_edges;
740 : 44 : delete must_see_bbs;
741 : : }
742 : 3872805 : return;
743 : : }
744 : 1532405 : if (bad_stmt)
745 : : {
746 : 9 : maybe_error_musttail (call, _("memory reference or volatile "
747 : : "after call"), diag_musttail);
748 : 9 : goto maybe_delete_ignored_edges;
749 : : }
750 : 1532396 : ass_var = gimple_call_lhs (call);
751 : 1532396 : break;
752 : : }
753 : :
754 : : /* Allow simple copies between local variables, even if they're
755 : : aggregates. */
756 : 2145180 : if (is_gimple_assign (stmt)
757 : 2124263 : && auto_var_in_fn_p (gimple_assign_lhs (stmt), cfun->decl)
758 : 2202304 : && auto_var_in_fn_p (gimple_assign_rhs1 (stmt), cfun->decl))
759 : 28219 : continue;
760 : :
761 : : /* If the statement references memory or volatile operands, fail. */
762 : 2116961 : if (gimple_references_memory_p (stmt)
763 : 13605527 : || gimple_has_volatile_ops (stmt))
764 : : {
765 : 1167704 : if (dump_file)
766 : : {
767 : 26 : fprintf (dump_file, "Cannot handle ");
768 : 26 : print_gimple_stmt (dump_file, stmt, 0);
769 : : }
770 : 1167704 : bad_stmt = true;
771 : 1167704 : if (!cfun->has_musttail)
772 : : break;
773 : : }
774 : : }
775 : :
776 : 5405170 : if (bad_stmt)
777 : 1167655 : goto maybe_delete_ignored_edges;
778 : :
779 : 4237515 : if (gsi_end_p (gsi))
780 : : {
781 : 2705119 : if (must_see_bbs)
782 : 36 : must_see_bbs->remove (bb);
783 : :
784 : 2705119 : edge_iterator ei;
785 : : /* Recurse to the predecessors. */
786 : 6494591 : FOR_EACH_EDGE (e, ei, bb->preds)
787 : : {
788 : 3789472 : if (ignored_edges && ignored_edges->contains (e))
789 : 12 : continue;
790 : 3789460 : find_tail_calls (e->src, e, ret, only_musttail, opt_tailcalls,
791 : : diag_musttail, retry_tsan_func_exit, ignored_edges,
792 : : must_see_bbs);
793 : : }
794 : :
795 : 2705119 : goto maybe_delete_ignored_edges;
796 : : }
797 : :
798 : 1532396 : if (must_see_bbs && !must_see_bbs->is_empty ())
799 : 0 : goto maybe_delete_ignored_edges;
800 : :
801 : 1532396 : if (delete_ignored_edges)
802 : : {
803 : 0 : delete ignored_edges;
804 : 0 : delete must_see_bbs;
805 : : }
806 : :
807 : 1532396 : if (!suitable_for_tail_opt_p (call, diag_musttail))
808 : : return;
809 : :
810 : 1514012 : if (!suitable_for_tail_call_opt_p (call, diag_musttail))
811 : 15192 : opt_tailcalls = false;
812 : :
813 : : /* ??? It is OK if the argument of a function is taken in some cases,
814 : : but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
815 : 1514012 : if (!diag_musttail || !gimple_call_must_tail_p (call))
816 : 1513318 : for (param = DECL_ARGUMENTS (current_function_decl);
817 : 4469703 : param; param = DECL_CHAIN (param))
818 : 2956385 : if (TREE_ADDRESSABLE (param))
819 : : {
820 : 28649 : maybe_error_musttail (call, _("address of caller arguments taken"),
821 : : diag_musttail);
822 : : /* If current function has musttail calls, we can't disable tail
823 : : calls altogether for the whole caller, because those might be
824 : : actually fine. So just punt if this exact call is not
825 : : a tail recursion. */
826 : 28649 : if (cfun->has_musttail)
827 : : only_tailr = true;
828 : : else
829 : 28577 : opt_tailcalls = false;
830 : : }
831 : :
832 : : /* If the LHS of our call is not just a simple register or local
833 : : variable, we can't transform this into a tail or sibling call.
834 : : This situation happens, in (e.g.) "*p = foo()" where foo returns a
835 : : struct. In this case we won't have a temporary here, but we need
836 : : to carry out the side effect anyway, so tailcall is impossible.
837 : :
838 : : ??? In some situations (when the struct is returned in memory via
839 : : invisible argument) we could deal with this, e.g. by passing 'p'
840 : : itself as that argument to foo, but it's too early to do this here,
841 : : and expand_call() will not handle it anyway. If it ever can, then
842 : : we need to revisit this here, to allow that situation. */
843 : 1514012 : if (ass_var
844 : 429780 : && !is_gimple_reg (ass_var)
845 : 1572613 : && !auto_var_in_fn_p (ass_var, cfun->decl))
846 : : {
847 : 7771 : maybe_error_musttail (call, _("return value in memory"), diag_musttail);
848 : 7771 : return;
849 : : }
850 : :
851 : 1506241 : if (cfun->calls_setjmp)
852 : : {
853 : 164 : maybe_error_musttail (call, _("caller uses setjmp"), diag_musttail);
854 : 164 : return;
855 : : }
856 : :
857 : : /* If the call might throw an exception that wouldn't propagate out of
858 : : cfun, we can't transform to a tail or sibling call (82081). */
859 : 1506077 : if ((stmt_could_throw_p (cfun, stmt)
860 : 1506077 : && !stmt_can_throw_external (cfun, stmt)) || EDGE_COUNT (bb->succs) > 1)
861 : : {
862 : 18967 : if (stmt != last_stmt)
863 : : {
864 : 74 : maybe_error_musttail (call, _("code between call and return"),
865 : : diag_musttail);
866 : 18835 : return;
867 : : }
868 : :
869 : 18893 : edge e;
870 : 18893 : edge_iterator ei;
871 : 37584 : FOR_EACH_EDGE (e, ei, bb->succs)
872 : 18905 : if (e->flags & EDGE_EH)
873 : : break;
874 : :
875 : 18893 : if (!e)
876 : : {
877 : 18679 : maybe_error_musttail (call, _("call may throw exception that does not "
878 : : "propagate"), diag_musttail);
879 : 18679 : return;
880 : : }
881 : :
882 : 214 : if (diag_musttail && gimple_call_must_tail_p (call))
883 : 137 : eh_has_tsan_func_exit = 0;
884 : 214 : if (!gimple_call_must_tail_p (call)
885 : 206 : || !empty_eh_cleanup (e->dest,
886 : 206 : eh_has_tsan_func_exit
887 : : ? NULL : &eh_has_tsan_func_exit, 20)
888 : 420 : || EDGE_COUNT (bb->succs) > 2)
889 : : {
890 : 8 : maybe_error_musttail (call, _("call may throw exception caught "
891 : : "locally or perform cleanups"),
892 : : diag_musttail);
893 : 8 : return;
894 : : }
895 : : }
896 : :
897 : : /* If the function returns a value, then at present, the tail call
898 : : must return the same type of value. There is conceptually a copy
899 : : between the object returned by the tail call candidate and the
900 : : object returned by CFUN itself.
901 : :
902 : : This means that if we have:
903 : :
904 : : lhs = f (&<retval>); // f reads from <retval>
905 : : // (lhs is usually also <retval>)
906 : :
907 : : there is a copy between the temporary object returned by f and lhs,
908 : : meaning that any use of <retval> in f occurs before the assignment
909 : : to lhs begins. Thus the <retval> that is live on entry to the call
910 : : to f is really an independent local variable V that happens to be
911 : : stored in the RESULT_DECL rather than a local VAR_DECL.
912 : :
913 : : Turning this into a tail call would remove the copy and make the
914 : : lifetimes of the return value and V overlap. The same applies to
915 : : tail recursion, since if f can read from <retval>, we have to assume
916 : : that CFUN might already have written to <retval> before the call.
917 : :
918 : : The problem doesn't apply when <retval> is passed by value, but that
919 : : isn't a case we handle anyway. */
920 : 1487316 : tree result_decl = DECL_RESULT (cfun->decl);
921 : 1487316 : if (result_decl
922 : 1487316 : && may_be_aliased (result_decl)
923 : 1492035 : && ref_maybe_used_by_stmt_p (call, result_decl, false))
924 : : {
925 : 1538 : maybe_error_musttail (call, _("return value used after call"),
926 : : diag_musttail);
927 : 1538 : return;
928 : : }
929 : :
930 : : /* We found the call, check whether it is suitable. */
931 : 1485778 : tail_recursion = false;
932 : 1485778 : func = gimple_call_fndecl (call);
933 : 1485778 : if (func
934 : 1410604 : && !fndecl_built_in_p (func)
935 : 1079709 : && recursive_call_p (current_function_decl, func)
936 : 1488722 : && !only_musttail)
937 : : {
938 : 2921 : tree arg;
939 : :
940 : 2921 : for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
941 : 10025 : param && idx < gimple_call_num_args (call);
942 : 7104 : param = DECL_CHAIN (param), idx ++)
943 : : {
944 : 7217 : arg = gimple_call_arg (call, idx);
945 : 7217 : if (param != arg)
946 : : {
947 : : /* Make sure there are no problems with copying. The parameter
948 : : have a copyable type and the two arguments must have reasonably
949 : : equivalent types. The latter requirement could be relaxed if
950 : : we emitted a suitable type conversion statement. */
951 : 7005 : if (TREE_ADDRESSABLE (TREE_TYPE (param))
952 : 14010 : || !useless_type_conversion_p (TREE_TYPE (param),
953 : 7005 : TREE_TYPE (arg)))
954 : : break;
955 : :
956 : 13489 : if (is_gimple_reg_type (TREE_TYPE (param))
957 : 6969 : ? !is_gimple_reg (param)
958 : 449 : : (!is_gimple_variable (param)
959 : 449 : || TREE_THIS_VOLATILE (param)
960 : 898 : || may_be_aliased (param)))
961 : : break;
962 : : }
963 : : }
964 : 2921 : if (idx == gimple_call_num_args (call) && !param)
965 : 1485778 : tail_recursion = true;
966 : : }
967 : :
968 : 1485778 : if (only_tailr && !tail_recursion)
969 : : return;
970 : :
971 : : /* Compute live vars if not computed yet. */
972 : 1485706 : if (live_vars == NULL)
973 : : {
974 : 1443425 : unsigned int cnt = 0;
975 : 13212436 : FOR_EACH_LOCAL_DECL (cfun, idx, var)
976 : 10521847 : if (VAR_P (var)
977 : 10521847 : && auto_var_in_fn_p (var, cfun->decl)
978 : 20921271 : && may_be_aliased (var))
979 : : {
980 : 868296 : if (live_vars == NULL)
981 : 207175 : live_vars = new live_vars_map;
982 : 868296 : live_vars->put (DECL_UID (var), cnt++);
983 : : }
984 : 1443425 : if (live_vars)
985 : 207175 : live_vars_vec = compute_live_vars (cfun, live_vars);
986 : : }
987 : :
988 : : /* Determine a bitmap of variables which are still in scope after the
989 : : call. */
990 : 1485706 : bitmap local_live_vars = NULL;
991 : 1485706 : if (live_vars)
992 : 249456 : local_live_vars = live_vars_at_stmt (live_vars_vec, live_vars, call);
993 : :
994 : : /* Make sure the tail invocation of this function does not indirectly
995 : : refer to local variables. (Passing variables directly by value
996 : : is OK.) */
997 : 13500220 : FOR_EACH_LOCAL_DECL (cfun, idx, var)
998 : : {
999 : 10912374 : if (TREE_CODE (var) != PARM_DECL
1000 : 10912374 : && auto_var_in_fn_p (var, cfun->decl)
1001 : 10834892 : && may_be_aliased (var)
1002 : 11627871 : && (ref_maybe_used_by_stmt_p (call, var, false)
1003 : 325150 : || call_may_clobber_ref_p (call, var, false)))
1004 : : {
1005 : 446902 : if (!VAR_P (var))
1006 : : {
1007 : 0 : if (diag_musttail && gimple_call_must_tail_p (call))
1008 : : {
1009 : 0 : auto opt = OPT_Wmaybe_musttail_local_addr;
1010 : 0 : if (!warning_suppressed_p (call,
1011 : : opt))
1012 : : {
1013 : 0 : warning_at (gimple_location (call), opt,
1014 : : "address of local variable can escape to "
1015 : : "%<musttail%> call");
1016 : 0 : suppress_warning (call, opt);
1017 : : }
1018 : 0 : continue;
1019 : 0 : }
1020 : 0 : if (local_live_vars)
1021 : 0 : BITMAP_FREE (local_live_vars);
1022 : 0 : maybe_error_musttail (call, _("call invocation refers to "
1023 : : "locals"), diag_musttail);
1024 : 0 : return;
1025 : : }
1026 : : else
1027 : : {
1028 : 446902 : unsigned int *v = live_vars->get (DECL_UID (var));
1029 : 446902 : if (bitmap_bit_p (local_live_vars, *v))
1030 : : {
1031 : 187733 : if (diag_musttail && gimple_call_must_tail_p (call))
1032 : : {
1033 : 428 : auto opt = OPT_Wmaybe_musttail_local_addr;
1034 : 428 : if (!warning_suppressed_p (call, opt))
1035 : : {
1036 : 151 : if (!DECL_ARTIFICIAL (var) && DECL_NAME (var))
1037 : 150 : warning_at (gimple_location (call), opt,
1038 : : "address of automatic variable %qD "
1039 : : "can escape to %<musttail%> call",
1040 : : var);
1041 : : else
1042 : 1 : warning_at (gimple_location (call), opt,
1043 : : "address of local variable can escape "
1044 : : "to %<musttail%> call");
1045 : 151 : suppress_warning (call, opt);
1046 : : }
1047 : 428 : continue;
1048 : 428 : }
1049 : 187305 : BITMAP_FREE (local_live_vars);
1050 : 187305 : maybe_error_musttail (call, _("call invocation refers to "
1051 : : "locals"), diag_musttail);
1052 : 187305 : return;
1053 : : }
1054 : : }
1055 : : }
1056 : : }
1057 : 1298401 : if (diag_musttail
1058 : 307469 : && gimple_call_must_tail_p (call)
1059 : 1299086 : && !warning_suppressed_p (call, OPT_Wmaybe_musttail_local_addr))
1060 : 387 : for (tree param = DECL_ARGUMENTS (current_function_decl);
1061 : 761 : param; param = DECL_CHAIN (param))
1062 : 399 : if (may_be_aliased (param)
1063 : 399 : && (ref_maybe_used_by_stmt_p (call, param, false)
1064 : 0 : || call_may_clobber_ref_p (call, param, false)))
1065 : : {
1066 : 25 : auto opt = OPT_Wmaybe_musttail_local_addr;
1067 : 25 : warning_at (gimple_location (call), opt,
1068 : : "address of parameter %qD can escape to "
1069 : : "%<musttail%> call", param);
1070 : 25 : suppress_warning (call, opt);
1071 : 25 : break;
1072 : : }
1073 : :
1074 : 1298401 : if (local_live_vars)
1075 : 62151 : BITMAP_FREE (local_live_vars);
1076 : :
1077 : : /* Now check the statements after the call. None of them has virtual
1078 : : operands, so they may only depend on the call through its return
1079 : : value. The return value should also be dependent on each of them,
1080 : : since we are running after dce. */
1081 : 1298401 : m = NULL_TREE;
1082 : 1298401 : a = NULL_TREE;
1083 : 2134025 : auto_bitmap to_move_defs;
1084 : 2134025 : auto_vec<gimple *> to_move_stmts;
1085 : 1298401 : bool is_noreturn = gimple_call_noreturn_p (call);
1086 : 2134025 : auto_vec<edge> edges;
1087 : :
1088 : 1298401 : abb = bb;
1089 : 1298401 : agsi = gsi;
1090 : 3066788 : while (!is_noreturn)
1091 : : {
1092 : 3066122 : tree tmp_a = NULL_TREE;
1093 : 3066122 : tree tmp_m = NULL_TREE;
1094 : 3066122 : gsi_next (&agsi);
1095 : :
1096 : : new_bb:
1097 : 3587392 : while (gsi_end_p (agsi))
1098 : : {
1099 : 521258 : edge e = single_non_eh_succ_edge (abb);
1100 : 521258 : ass_var = propagate_through_phis (ass_var, e);
1101 : 521258 : if (!ass_var || ignored_edges)
1102 : 433165 : edges.safe_push (e);
1103 : 521258 : abb = e->dest;
1104 : 1042516 : agsi = gsi_start_bb (abb);
1105 : : }
1106 : :
1107 : 3066134 : stmt = gsi_stmt (agsi);
1108 : 3066134 : if (gimple_code (stmt) == GIMPLE_RETURN)
1109 : : break;
1110 : :
1111 : 3605967 : if (gimple_code (stmt) == GIMPLE_LABEL
1112 : 1834119 : || gimple_code (stmt) == GIMPLE_NOP
1113 : 1834119 : || gimple_code (stmt) == GIMPLE_PREDICT
1114 : 1814816 : || gimple_clobber_p (stmt)
1115 : 3506791 : || is_gimple_debug (stmt))
1116 : 1746683 : continue;
1117 : :
1118 : 113207 : if (cfun->has_musttail
1119 : 528 : && sanitize_flags_p (SANITIZE_THREAD)
1120 : 10 : && retry_tsan_func_exit == 1
1121 : 10 : && gimple_call_builtin_p (stmt, BUILT_IN_TSAN_FUNC_EXIT)
1122 : 8 : && !has_tsan_func_exit
1123 : 113207 : && gimple_call_must_tail_p (call))
1124 : : {
1125 : 8 : has_tsan_func_exit = true;
1126 : 8 : continue;
1127 : : }
1128 : :
1129 : 113443 : if (cfun->has_musttail
1130 : 520 : && sanitize_flags_p (SANITIZE_ADDRESS)
1131 : 279 : && asan_mark_p (stmt, ASAN_MARK_POISON)
1132 : 113443 : && diag_musttail)
1133 : 252 : continue;
1134 : :
1135 : : /* See earlier comment on GIMPLE_CONDs. Here we need to propagate
1136 : : through on the forward walk, so based on the edges vector we've
1137 : : walked through determine which edge to follow. */
1138 : 112939 : if (ignored_edges)
1139 : : {
1140 : 26 : if (is_gimple_assign (stmt)
1141 : 26 : && gimple_assign_rhs_code (stmt) == INTEGER_CST)
1142 : : {
1143 : 12 : use_operand_p use_p;
1144 : 12 : gimple *use_stmt;
1145 : 12 : if ((integer_zerop (gimple_assign_rhs1 (stmt))
1146 : 0 : || integer_onep (gimple_assign_rhs1 (stmt)))
1147 : 12 : && single_imm_use (gimple_assign_lhs (stmt), &use_p,
1148 : : &use_stmt))
1149 : : {
1150 : 12 : if (gimple_code (use_stmt) == GIMPLE_COND)
1151 : 12 : continue;
1152 : 24 : if (gimple_code (use_stmt) == GIMPLE_PHI
1153 : 12 : && single_imm_use (gimple_phi_result (use_stmt),
1154 : : &use_p, &use_stmt)
1155 : 24 : && gimple_code (use_stmt) == GIMPLE_COND)
1156 : 12 : continue;
1157 : : }
1158 : : }
1159 : 14 : if (gimple_code (stmt) == GIMPLE_COND
1160 : 12 : && (gimple_cond_code (stmt) == EQ_EXPR
1161 : 0 : || gimple_cond_code (stmt) == NE_EXPR)
1162 : 12 : && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
1163 : 12 : && TREE_CODE (gimple_cond_rhs (stmt)) == INTEGER_CST
1164 : 12 : && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
1165 : 26 : && (integer_zerop (gimple_cond_rhs (stmt))
1166 : 12 : || integer_onep (gimple_cond_rhs (stmt))))
1167 : : {
1168 : 12 : edge e = NULL, et, ef;
1169 : 12 : tree lhs = gimple_cond_lhs (stmt);
1170 : 12 : bool rhsv = integer_onep (gimple_cond_rhs (stmt));
1171 : 12 : if (gimple_cond_code (stmt) == NE_EXPR)
1172 : 0 : rhsv = !rhsv;
1173 : 12 : extract_true_false_edges_from_block (gimple_bb (stmt), &et, &ef);
1174 : 12 : if (is_gimple_assign (SSA_NAME_DEF_STMT (lhs))
1175 : 12 : && (gimple_assign_rhs_code (SSA_NAME_DEF_STMT (lhs))
1176 : : == INTEGER_CST))
1177 : : {
1178 : 0 : tree rhs = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (lhs));
1179 : 0 : if (rhsv ? integer_onep (rhs) : integer_zerop (rhs))
1180 : 0 : e = et;
1181 : 0 : else if (rhsv ? integer_zerop (rhs) : integer_onep (rhs))
1182 : 0 : e = ef;
1183 : : }
1184 : 12 : else if (gimple_code (SSA_NAME_DEF_STMT (lhs)) == GIMPLE_PHI)
1185 : : {
1186 : 12 : gimple *phi = SSA_NAME_DEF_STMT (lhs);
1187 : 12 : basic_block pbb = gimple_bb (phi);
1188 : 52 : for (edge e2 : edges)
1189 : 28 : if (e2->dest == pbb)
1190 : : {
1191 : 12 : tree rhs = gimple_phi_arg_def_from_edge (phi, e2);
1192 : 12 : if (TREE_CODE (rhs) == SSA_NAME)
1193 : 12 : if (gimple *g = SSA_NAME_DEF_STMT (rhs))
1194 : 12 : if (is_gimple_assign (g)
1195 : 12 : && gimple_assign_rhs_code (g) == INTEGER_CST)
1196 : 12 : rhs = gimple_assign_rhs1 (g);
1197 : 12 : if (rhsv ? integer_onep (rhs) : integer_zerop (rhs))
1198 : 0 : e = et;
1199 : 12 : else if (rhsv ? integer_zerop (rhs)
1200 : 0 : : integer_onep (rhs))
1201 : 12 : e = ef;
1202 : : break;
1203 : : }
1204 : : }
1205 : 12 : if (e)
1206 : : {
1207 : 12 : ass_var = propagate_through_phis (ass_var, e);
1208 : 12 : if (!ass_var || ignored_edges)
1209 : 12 : edges.safe_push (e);
1210 : 12 : abb = e->dest;
1211 : 12 : agsi = gsi_start_bb (abb);
1212 : 12 : goto new_bb;
1213 : : }
1214 : : }
1215 : : }
1216 : :
1217 : 112915 : if (gimple_code (stmt) != GIMPLE_ASSIGN)
1218 : : {
1219 : 258 : maybe_error_musttail (call, _("unhandled code after call"),
1220 : : diag_musttail);
1221 : 91442 : return;
1222 : : }
1223 : :
1224 : : /* This is a gimple assign. */
1225 : 112657 : par ret = process_assignment (as_a <gassign *> (stmt), gsi,
1226 : : &tmp_m, &tmp_a, &ass_var, to_move_defs);
1227 : 112657 : if (ret == FAIL || (ret == TRY_MOVE && !tail_recursion))
1228 : : {
1229 : 90913 : maybe_error_musttail (call, _("return value changed after call"),
1230 : : diag_musttail);
1231 : 90913 : return;
1232 : : }
1233 : 21744 : else if (ret == TRY_MOVE)
1234 : : {
1235 : : /* Do not deal with checking dominance, the real fix is to
1236 : : do path isolation for the transform phase anyway, removing
1237 : : the need to compute the accumulators with new stmts. */
1238 : 40 : if (abb != bb)
1239 : : return;
1240 : 81 : for (unsigned opno = 1; opno < gimple_num_ops (stmt); ++opno)
1241 : : {
1242 : 54 : tree op = gimple_op (stmt, opno);
1243 : 54 : if (independent_of_stmt_p (op, stmt, gsi, to_move_defs) != op)
1244 : : return;
1245 : : }
1246 : 54 : bitmap_set_bit (to_move_defs,
1247 : 27 : SSA_NAME_VERSION (gimple_assign_lhs (stmt)));
1248 : 27 : to_move_stmts.safe_push (stmt);
1249 : 27 : continue;
1250 : 27 : }
1251 : :
1252 : 21704 : if (tmp_a)
1253 : : {
1254 : 8346 : tree type = TREE_TYPE (tmp_a);
1255 : 8346 : if (a)
1256 : 296 : a = fold_build2 (PLUS_EXPR, type, fold_convert (type, a), tmp_a);
1257 : : else
1258 : : a = tmp_a;
1259 : : }
1260 : 21704 : if (tmp_m)
1261 : : {
1262 : 2125 : tree type = TREE_TYPE (tmp_m);
1263 : 2125 : if (m)
1264 : 76 : m = fold_build2 (MULT_EXPR, type, fold_convert (type, m), tmp_m);
1265 : : else
1266 : : m = tmp_m;
1267 : :
1268 : 2125 : if (a)
1269 : 1649 : a = fold_build2 (MULT_EXPR, type, fold_convert (type, a), tmp_m);
1270 : : }
1271 : : }
1272 : :
1273 : : /* See if this is a tail call we can handle. */
1274 : 1207217 : if (is_noreturn)
1275 : : {
1276 : 666 : if (gimple_call_internal_p (call))
1277 : : {
1278 : 654 : maybe_error_musttail (call, _("internal call"), diag_musttail);
1279 : 654 : return;
1280 : : }
1281 : 12 : tree rettype = TREE_TYPE (TREE_TYPE (current_function_decl));
1282 : 12 : tree calltype = TREE_TYPE (gimple_call_fntype (call));
1283 : 12 : if (!VOID_TYPE_P (rettype)
1284 : 12 : && !useless_type_conversion_p (rettype, calltype))
1285 : : {
1286 : 0 : maybe_error_musttail (call, _("call and return value are different"),
1287 : : diag_musttail);
1288 : 0 : return;
1289 : : }
1290 : : ret_var = NULL_TREE;
1291 : : }
1292 : : else
1293 : 1206551 : ret_var = gimple_return_retval (as_a <greturn *> (stmt));
1294 : :
1295 : : /* We may proceed if there either is no return value, or the return value
1296 : : is identical to the call's return or if the return decl is an empty type
1297 : : variable and the call's return was not assigned. */
1298 : 1206551 : if (ret_var
1299 : 1206551 : && (ret_var != ass_var
1300 : 370277 : && !(is_empty_type (TREE_TYPE (ret_var)) && !ass_var)))
1301 : : {
1302 : 369751 : bool ok = false;
1303 : 369751 : value_range val;
1304 : 369751 : if (ass_var == NULL_TREE && !tail_recursion)
1305 : : {
1306 : 369647 : tree other_value = NULL_TREE;
1307 : : /* If we have a function call that we know the return value is the same
1308 : : as the argument, try the argument too. */
1309 : 369647 : int flags = gimple_call_return_flags (call);
1310 : 369647 : if ((flags & ERF_RETURNS_ARG) != 0
1311 : 369647 : && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (call))
1312 : : {
1313 : 4310 : tree arg = gimple_call_arg (call, flags & ERF_RETURN_ARG_MASK);
1314 : 4310 : if (useless_type_conversion_p (TREE_TYPE (ret_var), TREE_TYPE (arg) ))
1315 : : other_value = arg;
1316 : : }
1317 : : /* If IPA-VRP proves called function always returns a singleton range,
1318 : : the return value is replaced by the only value in that range.
1319 : : For tail call purposes, pretend such replacement didn't happen. */
1320 : 365337 : else if (tree type = gimple_range_type (call))
1321 : 81801 : if (tree callee = gimple_call_fndecl (call))
1322 : : {
1323 : 81238 : tree valr;
1324 : 81238 : if ((INTEGRAL_TYPE_P (type)
1325 : : || SCALAR_FLOAT_TYPE_P (type)
1326 : 81238 : || POINTER_TYPE_P (type))
1327 : 81238 : && useless_type_conversion_p (TREE_TYPE (TREE_TYPE (callee)),
1328 : : type)
1329 : 81230 : && useless_type_conversion_p (TREE_TYPE (ret_var), type)
1330 : 21171 : && ipa_return_value_range (val, callee)
1331 : 90966 : && val.singleton_p (&valr))
1332 : 6441 : other_value = valr;
1333 : : }
1334 : :
1335 : 83722 : if (other_value)
1336 : : {
1337 : 8925 : tree rv = ret_var;
1338 : 8925 : unsigned int i = edges.length ();
1339 : : /* If ret_var is equal to other_value, we can tail optimize. */
1340 : 8925 : if (operand_equal_p (ret_var, other_value, 0))
1341 : : ok = true;
1342 : : else
1343 : : /* Otherwise, if ret_var is a PHI result, try to find out
1344 : : if other_value isn't propagated through PHIs on the path from
1345 : : call's bb to SSA_NAME_DEF_STMT (ret_var)'s bb. */
1346 : 3891 : while (TREE_CODE (rv) == SSA_NAME
1347 : 3891 : && gimple_code (SSA_NAME_DEF_STMT (rv)) == GIMPLE_PHI)
1348 : : {
1349 : 1459 : tree nrv = NULL_TREE;
1350 : : gimple *g = SSA_NAME_DEF_STMT (rv);
1351 : 1459 : for (; i; --i)
1352 : : {
1353 : 1459 : if (edges[i - 1]->dest == gimple_bb (g))
1354 : : {
1355 : 1459 : nrv = gimple_phi_arg_def_from_edge (g,
1356 : 1459 : edges[i - 1]);
1357 : 1459 : --i;
1358 : 1459 : break;
1359 : : }
1360 : : }
1361 : 1459 : if (nrv == NULL_TREE)
1362 : : break;
1363 : 1459 : if (operand_equal_p (nrv, other_value, 0))
1364 : : {
1365 : : ok = true;
1366 : : break;
1367 : : }
1368 : : rv = nrv;
1369 : : }
1370 : : }
1371 : : }
1372 : 2793 : if (!ok)
1373 : : {
1374 : 363258 : maybe_error_musttail (call, _("call and return value are different"),
1375 : : diag_musttail);
1376 : 363258 : return;
1377 : : }
1378 : 369751 : }
1379 : :
1380 : : /* If this is not a tail recursive call, we cannot handle addends or
1381 : : multiplicands. */
1382 : 843305 : if (!tail_recursion && (m || a))
1383 : : {
1384 : 7681 : maybe_error_musttail (call, _("operations after non tail recursive "
1385 : : "call"), diag_musttail);
1386 : 7681 : return;
1387 : : }
1388 : :
1389 : : /* For pointers only allow additions. */
1390 : 2133 : if (m && POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
1391 : : {
1392 : 0 : maybe_error_musttail (call, _("tail recursion with pointers can only "
1393 : : "use additions"), diag_musttail);
1394 : 0 : return;
1395 : : }
1396 : :
1397 : 835624 : if (eh_has_tsan_func_exit != -1
1398 : 137 : && eh_has_tsan_func_exit != has_tsan_func_exit)
1399 : : {
1400 : 0 : if (eh_has_tsan_func_exit)
1401 : 0 : maybe_error_musttail (call, _("call may throw exception caught "
1402 : : "locally or perform cleanups"),
1403 : : diag_musttail);
1404 : : else
1405 : 0 : maybe_error_musttail (call, _("exception cleanups omit "
1406 : : "__tsan_func_exit call"), diag_musttail);
1407 : 0 : return;
1408 : : }
1409 : :
1410 : : /* Move queued defs. */
1411 : 835624 : if (tail_recursion)
1412 : : {
1413 : : unsigned i;
1414 : 2136 : FOR_EACH_VEC_ELT (to_move_stmts, i, stmt)
1415 : : {
1416 : 3 : gimple_stmt_iterator mgsi = gsi_for_stmt (stmt);
1417 : 3 : gsi_move_before (&mgsi, &gsi);
1418 : : }
1419 : 2133 : if (!tailr_arg_needs_copy)
1420 : 1206 : tailr_arg_needs_copy = BITMAP_ALLOC (NULL);
1421 : 2133 : for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
1422 : 7856 : param;
1423 : 5723 : param = DECL_CHAIN (param), idx++)
1424 : : {
1425 : 5723 : tree ddef, arg = gimple_call_arg (call, idx);
1426 : 5723 : if (!is_gimple_reg (param)
1427 : 5723 : || ((ddef = ssa_default_def (cfun, param))
1428 : 5233 : && arg != ddef))
1429 : 2770 : bitmap_set_bit (tailr_arg_needs_copy, idx);
1430 : : }
1431 : : }
1432 : :
1433 : 835624 : nw = XNEW (struct tailcall);
1434 : :
1435 : 835624 : nw->call_gsi = gsi;
1436 : :
1437 : 835624 : nw->tail_recursion = tail_recursion;
1438 : 835624 : nw->has_tsan_func_exit = has_tsan_func_exit;
1439 : :
1440 : 835624 : nw->mult = m;
1441 : 835624 : nw->add = a;
1442 : :
1443 : 835624 : nw->next = *ret;
1444 : 835624 : *ret = nw;
1445 : : }
1446 : :
1447 : : /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
1448 : :
1449 : : static void
1450 : 212 : add_successor_phi_arg (edge e, tree var, tree phi_arg)
1451 : : {
1452 : 212 : gphi_iterator gsi;
1453 : :
1454 : 450 : for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
1455 : 450 : if (PHI_RESULT (gsi.phi ()) == var)
1456 : : break;
1457 : :
1458 : 212 : gcc_assert (!gsi_end_p (gsi));
1459 : 212 : add_phi_arg (gsi.phi (), phi_arg, e, UNKNOWN_LOCATION);
1460 : 212 : }
1461 : :
1462 : : /* Creates a GIMPLE statement which computes the operation specified by
1463 : : CODE, ACC and OP1 to a new variable with name LABEL and inserts the
1464 : : statement in the position specified by GSI. Returns the
1465 : : tree node of the statement's result. */
1466 : :
1467 : : static tree
1468 : 178 : adjust_return_value_with_ops (enum tree_code code, const char *label,
1469 : : tree acc, tree op1, gimple_stmt_iterator gsi)
1470 : : {
1471 : :
1472 : 178 : tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
1473 : 178 : tree result = make_temp_ssa_name (ret_type, NULL, label);
1474 : 178 : gassign *stmt;
1475 : :
1476 : 178 : if (POINTER_TYPE_P (ret_type))
1477 : : {
1478 : 6 : gcc_assert (code == PLUS_EXPR && TREE_TYPE (acc) == sizetype);
1479 : : code = POINTER_PLUS_EXPR;
1480 : : }
1481 : 178 : if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1))
1482 : 178 : && code != POINTER_PLUS_EXPR)
1483 : 167 : stmt = gimple_build_assign (result, code, acc, op1);
1484 : : else
1485 : : {
1486 : 11 : tree tem;
1487 : 11 : if (code == POINTER_PLUS_EXPR)
1488 : 6 : tem = fold_build2 (code, TREE_TYPE (op1), op1, acc);
1489 : : else
1490 : 5 : tem = fold_build2 (code, TREE_TYPE (op1),
1491 : : fold_convert (TREE_TYPE (op1), acc), op1);
1492 : 11 : tree rhs = fold_convert (ret_type, tem);
1493 : 11 : rhs = force_gimple_operand_gsi (&gsi, rhs,
1494 : : false, NULL, true, GSI_SAME_STMT);
1495 : 11 : stmt = gimple_build_assign (result, rhs);
1496 : : }
1497 : :
1498 : 178 : gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1499 : 178 : return result;
1500 : : }
1501 : :
1502 : : /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
1503 : : the computation specified by CODE and OP1 and insert the statement
1504 : : at the position specified by GSI as a new statement. Returns new SSA name
1505 : : of updated accumulator. */
1506 : :
1507 : : static tree
1508 : 209 : update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
1509 : : gimple_stmt_iterator gsi)
1510 : : {
1511 : 209 : gassign *stmt;
1512 : 209 : tree var = copy_ssa_name (acc);
1513 : 209 : if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
1514 : 195 : stmt = gimple_build_assign (var, code, acc, op1);
1515 : : else
1516 : : {
1517 : 14 : tree rhs = fold_convert (TREE_TYPE (acc),
1518 : : fold_build2 (code,
1519 : : TREE_TYPE (op1),
1520 : : fold_convert (TREE_TYPE (op1), acc),
1521 : : op1));
1522 : 14 : rhs = force_gimple_operand_gsi (&gsi, rhs,
1523 : : false, NULL, false, GSI_CONTINUE_LINKING);
1524 : 14 : stmt = gimple_build_assign (var, rhs);
1525 : : }
1526 : 209 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1527 : 209 : return var;
1528 : : }
1529 : :
1530 : : /* Adjust the accumulator values according to A and M after GSI, and update
1531 : : the phi nodes on edge BACK. */
1532 : :
1533 : : static void
1534 : 2127 : adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
1535 : : {
1536 : 2127 : tree var, a_acc_arg, m_acc_arg;
1537 : :
1538 : 2127 : if (m)
1539 : 115 : m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT);
1540 : 2127 : if (a)
1541 : 94 : a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT);
1542 : :
1543 : 2127 : a_acc_arg = a_acc;
1544 : 2127 : m_acc_arg = m_acc;
1545 : 2127 : if (a)
1546 : : {
1547 : 94 : if (m_acc)
1548 : : {
1549 : 18 : if (integer_onep (a))
1550 : 1 : var = m_acc;
1551 : : else
1552 : 17 : var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
1553 : : a, gsi);
1554 : : }
1555 : : else
1556 : : var = a;
1557 : :
1558 : 94 : a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
1559 : : }
1560 : :
1561 : 2127 : if (m)
1562 : 115 : m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
1563 : :
1564 : 2127 : if (a_acc)
1565 : 97 : add_successor_phi_arg (back, a_acc, a_acc_arg);
1566 : :
1567 : 2127 : if (m_acc)
1568 : 115 : add_successor_phi_arg (back, m_acc, m_acc_arg);
1569 : 2127 : }
1570 : :
1571 : : /* Adjust value of the return at the end of BB according to M and A
1572 : : accumulators. */
1573 : :
1574 : : static void
1575 : 148 : adjust_return_value (basic_block bb, tree m, tree a)
1576 : : {
1577 : 148 : tree retval;
1578 : 296 : greturn *ret_stmt = as_a <greturn *> (gimple_seq_last_stmt (bb_seq (bb)));
1579 : 148 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
1580 : :
1581 : 148 : gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
1582 : :
1583 : 148 : retval = gimple_return_retval (ret_stmt);
1584 : 148 : if (!retval || retval == error_mark_node)
1585 : 0 : return;
1586 : :
1587 : 148 : if (m)
1588 : 86 : retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
1589 : : gsi);
1590 : 148 : if (a)
1591 : 75 : retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
1592 : : gsi);
1593 : 148 : gimple_return_set_retval (ret_stmt, retval);
1594 : 148 : update_stmt (ret_stmt);
1595 : : }
1596 : :
1597 : : /* Subtract COUNT and FREQUENCY from the basic block and it's
1598 : : outgoing edge. */
1599 : : static void
1600 : 6116 : decrease_profile (basic_block bb, profile_count count)
1601 : : {
1602 : 0 : bb->count = bb->count - count;
1603 : 0 : }
1604 : :
1605 : : /* Eliminates tail call described by T. TMP_VARS is a list of
1606 : : temporary variables used to copy the function arguments.
1607 : : Allocates *NEW_LOOP if not already done and initializes it. */
1608 : :
1609 : : static void
1610 : 2127 : eliminate_tail_call (struct tailcall *t, class loop *&new_loop)
1611 : : {
1612 : 2127 : tree param, rslt;
1613 : 2127 : gimple *stmt, *call;
1614 : 2127 : tree arg;
1615 : 2127 : size_t idx;
1616 : 2127 : basic_block bb, first;
1617 : 2127 : edge e;
1618 : 2127 : gphi *phi;
1619 : 2127 : gphi_iterator gpi;
1620 : 2127 : gimple_stmt_iterator gsi;
1621 : 2127 : gimple *orig_stmt;
1622 : :
1623 : 2127 : stmt = orig_stmt = gsi_stmt (t->call_gsi);
1624 : 2127 : bb = gsi_bb (t->call_gsi);
1625 : :
1626 : 2127 : if (dump_file && (dump_flags & TDF_DETAILS))
1627 : : {
1628 : 8 : fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
1629 : : bb->index);
1630 : 8 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1631 : 8 : fprintf (dump_file, "\n");
1632 : : }
1633 : :
1634 : 2127 : gcc_assert (is_gimple_call (stmt));
1635 : :
1636 : 2127 : first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1637 : :
1638 : : /* Remove the code after call_gsi that will become unreachable. The
1639 : : possibly unreachable code in other blocks is removed later in
1640 : : cfg cleanup. */
1641 : 2127 : gsi = t->call_gsi;
1642 : 2127 : gimple_stmt_iterator gsi2 = gsi_last_bb (gimple_bb (gsi_stmt (gsi)));
1643 : 3461 : while (gsi_stmt (gsi2) != gsi_stmt (gsi))
1644 : : {
1645 : 1334 : gimple *t = gsi_stmt (gsi2);
1646 : : /* Do not remove the return statement, so that redirect_edge_and_branch
1647 : : sees how the block ends. */
1648 : 1334 : if (gimple_code (t) != GIMPLE_RETURN)
1649 : : {
1650 : 1081 : gimple_stmt_iterator gsi3 = gsi2;
1651 : 1081 : gsi_prev (&gsi2);
1652 : 1081 : gsi_remove (&gsi3, true);
1653 : 1081 : release_defs (t);
1654 : : }
1655 : : else
1656 : 3714 : gsi_prev (&gsi2);
1657 : : }
1658 : :
1659 : 2127 : if (gimple_call_noreturn_p (as_a <gcall *> (stmt)))
1660 : : {
1661 : 4 : e = make_edge (gsi_bb (t->call_gsi), first, EDGE_FALLTHRU);
1662 : 4 : e->probability = profile_probability::always ();
1663 : : }
1664 : : else
1665 : : {
1666 : : /* Number of executions of function has reduced by the tailcall. */
1667 : 2123 : e = single_non_eh_succ_edge (gsi_bb (t->call_gsi));
1668 : :
1669 : 2123 : profile_count count = e->count ();
1670 : :
1671 : : /* When profile is inconsistent and the recursion edge is more frequent
1672 : : than number of executions of functions, scale it down, so we do not
1673 : : end up with 0 executions of entry block. */
1674 : 2123 : if (count >= ENTRY_BLOCK_PTR_FOR_FN (cfun)->count)
1675 : 38 : count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.apply_scale (7, 8);
1676 : 2123 : decrease_profile (EXIT_BLOCK_PTR_FOR_FN (cfun), count);
1677 : 2123 : decrease_profile (ENTRY_BLOCK_PTR_FOR_FN (cfun), count);
1678 : 2123 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1679 : 1870 : decrease_profile (e->dest, count);
1680 : :
1681 : : /* Replace the call by a jump to the start of function. */
1682 : 2123 : e = redirect_edge_and_branch (e, first);
1683 : : }
1684 : 2127 : gcc_assert (e);
1685 : 2127 : PENDING_STMT (e) = NULL;
1686 : :
1687 : : /* Add the new loop. */
1688 : 2127 : if (!new_loop)
1689 : : {
1690 : 1204 : new_loop = alloc_loop ();
1691 : 1204 : new_loop->header = first;
1692 : 1204 : new_loop->finite_p = true;
1693 : : }
1694 : : else
1695 : 923 : gcc_assert (new_loop->header == first);
1696 : :
1697 : : /* Add phi node entries for arguments. The ordering of the phi nodes should
1698 : : be the same as the ordering of the arguments. */
1699 : 2127 : auto_vec<tree> copies;
1700 : 2127 : for (param = DECL_ARGUMENTS (current_function_decl),
1701 : 2127 : idx = 0, gpi = gsi_start_phis (first);
1702 : 7838 : param;
1703 : 5711 : param = DECL_CHAIN (param), idx++)
1704 : : {
1705 : 5711 : if (!bitmap_bit_p (tailr_arg_needs_copy, idx))
1706 : 2938 : continue;
1707 : :
1708 : 2773 : if (!is_gimple_reg_type (TREE_TYPE (param)))
1709 : : {
1710 : 452 : if (param == gimple_call_arg (stmt, idx))
1711 : 160 : continue;
1712 : : /* First check if param isn't used by any of the following
1713 : : call arguments. If it is, we need to copy first to
1714 : : a temporary and only after doing all the assignments copy it
1715 : : to param. */
1716 : 292 : size_t idx2 = idx + 1;
1717 : 292 : tree param2 = DECL_CHAIN (param);
1718 : 1503 : for (; param2; param2 = DECL_CHAIN (param2), idx2++)
1719 : 1212 : if (!is_gimple_reg_type (TREE_TYPE (param)))
1720 : : {
1721 : 1212 : tree base = get_base_address (gimple_call_arg (stmt, idx2));
1722 : 1212 : if (base == param)
1723 : : break;
1724 : : }
1725 : 292 : tree tmp = param;
1726 : 292 : if (param2)
1727 : : {
1728 : 1 : tmp = create_tmp_var (TREE_TYPE (param));
1729 : 1 : copies.safe_push (param);
1730 : 1 : copies.safe_push (tmp);
1731 : : }
1732 : 292 : gimple *g = gimple_build_assign (tmp, gimple_call_arg (stmt, idx));
1733 : 292 : gsi_insert_before (&t->call_gsi, g, GSI_SAME_STMT);
1734 : 292 : continue;
1735 : 292 : }
1736 : :
1737 : 2321 : arg = gimple_call_arg (stmt, idx);
1738 : 2321 : phi = gpi.phi ();
1739 : 2321 : gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
1740 : :
1741 : 2321 : add_phi_arg (phi, arg, e, gimple_location (stmt));
1742 : 2321 : gsi_next (&gpi);
1743 : : }
1744 : 2128 : for (unsigned i = 0; i < copies.length (); i += 2)
1745 : : {
1746 : 1 : gimple *g = gimple_build_assign (copies[i], copies[i + 1]);
1747 : 1 : gsi_insert_before (&t->call_gsi, g, GSI_SAME_STMT);
1748 : : }
1749 : :
1750 : : /* Update the values of accumulators. */
1751 : 2127 : adjust_accumulator_values (t->call_gsi, t->mult, t->add, e);
1752 : :
1753 : 2127 : call = gsi_stmt (t->call_gsi);
1754 : 2127 : rslt = gimple_call_lhs (call);
1755 : 2127 : if (rslt != NULL_TREE && TREE_CODE (rslt) == SSA_NAME)
1756 : : {
1757 : : /* Result of the call will no longer be defined. So adjust the
1758 : : SSA_NAME_DEF_STMT accordingly. */
1759 : 524 : SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
1760 : : }
1761 : :
1762 : 2127 : gsi_remove (&t->call_gsi, true);
1763 : 2127 : release_defs (call);
1764 : 2127 : }
1765 : :
1766 : : /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
1767 : : mark the tailcalls for the sibcall optimization. */
1768 : :
1769 : : static bool
1770 : 835618 : optimize_tail_call (struct tailcall *t, bool opt_tailcalls,
1771 : : class loop *&new_loop)
1772 : : {
1773 : 835618 : if (t->has_tsan_func_exit && (t->tail_recursion || opt_tailcalls))
1774 : : {
1775 : 8 : tree builtin_decl = builtin_decl_implicit (BUILT_IN_TSAN_FUNC_EXIT);
1776 : 8 : gimple *g = gimple_build_call (builtin_decl, 0);
1777 : 8 : gimple_set_location (g, cfun->function_end_locus);
1778 : 8 : gsi_insert_before (&t->call_gsi, g, GSI_SAME_STMT);
1779 : : }
1780 : :
1781 : 835618 : if (t->tail_recursion)
1782 : : {
1783 : 2127 : eliminate_tail_call (t, new_loop);
1784 : 2127 : return true;
1785 : : }
1786 : :
1787 : 833491 : if (opt_tailcalls)
1788 : : {
1789 : 172808 : gcall *stmt = as_a <gcall *> (gsi_stmt (t->call_gsi));
1790 : :
1791 : 172808 : gimple_call_set_tail (stmt, true);
1792 : 172808 : cfun->tail_call_marked = true;
1793 : 172808 : if (dump_file && (dump_flags & TDF_DETAILS))
1794 : : {
1795 : 25 : fprintf (dump_file, "Found tail call ");
1796 : 25 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1797 : 25 : fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
1798 : : }
1799 : 172808 : return t->has_tsan_func_exit;
1800 : : }
1801 : :
1802 : : return false;
1803 : : }
1804 : :
1805 : : /* Creates a tail-call accumulator of the same type as the return type of the
1806 : : current function. LABEL is the name used to creating the temporary
1807 : : variable for the accumulator. The accumulator will be inserted in the
1808 : : phis of a basic block BB with single predecessor with an initial value
1809 : : INIT converted to the current function return type. */
1810 : :
1811 : : static tree
1812 : 194 : create_tailcall_accumulator (const char *label, basic_block bb, tree init)
1813 : : {
1814 : 194 : tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
1815 : 194 : if (POINTER_TYPE_P (ret_type))
1816 : 6 : ret_type = sizetype;
1817 : :
1818 : 194 : tree tmp = make_temp_ssa_name (ret_type, NULL, label);
1819 : 194 : gphi *phi;
1820 : :
1821 : 194 : phi = create_phi_node (tmp, bb);
1822 : 194 : add_phi_arg (phi, init, single_pred_edge (bb),
1823 : : UNKNOWN_LOCATION);
1824 : 194 : return PHI_RESULT (phi);
1825 : : }
1826 : :
1827 : : /* Optimizes tail calls in the function, turning the tail recursion
1828 : : into iteration. When ONLY_MUSTTAIL is true only optimize musttail
1829 : : marked calls. When DIAG_MUSTTAIL, diagnose if musttail calls can't
1830 : : be tail call optimized. */
1831 : :
1832 : : static unsigned int
1833 : 3485718 : tree_optimize_tail_calls_1 (bool opt_tailcalls, bool only_musttail,
1834 : : bool diag_musttail)
1835 : : {
1836 : 3485718 : edge e;
1837 : 3485718 : bool phis_constructed = false;
1838 : 3485718 : struct tailcall *tailcalls = NULL, *act, *next;
1839 : 3485718 : bool changed = false;
1840 : 3485718 : basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1841 : 3485718 : tree param;
1842 : 3485718 : edge_iterator ei;
1843 : :
1844 : 6904296 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
1845 : : {
1846 : : /* Only traverse the normal exits, i.e. those that end with return
1847 : : statement. */
1848 : 10254884 : if (safe_is_a <greturn *> (*gsi_last_bb (e->src)))
1849 : : {
1850 : 3417728 : int retry_tsan_func_exit = 0;
1851 : 3417728 : find_tail_calls (e->src, e, &tailcalls, only_musttail, opt_tailcalls,
1852 : : diag_musttail, retry_tsan_func_exit, NULL, NULL);
1853 : 3417728 : if (retry_tsan_func_exit == -1)
1854 : : {
1855 : 8 : retry_tsan_func_exit = 1;
1856 : 8 : find_tail_calls (e->src, e, &tailcalls, only_musttail,
1857 : : opt_tailcalls, diag_musttail,
1858 : : retry_tsan_func_exit, NULL, NULL);
1859 : : }
1860 : : }
1861 : : }
1862 : 3485718 : if (cfun->has_musttail && diag_musttail)
1863 : : {
1864 : 445 : basic_block bb;
1865 : 445 : int retry_tsan_func_exit = 0;
1866 : 2766 : FOR_EACH_BB_FN (bb, cfun)
1867 : 2321 : if (EDGE_COUNT (bb->succs) == 0
1868 : 2197 : || (single_succ_p (bb)
1869 : 1490 : && (single_succ_edge (bb)->flags & EDGE_EH)))
1870 : 210 : if (gimple *c = last_nondebug_stmt (bb))
1871 : 210 : if (is_gimple_call (c)
1872 : 12 : && gimple_call_must_tail_p (as_a <gcall *> (c))
1873 : 222 : && gimple_call_noreturn_p (as_a <gcall *> (c)))
1874 : 12 : find_tail_calls (bb, NULL, &tailcalls, only_musttail,
1875 : : opt_tailcalls, diag_musttail,
1876 : : retry_tsan_func_exit, NULL, NULL);
1877 : : }
1878 : :
1879 : 3485718 : if (live_vars)
1880 : : {
1881 : 207175 : destroy_live_vars (live_vars_vec);
1882 : 414350 : delete live_vars;
1883 : 207175 : live_vars = NULL;
1884 : : }
1885 : :
1886 : 3485718 : if (cfun->has_musttail)
1887 : : {
1888 : : /* We can't mix non-recursive must tail calls with tail recursive
1889 : : calls which require accumulators, because in that case we have to
1890 : : emit code in between the musttail calls and return, which prevent
1891 : : calling them as tail calls. So, in that case give up on the
1892 : : tail recursion. */
1893 : 977 : for (act = tailcalls; act; act = act->next)
1894 : 658 : if (!act->tail_recursion)
1895 : : {
1896 : 616 : gcall *call = as_a <gcall *> (gsi_stmt (act->call_gsi));
1897 : 616 : if (gimple_call_must_tail_p (call))
1898 : : break;
1899 : : }
1900 : 926 : if (act)
1901 : 1660 : for (struct tailcall **p = &tailcalls; *p; )
1902 : : {
1903 : 1053 : if ((*p)->tail_recursion && ((*p)->add || (*p)->mult))
1904 : : {
1905 : 6 : struct tailcall *a = *p;
1906 : 6 : *p = (*p)->next;
1907 : 6 : gcall *call = as_a <gcall *> (gsi_stmt (a->call_gsi));
1908 : 6 : maybe_error_musttail (call, _("tail recursion with "
1909 : : "accumulation mixed with "
1910 : : "musttail non-recursive call"),
1911 : : diag_musttail);
1912 : 6 : free (a);
1913 : 6 : }
1914 : : else
1915 : 1047 : p = &(*p)->next;
1916 : : }
1917 : : }
1918 : : /* Construct the phi nodes and accumulators if necessary. */
1919 : 3485718 : a_acc = m_acc = NULL_TREE;
1920 : 4321336 : for (act = tailcalls; act; act = act->next)
1921 : : {
1922 : 835618 : if (!act->tail_recursion)
1923 : 833491 : continue;
1924 : :
1925 : 2127 : if (!phis_constructed)
1926 : : {
1927 : : /* Ensure that there is only one predecessor of the block
1928 : : or if there are existing degenerate PHI nodes. */
1929 : 1204 : if (!single_pred_p (first)
1930 : 1204 : || !gimple_seq_empty_p (phi_nodes (first)))
1931 : 0 : first
1932 : 0 : = split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1933 : :
1934 : : /* Copy the args if needed. */
1935 : 1204 : unsigned idx;
1936 : 1204 : for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
1937 : 4244 : param;
1938 : 3040 : param = DECL_CHAIN (param), idx++)
1939 : 3040 : if (bitmap_bit_p (tailr_arg_needs_copy, idx))
1940 : : {
1941 : 1824 : if (!is_gimple_reg_type (TREE_TYPE (param)))
1942 : 452 : continue;
1943 : 1372 : tree name = ssa_default_def (cfun, param);
1944 : 1372 : tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
1945 : 1372 : gphi *phi;
1946 : :
1947 : 1372 : set_ssa_default_def (cfun, param, new_name);
1948 : 1372 : phi = create_phi_node (name, first);
1949 : 1372 : add_phi_arg (phi, new_name, single_pred_edge (first),
1950 : 1372 : EXPR_LOCATION (param));
1951 : : }
1952 : : phis_constructed = true;
1953 : : }
1954 : 2127 : tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
1955 : 2127 : if (POINTER_TYPE_P (ret_type))
1956 : 141 : ret_type = sizetype;
1957 : :
1958 : 2127 : if (act->add && !a_acc)
1959 : 88 : a_acc = create_tailcall_accumulator ("add_acc", first,
1960 : : build_zero_cst (ret_type));
1961 : :
1962 : 2127 : if (act->mult && !m_acc)
1963 : 106 : m_acc = create_tailcall_accumulator ("mult_acc", first,
1964 : : build_one_cst (ret_type));
1965 : : }
1966 : :
1967 : 3485718 : if (a_acc || m_acc)
1968 : : {
1969 : : /* When the tail call elimination using accumulators is performed,
1970 : : statements adding the accumulated value are inserted at all exits.
1971 : : This turns all other tail calls to non-tail ones. */
1972 : 176 : opt_tailcalls = false;
1973 : : }
1974 : :
1975 : 3485718 : class loop *new_loop = NULL;
1976 : 4321336 : for (; tailcalls; tailcalls = next)
1977 : : {
1978 : 835618 : next = tailcalls->next;
1979 : 835618 : changed |= optimize_tail_call (tailcalls, opt_tailcalls, new_loop);
1980 : 835618 : free (tailcalls);
1981 : : }
1982 : 3485718 : if (new_loop)
1983 : 1204 : add_loop (new_loop, loops_for_fn (cfun)->tree_root);
1984 : :
1985 : 3485718 : if (a_acc || m_acc)
1986 : : {
1987 : : /* Modify the remaining return statements. */
1988 : 324 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
1989 : : {
1990 : 444 : if (safe_is_a <greturn *> (*gsi_last_bb (e->src)))
1991 : 148 : adjust_return_value (e->src, m_acc, a_acc);
1992 : : }
1993 : : }
1994 : :
1995 : 3485718 : if (changed)
1996 : 1210 : free_dominance_info (CDI_DOMINATORS);
1997 : :
1998 : : /* Add phi nodes for the virtual operands defined in the function to the
1999 : : header of the loop created by tail recursion elimination. Do so
2000 : : by triggering the SSA renamer. */
2001 : 3485718 : if (phis_constructed)
2002 : 1204 : mark_virtual_operands_for_renaming (cfun);
2003 : :
2004 : 3485718 : if (tailr_arg_needs_copy)
2005 : 1206 : BITMAP_FREE (tailr_arg_needs_copy);
2006 : :
2007 : 3485718 : if (diag_musttail)
2008 : 708327 : cfun->has_musttail = false;
2009 : :
2010 : 3485718 : if (changed)
2011 : 1210 : return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
2012 : : return 0;
2013 : : }
2014 : :
2015 : : static bool
2016 : 4473707 : gate_tail_calls (void)
2017 : : {
2018 : 4473707 : return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
2019 : : }
2020 : :
2021 : : static unsigned int
2022 : 708107 : execute_tail_calls (void)
2023 : : {
2024 : 0 : return tree_optimize_tail_calls_1 (true, false, true);
2025 : : }
2026 : :
2027 : : namespace {
2028 : :
2029 : : const pass_data pass_data_tail_recursion =
2030 : : {
2031 : : GIMPLE_PASS, /* type */
2032 : : "tailr", /* name */
2033 : : OPTGROUP_NONE, /* optinfo_flags */
2034 : : TV_NONE, /* tv_id */
2035 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
2036 : : 0, /* properties_provided */
2037 : : 0, /* properties_destroyed */
2038 : : 0, /* todo_flags_start */
2039 : : 0, /* todo_flags_finish */
2040 : : };
2041 : :
2042 : : class pass_tail_recursion : public gimple_opt_pass
2043 : : {
2044 : : public:
2045 : 573364 : pass_tail_recursion (gcc::context *ctxt)
2046 : 1146728 : : gimple_opt_pass (pass_data_tail_recursion, ctxt)
2047 : : {}
2048 : :
2049 : : /* opt_pass methods: */
2050 : 286682 : opt_pass * clone () final override
2051 : : {
2052 : 286682 : return new pass_tail_recursion (m_ctxt);
2053 : : }
2054 : 3452401 : bool gate (function *) final override { return gate_tail_calls (); }
2055 : 2777391 : unsigned int execute (function *) final override
2056 : : {
2057 : 2777391 : return tree_optimize_tail_calls_1 (false, false, false);
2058 : : }
2059 : :
2060 : : }; // class pass_tail_recursion
2061 : :
2062 : : } // anon namespace
2063 : :
2064 : : gimple_opt_pass *
2065 : 286682 : make_pass_tail_recursion (gcc::context *ctxt)
2066 : : {
2067 : 286682 : return new pass_tail_recursion (ctxt);
2068 : : }
2069 : :
2070 : : namespace {
2071 : :
2072 : : const pass_data pass_data_tail_calls =
2073 : : {
2074 : : GIMPLE_PASS, /* type */
2075 : : "tailc", /* name */
2076 : : OPTGROUP_NONE, /* optinfo_flags */
2077 : : TV_NONE, /* tv_id */
2078 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
2079 : : 0, /* properties_provided */
2080 : : 0, /* properties_destroyed */
2081 : : 0, /* todo_flags_start */
2082 : : 0, /* todo_flags_finish */
2083 : : };
2084 : :
2085 : : class pass_tail_calls : public gimple_opt_pass
2086 : : {
2087 : : public:
2088 : 286682 : pass_tail_calls (gcc::context *ctxt)
2089 : 573364 : : gimple_opt_pass (pass_data_tail_calls, ctxt)
2090 : : {}
2091 : :
2092 : : /* opt_pass methods: */
2093 : 1021306 : bool gate (function *) final override { return gate_tail_calls (); }
2094 : 708107 : unsigned int execute (function *) final override
2095 : : {
2096 : 708107 : return execute_tail_calls ();
2097 : : }
2098 : :
2099 : : }; // class pass_tail_calls
2100 : :
2101 : : } // anon namespace
2102 : :
2103 : : gimple_opt_pass *
2104 : 286682 : make_pass_tail_calls (gcc::context *ctxt)
2105 : : {
2106 : 286682 : return new pass_tail_calls (ctxt);
2107 : : }
2108 : :
2109 : : namespace {
2110 : :
2111 : : const pass_data pass_data_musttail =
2112 : : {
2113 : : GIMPLE_PASS, /* type */
2114 : : "musttail", /* name */
2115 : : OPTGROUP_NONE, /* optinfo_flags */
2116 : : TV_NONE, /* tv_id */
2117 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
2118 : : 0, /* properties_provided */
2119 : : 0, /* properties_destroyed */
2120 : : 0, /* todo_flags_start */
2121 : : 0, /* todo_flags_finish */
2122 : : };
2123 : :
2124 : : class pass_musttail : public gimple_opt_pass
2125 : : {
2126 : : public:
2127 : 286682 : pass_musttail (gcc::context *ctxt)
2128 : 573364 : : gimple_opt_pass (pass_data_musttail, ctxt)
2129 : : {}
2130 : :
2131 : : /* opt_pass methods: */
2132 : : /* This pass is only used when the other tail call pass
2133 : : doesn't run to make [[musttail]] still work. But only
2134 : : run it when there is actually a musttail in the function. */
2135 : 1456109 : bool gate (function *f) final override
2136 : : {
2137 : 1456109 : return f->has_musttail;
2138 : : }
2139 : 220 : unsigned int execute (function *) final override
2140 : : {
2141 : 220 : return tree_optimize_tail_calls_1 (true, true, true);
2142 : : }
2143 : :
2144 : : }; // class pass_musttail
2145 : :
2146 : : } // anon namespace
2147 : :
2148 : : gimple_opt_pass *
2149 : 286682 : make_pass_musttail (gcc::context *ctxt)
2150 : : {
2151 : 286682 : return new pass_musttail (ctxt);
2152 : : }
|