Line data Source code
1 : /* Tail call optimization on trees.
2 : Copyright (C) 2003-2026 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 1608592 : suitable_for_tail_opt_p (gcall *call, bool diag_musttail)
155 : {
156 1608592 : if (cfun->stdarg)
157 : {
158 18524 : maybe_error_musttail (call, _("caller uses stdargs"), diag_musttail);
159 18524 : 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 1590068 : 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 1590068 : if (cfun->calls_alloca)
176 : {
177 16325 : maybe_error_musttail (call, _("caller uses alloca"), diag_musttail);
178 16325 : 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 1573743 : if (targetm_common.except_unwind_info (&global_options) == UI_SJLJ
185 1573743 : && 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 1573743 : 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 1573599 : if (cfun->calls_eh_return)
204 : {
205 12 : maybe_error_musttail (call, _("caller uses __builtin_eh_return"),
206 : diag_musttail);
207 12 : return false;
208 : }
209 :
210 1573587 : if (diag_musttail
211 369503 : && gimple_call_must_tail_p (call)
212 1574334 : && warn_musttail_local_addr)
213 1728 : for (unsigned int i = 0; i < gimple_call_num_args (call); i++)
214 : {
215 981 : tree arg = gimple_call_arg (call, i);
216 981 : if (!POINTER_TYPE_P (TREE_TYPE (arg)))
217 508 : 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 524503 : single_non_eh_succ_edge (basic_block bb)
251 : {
252 524503 : edge e, ret = NULL;
253 524503 : edge_iterator ei;
254 1049173 : FOR_EACH_EDGE (e, ei, bb->succs)
255 524670 : if ((e->flags & EDGE_EH) == 0)
256 : {
257 524503 : gcc_assert (ret == NULL);
258 : ret = e;
259 : }
260 524503 : gcc_assert (ret);
261 524503 : 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 23333 : independent_of_stmt_p (tree expr, gimple *at, gimple_stmt_iterator gsi,
272 : bitmap to_move)
273 : {
274 23333 : basic_block bb, call_bb, at_bb;
275 23333 : edge e;
276 23333 : edge_iterator ei;
277 :
278 23333 : if (is_gimple_min_invariant (expr))
279 : return expr;
280 :
281 6407 : if (TREE_CODE (expr) != SSA_NAME)
282 : return NULL_TREE;
283 :
284 6407 : 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 6386 : at_bb = gimple_bb (at);
289 6386 : call_bb = gimple_bb (gsi_stmt (gsi));
290 7551 : for (bb = call_bb; bb != at_bb; bb = single_non_eh_succ_edge (bb)->dest)
291 1165 : bb->aux = &bb->aux;
292 6386 : bb->aux = &bb->aux;
293 :
294 6493 : while (1)
295 : {
296 6493 : at = SSA_NAME_DEF_STMT (expr);
297 6493 : bb = gimple_bb (at);
298 :
299 : /* The default definition or defined before the chain. */
300 6493 : if (!bb || !bb->aux)
301 : break;
302 :
303 3140 : if (bb == call_bb)
304 : {
305 18809 : for (; !gsi_end_p (gsi); gsi_next (&gsi))
306 15964 : if (gsi_stmt (gsi) == at)
307 : break;
308 :
309 3011 : 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 7551 : for (bb = call_bb; bb != at_bb; bb = single_non_eh_succ_edge (bb)->dest)
335 1165 : bb->aux = NULL;
336 6386 : bb->aux = NULL;
337 :
338 6386 : 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 109997 : process_assignment (gassign *stmt,
349 : gimple_stmt_iterator call, tree *m,
350 : tree *a, tree *ass_var, bitmap to_move)
351 : {
352 109997 : tree op0, op1 = NULL_TREE, non_ass_var = NULL_TREE;
353 109997 : tree dest = gimple_assign_lhs (stmt);
354 109997 : enum tree_code code = gimple_assign_rhs_code (stmt);
355 109997 : enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
356 109997 : 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 53249 : if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt))
363 129763 : && src_var == *ass_var)
364 : {
365 : /* Reject a tailcall if the type conversion might need
366 : additional code. */
367 19485 : if (gimple_assign_cast_p (stmt))
368 : {
369 17734 : 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 16104 : if (INTEGRAL_TYPE_P (TREE_TYPE (dest))
376 15615 : && !type_has_mode_precision_p (TREE_TYPE (dest)))
377 : return FAIL;
378 : }
379 :
380 9753 : *ass_var = dest;
381 9753 : return OK;
382 : }
383 :
384 90512 : switch (rhs_class)
385 : {
386 31664 : case GIMPLE_BINARY_RHS:
387 31664 : op1 = gimple_assign_rhs2 (stmt);
388 :
389 : /* Fall through. */
390 :
391 35139 : case GIMPLE_UNARY_RHS:
392 35139 : op0 = gimple_assign_rhs1 (stmt);
393 35139 : 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 35139 : if (!flag_associative_math)
403 34787 : 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 31135 : if (FIXED_POINT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
408 : return FAIL;
409 :
410 31135 : if (rhs_class == GIMPLE_UNARY_RHS
411 3149 : && op0 == *ass_var)
412 : ;
413 30010 : else if (op0 == *ass_var
414 30010 : && (non_ass_var = independent_of_stmt_p (op1, stmt, call,
415 : to_move)))
416 : ;
417 13037 : else if (*ass_var
418 6548 : && op1 == *ass_var
419 19259 : && (non_ass_var = independent_of_stmt_p (op0, stmt, call,
420 : to_move)))
421 : ;
422 : else
423 6897 : return TRY_MOVE;
424 :
425 24238 : switch (code)
426 : {
427 6638 : case PLUS_EXPR:
428 6638 : *a = non_ass_var;
429 6638 : *ass_var = dest;
430 6638 : return OK;
431 :
432 458 : case POINTER_PLUS_EXPR:
433 458 : if (op0 != *ass_var)
434 : return FAIL;
435 87 : *a = non_ass_var;
436 87 : *ass_var = dest;
437 87 : return OK;
438 :
439 415 : case MULT_EXPR:
440 415 : *m = non_ass_var;
441 415 : *ass_var = dest;
442 415 : 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 1468 : case MINUS_EXPR:
450 1468 : if (*ass_var == op0)
451 156 : *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
452 : else
453 : {
454 1312 : *m = build_minus_one_cst (TREE_TYPE (non_ass_var));
455 1312 : *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
456 : }
457 :
458 1468 : *ass_var = dest;
459 1468 : return OK;
460 :
461 : default:
462 : return FAIL;
463 : }
464 : }
465 :
466 : /* Propagate VAR through phis on edge E. */
467 :
468 : static tree
469 521077 : propagate_through_phis (tree var, edge e)
470 : {
471 521077 : basic_block dest = e->dest;
472 521077 : gphi_iterator gsi;
473 :
474 985545 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
475 : {
476 534432 : gphi *phi = gsi.phi ();
477 534432 : if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
478 69964 : 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 771819 : maybe_error_musttail (gcall *call, const char *err, bool diag_musttail)
489 : {
490 771819 : if (gimple_call_must_tail_p (call) && diag_musttail)
491 : {
492 44 : 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 44 : gimple_call_set_must_tail (call, false); /* Avoid another error. */
498 44 : gimple_call_set_tail (call, false);
499 : }
500 771819 : 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 771819 : }
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 165 : empty_eh_cleanup (basic_block bb, int *eh_has_tsan_func_exit, int cnt)
513 : {
514 270 : if (EDGE_COUNT (bb->succs) > 1)
515 : return false;
516 :
517 410 : for (gimple_stmt_iterator gsi = gsi_after_labels (bb); !gsi_end_p (gsi);
518 140 : gsi_next (&gsi))
519 : {
520 332 : gimple *g = gsi_stmt (gsi);
521 332 : if (is_gimple_debug (g) || gimple_clobber_p (g))
522 6 : continue;
523 330 : if (eh_has_tsan_func_exit
524 320 : && !*eh_has_tsan_func_exit
525 316 : && sanitize_flags_p (SANITIZE_THREAD)
526 330 : && gimple_call_builtin_p (g, BUILT_IN_TSAN_FUNC_EXIT))
527 : {
528 4 : *eh_has_tsan_func_exit = 1;
529 4 : continue;
530 : }
531 452 : if (eh_has_tsan_func_exit
532 316 : && sanitize_flags_p (SANITIZE_ADDRESS)
533 534 : && asan_mark_p (g, ASAN_MARK_POISON))
534 130 : continue;
535 192 : if (is_gimple_resx (g))
536 : {
537 192 : if (stmt_can_throw_external (cfun, g))
538 165 : return true;
539 192 : if (single_succ_p (bb)
540 27 : && (single_succ_edge (bb)->flags & EDGE_EH)
541 54 : && cnt > 1)
542 27 : return empty_eh_cleanup (single_succ (bb), eh_has_tsan_func_exit,
543 27 : cnt - 1);
544 : }
545 : return false;
546 : }
547 78 : if (!single_succ_p (bb))
548 : return false;
549 78 : if (cnt == 1)
550 : return false;
551 78 : 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 7102345 : 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 7102345 : tree ass_var = NULL_TREE, ret_var, func, param;
581 7102345 : gimple *stmt;
582 7102345 : gcall *call = NULL;
583 7102345 : gimple_stmt_iterator gsi, agsi;
584 7102345 : bool tail_recursion;
585 7102345 : struct tailcall *nw;
586 7102345 : edge e;
587 7102345 : tree m, a;
588 7102345 : basic_block abb;
589 7102345 : size_t idx;
590 7102345 : tree var;
591 7102345 : bool only_tailr = false;
592 7102345 : bool has_tsan_func_exit = false;
593 7102345 : int eh_has_tsan_func_exit = -1;
594 7102345 : bool delete_ignored_edges = false;
595 :
596 7102345 : if (!single_succ_p (bb)
597 7102345 : && (EDGE_COUNT (bb->succs) || !cfun->has_musttail || !diag_musttail))
598 : {
599 1770640 : if (EDGE_COUNT (bb->succs) == 2
600 1732680 : && esucc
601 1732680 : && cfun->has_musttail
602 3410 : && diag_musttail
603 3314 : && (EDGE_SUCC (bb, 0)->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
604 3091 : && (EDGE_SUCC (bb, 1)->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
605 3091 : && (stmt = last_nondebug_stmt (bb))
606 1773731 : && gimple_code (stmt) == GIMPLE_COND)
607 : ;
608 1767549 : else if (esucc
609 1767549 : && cfun->has_musttail
610 353 : && diag_musttail
611 249 : && (stmt = last_nondebug_stmt (bb))
612 1767798 : && gimple_code (stmt) == GIMPLE_SWITCH)
613 : ;
614 : /* If there is an abnormal edge assume it's the only extra one.
615 : Tolerate that case so that we can give better error messages
616 : for musttail later. */
617 1767523 : else if (!has_abnormal_or_eh_outgoing_edge_p (bb))
618 : {
619 1745491 : if (dump_file)
620 109 : fprintf (dump_file, "Basic block %d has extra exit edges\n",
621 : bb->index);
622 6218620 : return;
623 : }
624 25149 : if (!cfun->has_musttail)
625 : return;
626 : }
627 :
628 5335051 : bool bad_stmt = false;
629 5335051 : gimple *last_stmt = nullptr;
630 23150508 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
631 : {
632 15233014 : stmt = gsi_stmt (gsi);
633 :
634 : /* Ignore labels, returns, nops, clobbers and debug stmts. */
635 15233014 : if (gimple_code (stmt) == GIMPLE_LABEL
636 : || gimple_code (stmt) == GIMPLE_RETURN
637 : || gimple_code (stmt) == GIMPLE_NOP
638 : || gimple_code (stmt) == GIMPLE_PREDICT
639 11442987 : || gimple_clobber_p (stmt)
640 10467349 : || is_gimple_debug (stmt))
641 11504563 : continue;
642 :
643 3728451 : if (cfun->has_musttail
644 5974 : && sanitize_flags_p (SANITIZE_THREAD)
645 44 : && gimple_call_builtin_p (stmt, BUILT_IN_TSAN_FUNC_EXIT)
646 3728467 : && diag_musttail)
647 : {
648 16 : if (retry_tsan_func_exit == 0)
649 8 : retry_tsan_func_exit = -1;
650 8 : else if (retry_tsan_func_exit == 1)
651 8 : continue;
652 : }
653 :
654 3728887 : if (cfun->has_musttail
655 5966 : && sanitize_flags_p (SANITIZE_ADDRESS)
656 4064 : && asan_mark_p (stmt, ASAN_MARK_POISON)
657 3729163 : && diag_musttail)
658 444 : continue;
659 :
660 : /* Especially at -O0 with -fsanitize=address we can end up with
661 : code like
662 : _26 = foo (x_24(D)); [must tail call]
663 : finally_tmp.3_27 = 0;
664 : goto <bb 5>; [INV]
665 :
666 : ...
667 :
668 : <bb 5> :
669 : # _6 = PHI <_26(3), _23(D)(4)>
670 : # finally_tmp.3_8 = PHI <finally_tmp.3_27(3), finally_tmp.3_22(4)>
671 : .ASAN_MARK (POISON, &c, 4);
672 : if (finally_tmp.3_8 == 1)
673 : goto <bb 7>; [INV]
674 : else
675 : goto <bb 6>; [INV]
676 : When walking backwards, ESUCC is the edge we are coming from,
677 : depending on its EDGE_TRUE_FLAG, comparison code
678 : and value compared against try to find out through which edge
679 : we need to go and which edge should be ignored. The code handles
680 : both INTEGER_CST PHI arguments and SSA_NAMEs set to constants
681 : (for -O0 where those aren't propagated). */
682 3727999 : if (cfun->has_musttail
683 : && diag_musttail
684 5522 : && esucc
685 4488 : && gimple_code (stmt) == GIMPLE_COND
686 3091 : && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
687 3091 : && TREE_CODE (gimple_cond_rhs (stmt)) == INTEGER_CST
688 3091 : && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
689 3731090 : && tree_int_cst_sgn (gimple_cond_rhs (stmt)) >= 0)
690 : {
691 2995 : tree lhs = gimple_cond_lhs (stmt);
692 2995 : tree_code ccode = gimple_cond_code (stmt);
693 2995 : tree rhsv = gimple_cond_rhs (stmt);
694 2995 : if ((esucc->flags & EDGE_FALSE_VALUE) != 0)
695 2867 : ccode = invert_tree_comparison (ccode, false);
696 2995 : if (!ignored_edges)
697 : {
698 161 : ignored_edges = new hash_set<edge>;
699 161 : must_see_bbs = new hash_set<basic_block>;
700 161 : delete_ignored_edges = true;
701 : }
702 2995 : if (is_gimple_assign (SSA_NAME_DEF_STMT (lhs))
703 2995 : && (gimple_assign_rhs_code (SSA_NAME_DEF_STMT (lhs))
704 : == INTEGER_CST))
705 : {
706 0 : tree lhsv = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (lhs));
707 :
708 0 : if (const_binop (ccode, boolean_type_node, lhsv, rhsv)
709 0 : == boolean_true_node)
710 0 : continue;
711 : }
712 2995 : else if (gimple_code (SSA_NAME_DEF_STMT (lhs)) == GIMPLE_PHI)
713 : {
714 2556 : gimple *phi = SSA_NAME_DEF_STMT (lhs);
715 2556 : basic_block pbb = gimple_bb (phi);
716 2556 : must_see_bbs->add (pbb);
717 2556 : edge_iterator ei;
718 93238 : FOR_EACH_EDGE (e, ei, pbb->preds)
719 : {
720 90682 : tree lhsv = gimple_phi_arg_def_from_edge (phi, e);
721 90682 : if (TREE_CODE (lhsv) == SSA_NAME
722 90682 : && is_gimple_assign (SSA_NAME_DEF_STMT (lhsv))
723 181364 : && (gimple_assign_rhs_code (SSA_NAME_DEF_STMT (lhsv))
724 : == INTEGER_CST))
725 90680 : lhsv = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (lhsv));
726 90682 : if (TREE_CODE (lhsv) != INTEGER_CST
727 90682 : || const_binop (ccode, boolean_type_node,
728 90680 : lhsv, rhsv) != boolean_true_node)
729 16790 : ignored_edges->add (e);
730 : }
731 2556 : continue;
732 2556 : }
733 : }
734 3725443 : if (cfun->has_musttail
735 : && diag_musttail
736 2966 : && esucc
737 1932 : && gimple_code (stmt) == GIMPLE_SWITCH
738 3725469 : && (TREE_CODE (gimple_switch_index (as_a <gswitch *> (stmt)))
739 : == SSA_NAME))
740 : {
741 26 : gswitch *swtch = as_a <gswitch *> (stmt);
742 26 : tree idx = gimple_switch_index (swtch);
743 26 : if (!ignored_edges)
744 : {
745 24 : ignored_edges = new hash_set<edge>;
746 24 : must_see_bbs = new hash_set<basic_block>;
747 24 : delete_ignored_edges = true;
748 : }
749 26 : if (is_gimple_assign (SSA_NAME_DEF_STMT (idx))
750 26 : && (gimple_assign_rhs_code (SSA_NAME_DEF_STMT (idx))
751 : == INTEGER_CST))
752 : {
753 0 : tree val = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (idx));
754 0 : if (find_taken_edge_switch_expr (swtch, val) == esucc)
755 0 : continue;
756 : }
757 26 : else if (gimple_code (SSA_NAME_DEF_STMT (idx)) == GIMPLE_PHI)
758 : {
759 4 : gimple *phi = SSA_NAME_DEF_STMT (idx);
760 4 : basic_block pbb = gimple_bb (phi);
761 4 : must_see_bbs->add (pbb);
762 4 : edge_iterator ei;
763 148 : FOR_EACH_EDGE (e, ei, pbb->preds)
764 : {
765 144 : tree val = gimple_phi_arg_def_from_edge (phi, e);
766 144 : if (TREE_CODE (val) == SSA_NAME
767 144 : && is_gimple_assign (SSA_NAME_DEF_STMT (val))
768 288 : && (gimple_assign_rhs_code (SSA_NAME_DEF_STMT (val))
769 : == INTEGER_CST))
770 144 : val = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (val));
771 144 : if (TREE_CODE (val) != INTEGER_CST
772 144 : || find_taken_edge_switch_expr (swtch, val) != esucc)
773 140 : ignored_edges->add (e);
774 : }
775 4 : continue;
776 4 : }
777 : }
778 :
779 3725439 : if (!last_stmt)
780 3093412 : last_stmt = stmt;
781 : /* Check for a call. */
782 3725439 : if (is_gimple_call (stmt))
783 : {
784 1608666 : call = as_a <gcall *> (stmt);
785 : /* Handle only musttail calls when not optimizing. */
786 1608666 : if (only_musttail && !gimple_call_must_tail_p (call))
787 : {
788 3726459 : maybe_delete_ignored_edges:
789 3726459 : if (delete_ignored_edges)
790 : {
791 356 : delete ignored_edges;
792 356 : delete must_see_bbs;
793 : }
794 3726459 : return;
795 : }
796 1608616 : if (bad_stmt)
797 : {
798 24 : maybe_error_musttail (call, _("memory reference or volatile "
799 : "after call"), diag_musttail);
800 24 : goto maybe_delete_ignored_edges;
801 : }
802 1608592 : ass_var = gimple_call_lhs (call);
803 1608592 : break;
804 : }
805 :
806 : /* Allow simple copies between local variables, even if they're
807 : aggregates. */
808 2116773 : if (is_gimple_assign (stmt)
809 2094355 : && auto_var_in_fn_p (gimple_assign_lhs (stmt), cfun->decl)
810 2170270 : && auto_var_in_fn_p (gimple_assign_rhs1 (stmt), cfun->decl))
811 22641 : continue;
812 :
813 : /* If the statement references memory or volatile operands, fail. */
814 2094132 : if (gimple_references_memory_p (stmt)
815 13429892 : || gimple_has_volatile_ops (stmt))
816 : {
817 1144072 : if (dump_file)
818 : {
819 26 : fprintf (dump_file, "Cannot handle ");
820 26 : print_gimple_stmt (dump_file, stmt, 0);
821 : }
822 1144072 : bad_stmt = true;
823 1144072 : if (!cfun->has_musttail)
824 : break;
825 : }
826 : }
827 :
828 5334977 : if (bad_stmt)
829 1144008 : goto maybe_delete_ignored_edges;
830 :
831 4190969 : if (gsi_end_p (gsi))
832 : {
833 2582377 : if (must_see_bbs)
834 3078 : must_see_bbs->remove (bb);
835 :
836 2582377 : edge_iterator ei;
837 : /* Recurse to the predecessors. */
838 6260471 : FOR_EACH_EDGE (e, ei, bb->preds)
839 : {
840 3678094 : if (ignored_edges && ignored_edges->contains (e))
841 2700 : continue;
842 3675394 : find_tail_calls (e->src, e, ret, only_musttail, opt_tailcalls,
843 : diag_musttail, retry_tsan_func_exit, ignored_edges,
844 : must_see_bbs);
845 : }
846 :
847 2582377 : goto maybe_delete_ignored_edges;
848 : }
849 :
850 1608592 : if (must_see_bbs && !must_see_bbs->is_empty ())
851 0 : goto maybe_delete_ignored_edges;
852 :
853 1608592 : if (delete_ignored_edges)
854 : {
855 14 : delete ignored_edges;
856 14 : delete must_see_bbs;
857 : }
858 :
859 1608592 : if (!suitable_for_tail_opt_p (call, diag_musttail))
860 : return;
861 :
862 1590068 : if (!suitable_for_tail_call_opt_p (call, diag_musttail))
863 16481 : opt_tailcalls = false;
864 :
865 : /* ??? It is OK if the argument of a function is taken in some cases,
866 : but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
867 1590068 : if (!diag_musttail || !gimple_call_must_tail_p (call))
868 1589321 : for (param = DECL_ARGUMENTS (current_function_decl);
869 4689997 : param; param = DECL_CHAIN (param))
870 3100676 : if (TREE_ADDRESSABLE (param))
871 : {
872 30526 : maybe_error_musttail (call, _("address of caller arguments taken"),
873 : diag_musttail);
874 : /* If current function has musttail calls, we can't disable tail
875 : calls altogether for the whole caller, because those might be
876 : actually fine. So just punt if this exact call is not
877 : a tail recursion. */
878 30526 : if (cfun->has_musttail)
879 : only_tailr = true;
880 : else
881 30454 : opt_tailcalls = false;
882 : }
883 :
884 : /* If the LHS of our call is not just a simple register or local
885 : variable, we can't transform this into a tail or sibling call.
886 : This situation happens, in (e.g.) "*p = foo()" where foo returns a
887 : struct. In this case we won't have a temporary here, but we need
888 : to carry out the side effect anyway, so tailcall is impossible.
889 :
890 : ??? In some situations (when the struct is returned in memory via
891 : invisible argument) we could deal with this, e.g. by passing 'p'
892 : itself as that argument to foo, but it's too early to do this here,
893 : and expand_call() will not handle it anyway. If it ever can, then
894 : we need to revisit this here, to allow that situation. */
895 1590068 : if (ass_var
896 454050 : && !is_gimple_reg (ass_var)
897 1642202 : && !auto_var_in_fn_p (ass_var, cfun->decl))
898 : {
899 9266 : maybe_error_musttail (call, _("return value in memory"), diag_musttail);
900 9266 : return;
901 : }
902 :
903 1580802 : if (cfun->calls_setjmp)
904 : {
905 164 : maybe_error_musttail (call, _("caller uses setjmp"), diag_musttail);
906 164 : return;
907 : }
908 :
909 : /* If the call might throw an exception that wouldn't propagate out of
910 : cfun, we can't transform to a tail or sibling call (82081). */
911 1580638 : if ((stmt_could_throw_p (cfun, stmt)
912 1580638 : && !stmt_can_throw_external (cfun, stmt)) || EDGE_COUNT (bb->succs) > 1)
913 : {
914 19737 : if (stmt != last_stmt)
915 : {
916 128 : maybe_error_musttail (call, _("code between call and return"),
917 : diag_musttail);
918 19700 : return;
919 : }
920 :
921 19609 : edge e;
922 19609 : edge_iterator ei;
923 39022 : FOR_EACH_EDGE (e, ei, bb->succs)
924 19621 : if (e->flags & EDGE_EH)
925 : break;
926 :
927 19609 : if (!e)
928 : {
929 19401 : maybe_error_musttail (call, _("call may throw exception that does not "
930 : "propagate"), diag_musttail);
931 19401 : return;
932 : }
933 :
934 208 : if (diag_musttail && gimple_call_must_tail_p (call))
935 159 : eh_has_tsan_func_exit = 0;
936 208 : if (!gimple_call_must_tail_p (call)
937 165 : || !empty_eh_cleanup (e->dest,
938 165 : eh_has_tsan_func_exit
939 : ? NULL : &eh_has_tsan_func_exit, 20)
940 373 : || EDGE_COUNT (bb->succs) > 2)
941 : {
942 43 : maybe_error_musttail (call, _("call may throw exception caught "
943 : "locally or perform cleanups"),
944 : diag_musttail);
945 43 : return;
946 : }
947 : }
948 :
949 : /* If the function returns a value, then at present, the tail call
950 : must return the same type of value. There is conceptually a copy
951 : between the object returned by the tail call candidate and the
952 : object returned by CFUN itself.
953 :
954 : This means that if we have:
955 :
956 : lhs = f (&<retval>); // f reads from <retval>
957 : // (lhs is usually also <retval>)
958 :
959 : there is a copy between the temporary object returned by f and lhs,
960 : meaning that any use of <retval> in f occurs before the assignment
961 : to lhs begins. Thus the <retval> that is live on entry to the call
962 : to f is really an independent local variable V that happens to be
963 : stored in the RESULT_DECL rather than a local VAR_DECL.
964 :
965 : Turning this into a tail call would remove the copy and make the
966 : lifetimes of the return value and V overlap. The same applies to
967 : tail recursion, since if f can read from <retval>, we have to assume
968 : that CFUN might already have written to <retval> before the call.
969 :
970 : The problem doesn't apply when <retval> is passed by value, but that
971 : isn't a case we handle anyway. */
972 1561066 : tree result_decl = DECL_RESULT (cfun->decl);
973 1561066 : if (result_decl
974 1561066 : && may_be_aliased (result_decl)
975 1566555 : && ref_maybe_used_by_stmt_p (call, result_decl, false))
976 : {
977 1423 : maybe_error_musttail (call, _("return value used after call"),
978 : diag_musttail);
979 1423 : return;
980 : }
981 :
982 : /* We found the call, check whether it is suitable. */
983 1559643 : tail_recursion = false;
984 1559643 : func = gimple_call_fndecl (call);
985 1559643 : if (func
986 1482456 : && !fndecl_built_in_p (func)
987 1144504 : && recursive_call_p (current_function_decl, func)
988 1561866 : && !only_musttail)
989 : {
990 2200 : tree arg;
991 :
992 2200 : for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
993 7290 : param && idx < gimple_call_num_args (call);
994 5090 : param = DECL_CHAIN (param), idx ++)
995 : {
996 5230 : arg = gimple_call_arg (call, idx);
997 5230 : if (param != arg)
998 : {
999 : /* Make sure there are no problems with copying. The parameter
1000 : have a copyable type and the two arguments must have reasonably
1001 : equivalent types. The latter requirement could be relaxed if
1002 : we emitted a suitable type conversion statement. */
1003 4995 : if (TREE_ADDRESSABLE (TREE_TYPE (param))
1004 9990 : || !useless_type_conversion_p (TREE_TYPE (param),
1005 4995 : TREE_TYPE (arg)))
1006 : break;
1007 :
1008 9277 : if (is_gimple_reg_type (TREE_TYPE (param))
1009 4959 : ? !is_gimple_reg (param)
1010 641 : : (!is_gimple_variable (param)
1011 641 : || TREE_THIS_VOLATILE (param)
1012 1282 : || may_be_aliased (param)))
1013 : break;
1014 : }
1015 : }
1016 2200 : if (idx == gimple_call_num_args (call) && !param)
1017 1559643 : tail_recursion = true;
1018 : }
1019 :
1020 1559643 : if (only_tailr && !tail_recursion)
1021 : return;
1022 :
1023 : /* Compute live vars if not computed yet. */
1024 1559571 : if (live_vars == NULL)
1025 : {
1026 1511663 : unsigned int cnt = 0;
1027 13285800 : FOR_EACH_LOCAL_DECL (cfun, idx, var)
1028 10461720 : if (VAR_P (var)
1029 10461720 : && auto_var_in_fn_p (var, cfun->decl)
1030 20799133 : && may_be_aliased (var))
1031 : {
1032 873253 : if (live_vars == NULL)
1033 221235 : live_vars = new live_vars_map;
1034 873253 : live_vars->put (DECL_UID (var), cnt++);
1035 : }
1036 1511663 : if (live_vars)
1037 221235 : live_vars_vec = compute_live_vars (cfun, live_vars);
1038 : }
1039 :
1040 : /* Determine a bitmap of variables which are still in scope after the
1041 : call. */
1042 1559571 : bitmap local_live_vars = NULL;
1043 1559571 : if (live_vars)
1044 269143 : local_live_vars = live_vars_at_stmt (live_vars_vec, live_vars, call);
1045 :
1046 : /* Make sure the tail invocation of this function does not indirectly
1047 : refer to local variables. (Passing variables directly by value
1048 : is OK.) */
1049 13527087 : FOR_EACH_LOCAL_DECL (cfun, idx, var)
1050 : {
1051 10813222 : if (TREE_CODE (var) != PARM_DECL
1052 10813222 : && auto_var_in_fn_p (var, cfun->decl)
1053 10733573 : && may_be_aliased (var)
1054 11538360 : && (ref_maybe_used_by_stmt_p (call, var, false)
1055 317401 : || call_may_clobber_ref_p (call, var, false)))
1056 : {
1057 453156 : if (!VAR_P (var))
1058 : {
1059 0 : if (diag_musttail && gimple_call_must_tail_p (call))
1060 : {
1061 0 : auto opt = OPT_Wmaybe_musttail_local_addr;
1062 0 : if (!warning_suppressed_p (call,
1063 : opt))
1064 : {
1065 0 : warning_at (gimple_location (call), opt,
1066 : "address of local variable can escape to "
1067 : "%<musttail%> call");
1068 0 : suppress_warning (call, opt);
1069 : }
1070 0 : continue;
1071 0 : }
1072 0 : if (local_live_vars)
1073 0 : BITMAP_FREE (local_live_vars);
1074 0 : maybe_error_musttail (call, _("call invocation refers to "
1075 : "locals"), diag_musttail);
1076 0 : return;
1077 : }
1078 : else
1079 : {
1080 453156 : unsigned int *v = live_vars->get (DECL_UID (var));
1081 453156 : if (bitmap_bit_p (local_live_vars, *v))
1082 : {
1083 206503 : if (diag_musttail && gimple_call_must_tail_p (call))
1084 : {
1085 472 : auto opt = OPT_Wmaybe_musttail_local_addr;
1086 472 : if (!warning_suppressed_p (call, opt))
1087 : {
1088 195 : if (!DECL_ARTIFICIAL (var) && DECL_NAME (var))
1089 194 : warning_at (gimple_location (call), opt,
1090 : "address of automatic variable %qD "
1091 : "can escape to %<musttail%> call",
1092 : var);
1093 : else
1094 1 : warning_at (gimple_location (call), opt,
1095 : "address of local variable can escape "
1096 : "to %<musttail%> call");
1097 195 : suppress_warning (call, opt);
1098 : }
1099 472 : continue;
1100 472 : }
1101 206031 : BITMAP_FREE (local_live_vars);
1102 206031 : maybe_error_musttail (call, _("call invocation refers to "
1103 : "locals"), diag_musttail);
1104 206031 : return;
1105 : }
1106 : }
1107 : }
1108 : }
1109 1353540 : if (diag_musttail
1110 314394 : && gimple_call_must_tail_p (call)
1111 1354278 : && !warning_suppressed_p (call, OPT_Wmaybe_musttail_local_addr))
1112 396 : for (tree param = DECL_ARGUMENTS (current_function_decl);
1113 782 : param; param = DECL_CHAIN (param))
1114 411 : if (may_be_aliased (param)
1115 411 : && (ref_maybe_used_by_stmt_p (call, param, false)
1116 0 : || call_may_clobber_ref_p (call, param, false)))
1117 : {
1118 25 : auto opt = OPT_Wmaybe_musttail_local_addr;
1119 25 : warning_at (gimple_location (call), opt,
1120 : "address of parameter %qD can escape to "
1121 : "%<musttail%> call", param);
1122 25 : suppress_warning (call, opt);
1123 25 : break;
1124 : }
1125 :
1126 1353540 : if (local_live_vars)
1127 63112 : BITMAP_FREE (local_live_vars);
1128 :
1129 : /* Now check the statements after the call. None of them has virtual
1130 : operands, so they may only depend on the call through its return
1131 : value. The return value should also be dependent on each of them,
1132 : since we are running after dce. */
1133 1353540 : m = NULL_TREE;
1134 1353540 : a = NULL_TREE;
1135 2237265 : auto_bitmap to_move_defs;
1136 2237265 : auto_vec<gimple *> to_move_stmts;
1137 1353540 : bool is_noreturn = gimple_call_noreturn_p (call);
1138 2237265 : auto_vec<edge> edges;
1139 :
1140 1353540 : abb = bb;
1141 1353540 : agsi = gsi;
1142 3293552 : while (!is_noreturn)
1143 : {
1144 3292882 : tree tmp_a = NULL_TREE;
1145 3292882 : tree tmp_m = NULL_TREE;
1146 3292882 : gsi_next (&agsi);
1147 :
1148 : new_bb:
1149 3813959 : while (gsi_end_p (agsi))
1150 : {
1151 520917 : edge e = single_non_eh_succ_edge (abb);
1152 520917 : ass_var = propagate_through_phis (ass_var, e);
1153 520917 : if (!ass_var || ignored_edges)
1154 435563 : edges.safe_push (e);
1155 520917 : abb = e->dest;
1156 1041834 : agsi = gsi_start_bb (abb);
1157 : }
1158 :
1159 3293042 : stmt = gsi_stmt (agsi);
1160 3293042 : if (gimple_code (stmt) == GIMPLE_RETURN)
1161 : break;
1162 :
1163 3953122 : if (gimple_code (stmt) == GIMPLE_LABEL
1164 2003625 : || gimple_code (stmt) == GIMPLE_NOP
1165 2003625 : || gimple_code (stmt) == GIMPLE_PREDICT
1166 1984059 : || gimple_clobber_p (stmt)
1167 3838231 : || is_gimple_debug (stmt))
1168 1921541 : continue;
1169 :
1170 110750 : if (cfun->has_musttail
1171 732 : && sanitize_flags_p (SANITIZE_THREAD)
1172 10 : && retry_tsan_func_exit == 1
1173 10 : && gimple_call_builtin_p (stmt, BUILT_IN_TSAN_FUNC_EXIT)
1174 8 : && !has_tsan_func_exit
1175 110750 : && gimple_call_must_tail_p (call))
1176 : {
1177 8 : has_tsan_func_exit = true;
1178 8 : continue;
1179 : }
1180 :
1181 111030 : if (cfun->has_musttail
1182 724 : && sanitize_flags_p (SANITIZE_ADDRESS)
1183 483 : && asan_mark_p (stmt, ASAN_MARK_POISON)
1184 111030 : && diag_musttail)
1185 296 : continue;
1186 :
1187 : /* See earlier comment on GIMPLE_CONDs. Here we need to propagate
1188 : through on the forward walk, so based on the edges vector we've
1189 : walked through determine which edge to follow. */
1190 110438 : if (ignored_edges)
1191 : {
1192 186 : if (is_gimple_assign (stmt)
1193 26 : && gimple_assign_rhs_code (stmt) == INTEGER_CST
1194 206 : && tree_int_cst_sgn (gimple_assign_rhs1 (stmt)) >= 0)
1195 : {
1196 20 : use_operand_p use_p;
1197 20 : imm_use_iterator imm_iter;
1198 20 : bool bad_p = false;
1199 60 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter,
1200 : gimple_assign_lhs (stmt))
1201 : {
1202 20 : gimple *use_stmt = USE_STMT (use_p);
1203 20 : if (is_gimple_debug (use_stmt)
1204 20 : || gimple_code (use_stmt) == GIMPLE_COND
1205 40 : || gimple_code (use_stmt) == GIMPLE_SWITCH)
1206 0 : continue;
1207 20 : if (gimple_code (use_stmt) == GIMPLE_PHI)
1208 : {
1209 20 : use_operand_p use_p2;
1210 20 : imm_use_iterator imm_iter2;
1211 206 : FOR_EACH_IMM_USE_FAST (use_p2, imm_iter2,
1212 : gimple_phi_result (use_stmt))
1213 : {
1214 166 : gimple *use_stmt2 = USE_STMT (use_p2);
1215 166 : if (is_gimple_debug (use_stmt2)
1216 166 : || gimple_code (use_stmt2) == GIMPLE_COND
1217 168 : || gimple_code (use_stmt2) == GIMPLE_SWITCH)
1218 166 : continue;
1219 : bad_p = true;
1220 : break;
1221 20 : }
1222 20 : if (bad_p)
1223 : break;
1224 : }
1225 : else
1226 : {
1227 : bad_p = true;
1228 : break;
1229 : }
1230 20 : }
1231 20 : if (!bad_p)
1232 20 : continue;
1233 : }
1234 166 : if (gimple_code (stmt) == GIMPLE_COND
1235 158 : && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
1236 158 : && TREE_CODE (gimple_cond_rhs (stmt)) == INTEGER_CST
1237 158 : && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
1238 324 : && tree_int_cst_sgn (gimple_cond_rhs (stmt)) >= 0)
1239 : {
1240 158 : edge e = NULL, et, ef;
1241 158 : enum tree_code ccode = gimple_cond_code (stmt);
1242 158 : tree lhs = gimple_cond_lhs (stmt);
1243 158 : tree rhsv = gimple_cond_rhs (stmt);
1244 158 : extract_true_false_edges_from_block (gimple_bb (stmt), &et, &ef);
1245 158 : if (is_gimple_assign (SSA_NAME_DEF_STMT (lhs))
1246 158 : && (gimple_assign_rhs_code (SSA_NAME_DEF_STMT (lhs))
1247 : == INTEGER_CST))
1248 : {
1249 0 : tree lhsv = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (lhs));
1250 0 : tree r = const_binop (ccode, boolean_type_node, lhsv, rhsv);
1251 0 : if (r == boolean_true_node)
1252 0 : e = et;
1253 0 : else if (r == boolean_false_node)
1254 0 : e = ef;
1255 : }
1256 158 : else if (gimple_code (SSA_NAME_DEF_STMT (lhs)) == GIMPLE_PHI)
1257 : {
1258 158 : gimple *phi = SSA_NAME_DEF_STMT (lhs);
1259 158 : basic_block pbb = gimple_bb (phi);
1260 563 : for (edge e2 : edges)
1261 247 : if (e2->dest == pbb)
1262 : {
1263 158 : tree lhsv = gimple_phi_arg_def_from_edge (phi, e2);
1264 158 : if (TREE_CODE (lhsv) == SSA_NAME)
1265 158 : if (gimple *g = SSA_NAME_DEF_STMT (lhsv))
1266 158 : if (is_gimple_assign (g)
1267 158 : && gimple_assign_rhs_code (g) == INTEGER_CST)
1268 158 : lhsv = gimple_assign_rhs1 (g);
1269 158 : tree r = const_binop (ccode, boolean_type_node,
1270 : lhsv, rhsv);
1271 158 : if (r == boolean_true_node)
1272 6 : e = et;
1273 152 : else if (r == boolean_false_node)
1274 152 : e = ef;
1275 : break;
1276 : }
1277 : }
1278 158 : if (e)
1279 : {
1280 158 : ass_var = propagate_through_phis (ass_var, e);
1281 158 : if (!ass_var || ignored_edges)
1282 158 : edges.safe_push (e);
1283 158 : abb = e->dest;
1284 158 : agsi = gsi_start_bb (abb);
1285 158 : goto new_bb;
1286 : }
1287 : }
1288 8 : if (gimple_code (stmt) == GIMPLE_SWITCH
1289 8 : && (TREE_CODE (gimple_switch_index (as_a <gswitch *> (stmt)))
1290 : == SSA_NAME))
1291 : {
1292 2 : edge e = NULL;
1293 2 : gswitch *swtch = as_a <gswitch *> (stmt);
1294 2 : tree idx = gimple_switch_index (swtch);
1295 2 : if (is_gimple_assign (SSA_NAME_DEF_STMT (idx))
1296 2 : && (gimple_assign_rhs_code (SSA_NAME_DEF_STMT (idx))
1297 : == INTEGER_CST))
1298 : {
1299 0 : tree val = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (idx));
1300 0 : e = find_taken_edge_switch_expr (swtch, val);
1301 : }
1302 2 : else if (gimple_code (SSA_NAME_DEF_STMT (idx)) == GIMPLE_PHI)
1303 : {
1304 2 : gimple *phi = SSA_NAME_DEF_STMT (idx);
1305 2 : basic_block pbb = gimple_bb (phi);
1306 7 : for (edge e2 : edges)
1307 3 : if (e2->dest == pbb)
1308 : {
1309 2 : tree val = gimple_phi_arg_def_from_edge (phi, e2);
1310 2 : if (TREE_CODE (val) == SSA_NAME)
1311 2 : if (gimple *g = SSA_NAME_DEF_STMT (val))
1312 2 : if (is_gimple_assign (g)
1313 2 : && gimple_assign_rhs_code (g) == INTEGER_CST)
1314 2 : val = gimple_assign_rhs1 (g);
1315 2 : if (TREE_CODE (val) == INTEGER_CST)
1316 2 : e = find_taken_edge_switch_expr (swtch, val);
1317 : break;
1318 : }
1319 : }
1320 2 : if (e)
1321 : {
1322 2 : ass_var = propagate_through_phis (ass_var, e);
1323 2 : if (!ass_var || ignored_edges)
1324 2 : edges.safe_push (e);
1325 2 : abb = e->dest;
1326 2 : agsi = gsi_start_bb (abb);
1327 2 : goto new_bb;
1328 : }
1329 : }
1330 : }
1331 :
1332 110258 : if (gimple_code (stmt) != GIMPLE_ASSIGN)
1333 : {
1334 261 : maybe_error_musttail (call, _("unhandled code after call"),
1335 : diag_musttail);
1336 92021 : return;
1337 : }
1338 :
1339 : /* This is a gimple assign. */
1340 109997 : par ret = process_assignment (as_a <gassign *> (stmt), gsi,
1341 : &tmp_m, &tmp_a, &ass_var, to_move_defs);
1342 109997 : if (ret == FAIL || (ret == TRY_MOVE && !tail_recursion))
1343 : {
1344 91486 : maybe_error_musttail (call, _("return value changed after call"),
1345 : diag_musttail);
1346 91486 : return;
1347 : }
1348 18511 : else if (ret == TRY_MOVE)
1349 : {
1350 : /* Do not deal with checking dominance, the real fix is to
1351 : do path isolation for the transform phase anyway, removing
1352 : the need to compute the accumulators with new stmts. */
1353 40 : if (abb != bb)
1354 : return;
1355 81 : for (unsigned opno = 1; opno < gimple_num_ops (stmt); ++opno)
1356 : {
1357 54 : tree op = gimple_op (stmt, opno);
1358 54 : if (independent_of_stmt_p (op, stmt, gsi, to_move_defs) != op)
1359 : return;
1360 : }
1361 54 : bitmap_set_bit (to_move_defs,
1362 27 : SSA_NAME_VERSION (gimple_assign_lhs (stmt)));
1363 27 : to_move_stmts.safe_push (stmt);
1364 27 : continue;
1365 27 : }
1366 :
1367 18471 : if (tmp_a)
1368 : {
1369 8193 : tree type = TREE_TYPE (tmp_a);
1370 8193 : if (a)
1371 418 : a = fold_build2 (PLUS_EXPR, type, fold_convert (type, a), tmp_a);
1372 : else
1373 : a = tmp_a;
1374 : }
1375 18471 : if (tmp_m)
1376 : {
1377 1837 : tree type = TREE_TYPE (tmp_m);
1378 1837 : if (m)
1379 76 : m = fold_build2 (MULT_EXPR, type, fold_convert (type, m), tmp_m);
1380 : else
1381 : m = tmp_m;
1382 :
1383 1837 : if (a)
1384 1322 : a = fold_build2 (MULT_EXPR, type, fold_convert (type, a), tmp_m);
1385 : }
1386 : }
1387 :
1388 : /* See if this is a tail call we can handle. */
1389 1261780 : if (is_noreturn)
1390 : {
1391 670 : if (gimple_call_internal_p (call))
1392 : {
1393 654 : maybe_error_musttail (call, _("internal call"), diag_musttail);
1394 654 : return;
1395 : }
1396 16 : tree rettype = TREE_TYPE (TREE_TYPE (current_function_decl));
1397 16 : tree calltype = TREE_TYPE (gimple_call_fntype (call));
1398 16 : if (!VOID_TYPE_P (rettype)
1399 16 : && !useless_type_conversion_p (rettype, calltype))
1400 : {
1401 0 : maybe_error_musttail (call, _("call and return value are different"),
1402 : diag_musttail);
1403 0 : return;
1404 : }
1405 : ret_var = NULL_TREE;
1406 : }
1407 : else
1408 1261110 : ret_var = gimple_return_retval (as_a <greturn *> (stmt));
1409 :
1410 : /* We may proceed if there either is no return value, or the return value
1411 : is identical to the call's return or if the return decl is an empty type
1412 : variable and the call's return was not assigned. */
1413 1261110 : if (ret_var
1414 1261110 : && (ret_var != ass_var
1415 377983 : && !(is_empty_type (TREE_TYPE (ret_var)) && !ass_var)))
1416 : {
1417 376960 : bool ok = false;
1418 376960 : value_range val;
1419 376960 : if (ass_var == NULL_TREE && !tail_recursion)
1420 : {
1421 376856 : tree other_value = NULL_TREE;
1422 : /* If we have a function call that we know the return value is the same
1423 : as the argument, try the argument too. */
1424 376856 : int flags = gimple_call_return_flags (call);
1425 376856 : if ((flags & ERF_RETURNS_ARG) != 0
1426 376856 : && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (call))
1427 : {
1428 4409 : tree arg = gimple_call_arg (call, flags & ERF_RETURN_ARG_MASK);
1429 4409 : if (useless_type_conversion_p (TREE_TYPE (ret_var), TREE_TYPE (arg) ))
1430 : other_value = arg;
1431 : }
1432 : /* If IPA-VRP proves called function always returns a singleton range,
1433 : the return value is replaced by the only value in that range.
1434 : For tail call purposes, pretend such replacement didn't happen. */
1435 372447 : else if (tree type = gimple_range_type (call))
1436 82492 : if (tree callee = gimple_call_fndecl (call))
1437 : {
1438 82059 : tree valr;
1439 82059 : if ((INTEGRAL_TYPE_P (type)
1440 : || SCALAR_FLOAT_TYPE_P (type)
1441 82059 : || POINTER_TYPE_P (type))
1442 82059 : && useless_type_conversion_p (TREE_TYPE (TREE_TYPE (callee)),
1443 : type)
1444 82051 : && useless_type_conversion_p (TREE_TYPE (ret_var), type)
1445 21902 : && ipa_return_value_range (val, callee)
1446 91977 : && val.singleton_p (&valr))
1447 6857 : other_value = valr;
1448 : }
1449 :
1450 84674 : if (other_value)
1451 : {
1452 9472 : tree rv = ret_var;
1453 9472 : unsigned int i = edges.length ();
1454 : /* If ret_var is equal to other_value, we can tail optimize. */
1455 9472 : if (operand_equal_p (ret_var, other_value, 0))
1456 : ok = true;
1457 : else
1458 : /* Otherwise, if ret_var is a PHI result, try to find out
1459 : if other_value isn't propagated through PHIs on the path from
1460 : call's bb to SSA_NAME_DEF_STMT (ret_var)'s bb. */
1461 4087 : while (TREE_CODE (rv) == SSA_NAME
1462 4087 : && gimple_code (SSA_NAME_DEF_STMT (rv)) == GIMPLE_PHI)
1463 : {
1464 1601 : tree nrv = NULL_TREE;
1465 : gimple *g = SSA_NAME_DEF_STMT (rv);
1466 1601 : for (; i; --i)
1467 : {
1468 1565 : if (edges[i - 1]->dest == gimple_bb (g))
1469 : {
1470 1565 : nrv = gimple_phi_arg_def_from_edge (g,
1471 1565 : edges[i - 1]);
1472 1565 : --i;
1473 1565 : break;
1474 : }
1475 : }
1476 1601 : if (nrv == NULL_TREE)
1477 : break;
1478 1565 : if (operand_equal_p (nrv, other_value, 0))
1479 : {
1480 : ok = true;
1481 : break;
1482 : }
1483 : rv = nrv;
1484 : }
1485 : }
1486 : }
1487 2915 : if (!ok)
1488 : {
1489 370010 : maybe_error_musttail (call, _("call and return value are different"),
1490 : diag_musttail);
1491 370010 : return;
1492 : }
1493 376960 : }
1494 :
1495 : /* If this is not a tail recursive call, we cannot handle addends or
1496 : multiplicands. */
1497 891116 : if (!tail_recursion && (m || a))
1498 : {
1499 7391 : maybe_error_musttail (call, _("operations after non tail recursive "
1500 : "call"), diag_musttail);
1501 7391 : return;
1502 : }
1503 :
1504 : /* For pointers only allow additions. */
1505 1266 : if (m && POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
1506 : {
1507 0 : maybe_error_musttail (call, _("tail recursion with pointers can only "
1508 : "use additions"), diag_musttail);
1509 0 : return;
1510 : }
1511 :
1512 883725 : if (eh_has_tsan_func_exit != -1
1513 159 : && eh_has_tsan_func_exit != has_tsan_func_exit)
1514 : {
1515 0 : if (eh_has_tsan_func_exit)
1516 0 : maybe_error_musttail (call, _("call may throw exception caught "
1517 : "locally or perform cleanups"),
1518 : diag_musttail);
1519 : else
1520 0 : maybe_error_musttail (call, _("exception cleanups omit "
1521 : "__tsan_func_exit call"), diag_musttail);
1522 0 : return;
1523 : }
1524 :
1525 : /* Move queued defs. */
1526 883725 : if (tail_recursion)
1527 : {
1528 : unsigned i;
1529 1269 : FOR_EACH_VEC_ELT (to_move_stmts, i, stmt)
1530 : {
1531 3 : gimple_stmt_iterator mgsi = gsi_for_stmt (stmt);
1532 3 : gsi_move_before (&mgsi, &gsi);
1533 : }
1534 1266 : if (!tailr_arg_needs_copy)
1535 1125 : tailr_arg_needs_copy = BITMAP_ALLOC (NULL);
1536 1266 : for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
1537 4478 : param;
1538 3212 : param = DECL_CHAIN (param), idx++)
1539 : {
1540 3212 : tree ddef, arg = gimple_call_arg (call, idx);
1541 3212 : if (!is_gimple_reg (param)
1542 3212 : || ((ddef = ssa_default_def (cfun, param))
1543 2638 : && arg != ddef))
1544 1986 : bitmap_set_bit (tailr_arg_needs_copy, idx);
1545 : }
1546 : }
1547 :
1548 883725 : nw = XNEW (struct tailcall);
1549 :
1550 883725 : nw->call_gsi = gsi;
1551 :
1552 883725 : nw->tail_recursion = tail_recursion;
1553 883725 : nw->has_tsan_func_exit = has_tsan_func_exit;
1554 :
1555 883725 : nw->mult = m;
1556 883725 : nw->add = a;
1557 :
1558 883725 : nw->next = *ret;
1559 883725 : *ret = nw;
1560 : }
1561 :
1562 : /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
1563 :
1564 : static void
1565 220 : add_successor_phi_arg (edge e, tree var, tree phi_arg)
1566 : {
1567 220 : gphi_iterator gsi;
1568 :
1569 474 : for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
1570 474 : if (PHI_RESULT (gsi.phi ()) == var)
1571 : break;
1572 :
1573 220 : gcc_assert (!gsi_end_p (gsi));
1574 220 : add_phi_arg (gsi.phi (), phi_arg, e, UNKNOWN_LOCATION);
1575 220 : }
1576 :
1577 : /* Creates a GIMPLE statement which computes the operation specified by
1578 : CODE, ACC and OP1 to a new variable with name LABEL and inserts the
1579 : statement in the position specified by GSI. Returns the
1580 : tree node of the statement's result. */
1581 :
1582 : static tree
1583 186 : adjust_return_value_with_ops (enum tree_code code, const char *label,
1584 : tree acc, tree op1, gimple_stmt_iterator gsi)
1585 : {
1586 :
1587 186 : tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
1588 186 : tree result = make_temp_ssa_name (ret_type, NULL, label);
1589 186 : gassign *stmt;
1590 :
1591 186 : if (POINTER_TYPE_P (ret_type))
1592 : {
1593 6 : gcc_assert (code == PLUS_EXPR && TREE_TYPE (acc) == sizetype);
1594 : code = POINTER_PLUS_EXPR;
1595 : }
1596 186 : if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1))
1597 186 : && code != POINTER_PLUS_EXPR)
1598 175 : stmt = gimple_build_assign (result, code, acc, op1);
1599 : else
1600 : {
1601 11 : tree tem;
1602 11 : if (code == POINTER_PLUS_EXPR)
1603 6 : tem = fold_build2 (code, TREE_TYPE (op1), op1, acc);
1604 : else
1605 5 : tem = fold_build2 (code, TREE_TYPE (op1),
1606 : fold_convert (TREE_TYPE (op1), acc), op1);
1607 11 : tree rhs = fold_convert (ret_type, tem);
1608 11 : rhs = force_gimple_operand_gsi (&gsi, rhs,
1609 : false, NULL, true, GSI_SAME_STMT);
1610 11 : stmt = gimple_build_assign (result, rhs);
1611 : }
1612 :
1613 186 : gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1614 186 : return result;
1615 : }
1616 :
1617 : /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
1618 : the computation specified by CODE and OP1 and insert the statement
1619 : at the position specified by GSI as a new statement. Returns new SSA name
1620 : of updated accumulator. */
1621 :
1622 : static tree
1623 217 : update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
1624 : gimple_stmt_iterator gsi)
1625 : {
1626 217 : gassign *stmt;
1627 217 : tree var = copy_ssa_name (acc);
1628 217 : if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
1629 203 : stmt = gimple_build_assign (var, code, acc, op1);
1630 : else
1631 : {
1632 14 : tree rhs = fold_convert (TREE_TYPE (acc),
1633 : fold_build2 (code,
1634 : TREE_TYPE (op1),
1635 : fold_convert (TREE_TYPE (op1), acc),
1636 : op1));
1637 14 : rhs = force_gimple_operand_gsi (&gsi, rhs,
1638 : false, NULL, false, GSI_CONTINUE_LINKING);
1639 14 : stmt = gimple_build_assign (var, rhs);
1640 : }
1641 217 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1642 217 : return var;
1643 : }
1644 :
1645 : /* Adjust the accumulator values according to A and M after GSI, and update
1646 : the phi nodes on edge BACK. */
1647 :
1648 : static void
1649 1260 : adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
1650 : {
1651 1260 : tree var, a_acc_arg, m_acc_arg;
1652 :
1653 1260 : if (m)
1654 115 : m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT);
1655 1260 : if (a)
1656 102 : a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT);
1657 :
1658 1260 : a_acc_arg = a_acc;
1659 1260 : m_acc_arg = m_acc;
1660 1260 : if (a)
1661 : {
1662 102 : if (m_acc)
1663 : {
1664 18 : if (integer_onep (a))
1665 1 : var = m_acc;
1666 : else
1667 17 : var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
1668 : a, gsi);
1669 : }
1670 : else
1671 : var = a;
1672 :
1673 102 : a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
1674 : }
1675 :
1676 1260 : if (m)
1677 115 : m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
1678 :
1679 1260 : if (a_acc)
1680 105 : add_successor_phi_arg (back, a_acc, a_acc_arg);
1681 :
1682 1260 : if (m_acc)
1683 115 : add_successor_phi_arg (back, m_acc, m_acc_arg);
1684 1260 : }
1685 :
1686 : /* Adjust value of the return at the end of BB according to M and A
1687 : accumulators. */
1688 :
1689 : static void
1690 156 : adjust_return_value (basic_block bb, tree m, tree a)
1691 : {
1692 156 : tree retval;
1693 312 : greturn *ret_stmt = as_a <greturn *> (gimple_seq_last_stmt (bb_seq (bb)));
1694 156 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
1695 :
1696 156 : gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
1697 :
1698 156 : retval = gimple_return_retval (ret_stmt);
1699 156 : if (!retval || retval == error_mark_node)
1700 0 : return;
1701 :
1702 156 : if (m)
1703 86 : retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
1704 : gsi);
1705 156 : if (a)
1706 83 : retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
1707 : gsi);
1708 156 : gimple_return_set_retval (ret_stmt, retval);
1709 156 : update_stmt (ret_stmt);
1710 : }
1711 :
1712 : /* Subtract COUNT and FREQUENCY from the basic block and it's
1713 : outgoing edge. */
1714 : static void
1715 3514 : decrease_profile (basic_block bb, profile_count count)
1716 : {
1717 0 : bb->count = bb->count - count;
1718 0 : }
1719 :
1720 : /* Eliminates tail call described by T. TMP_VARS is a list of
1721 : temporary variables used to copy the function arguments.
1722 : Allocates *NEW_LOOP if not already done and initializes it. */
1723 :
1724 : static void
1725 1260 : eliminate_tail_call (struct tailcall *t, class loop *&new_loop)
1726 : {
1727 1260 : tree param, rslt;
1728 1260 : gimple *stmt, *call;
1729 1260 : tree arg;
1730 1260 : size_t idx;
1731 1260 : basic_block bb, first;
1732 1260 : edge e;
1733 1260 : gphi *phi;
1734 1260 : gphi_iterator gpi;
1735 1260 : gimple_stmt_iterator gsi;
1736 1260 : gimple *orig_stmt;
1737 :
1738 1260 : stmt = orig_stmt = gsi_stmt (t->call_gsi);
1739 1260 : bb = gsi_bb (t->call_gsi);
1740 :
1741 1260 : if (dump_file && (dump_flags & TDF_DETAILS))
1742 : {
1743 8 : fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
1744 : bb->index);
1745 8 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1746 8 : fprintf (dump_file, "\n");
1747 : }
1748 :
1749 1260 : gcc_assert (is_gimple_call (stmt));
1750 :
1751 1260 : first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1752 :
1753 : /* Remove the code after call_gsi that will become unreachable. The
1754 : possibly unreachable code in other blocks is removed later in
1755 : cfg cleanup. */
1756 1260 : gsi = t->call_gsi;
1757 1260 : gimple_stmt_iterator gsi2 = gsi_last_bb (gimple_bb (gsi_stmt (gsi)));
1758 2591 : while (gsi_stmt (gsi2) != gsi_stmt (gsi))
1759 : {
1760 1331 : gimple *t = gsi_stmt (gsi2);
1761 : /* Do not remove the return statement, so that redirect_edge_and_branch
1762 : sees how the block ends. */
1763 1331 : if (gimple_code (t) != GIMPLE_RETURN)
1764 : {
1765 1077 : gimple_stmt_iterator gsi3 = gsi2;
1766 1077 : gsi_prev (&gsi2);
1767 1077 : gsi_remove (&gsi3, true);
1768 1077 : release_defs (t);
1769 : }
1770 : else
1771 2845 : gsi_prev (&gsi2);
1772 : }
1773 :
1774 1260 : if (gimple_call_noreturn_p (as_a <gcall *> (stmt)))
1775 : {
1776 4 : e = make_edge (gsi_bb (t->call_gsi), first, EDGE_FALLTHRU);
1777 4 : e->probability = profile_probability::always ();
1778 : }
1779 : else
1780 : {
1781 : /* Number of executions of function has reduced by the tailcall. */
1782 1256 : e = single_non_eh_succ_edge (gsi_bb (t->call_gsi));
1783 :
1784 1256 : profile_count count = e->count ();
1785 :
1786 : /* When profile is inconsistent and the recursion edge is more frequent
1787 : than number of executions of functions, scale it down, so we do not
1788 : end up with 0 executions of entry block. */
1789 1256 : if (count >= ENTRY_BLOCK_PTR_FOR_FN (cfun)->count)
1790 38 : count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.apply_scale (7, 8);
1791 1256 : decrease_profile (EXIT_BLOCK_PTR_FOR_FN (cfun), count);
1792 1256 : decrease_profile (ENTRY_BLOCK_PTR_FOR_FN (cfun), count);
1793 1256 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1794 1002 : decrease_profile (e->dest, count);
1795 :
1796 : /* Replace the call by a jump to the start of function. */
1797 1256 : e = redirect_edge_and_branch (e, first);
1798 : }
1799 1260 : gcc_assert (e);
1800 1260 : PENDING_STMT (e) = NULL;
1801 :
1802 : /* Add the new loop. */
1803 1260 : if (!new_loop)
1804 : {
1805 1123 : new_loop = alloc_loop ();
1806 1123 : new_loop->header = first;
1807 1123 : new_loop->finite_p = true;
1808 : }
1809 : else
1810 137 : gcc_assert (new_loop->header == first);
1811 :
1812 : /* Add phi node entries for arguments. The ordering of the phi nodes should
1813 : be the same as the ordering of the arguments. */
1814 1260 : auto_vec<tree> copies;
1815 1260 : for (param = DECL_ARGUMENTS (current_function_decl),
1816 1260 : idx = 0, gpi = gsi_start_phis (first);
1817 4460 : param;
1818 3200 : param = DECL_CHAIN (param), idx++)
1819 : {
1820 3200 : if (!bitmap_bit_p (tailr_arg_needs_copy, idx))
1821 1211 : continue;
1822 :
1823 1989 : if (!is_gimple_reg_type (TREE_TYPE (param)))
1824 : {
1825 529 : if (param == gimple_call_arg (stmt, idx))
1826 158 : continue;
1827 : /* First check if param isn't used by any of the following
1828 : call arguments. If it is, we need to copy first to
1829 : a temporary and only after doing all the assignments copy it
1830 : to param. */
1831 371 : size_t idx2 = idx + 1;
1832 371 : tree param2 = DECL_CHAIN (param);
1833 1756 : for (; param2; param2 = DECL_CHAIN (param2), idx2++)
1834 1386 : if (!is_gimple_reg_type (TREE_TYPE (param)))
1835 : {
1836 1386 : tree base = get_base_address (gimple_call_arg (stmt, idx2));
1837 1386 : if (base == param)
1838 : break;
1839 : }
1840 371 : tree tmp = param;
1841 371 : if (param2)
1842 : {
1843 1 : tmp = create_tmp_var (TREE_TYPE (param));
1844 1 : copies.safe_push (param);
1845 1 : copies.safe_push (tmp);
1846 : }
1847 371 : gimple *g = gimple_build_assign (tmp, gimple_call_arg (stmt, idx));
1848 371 : gsi_insert_before (&t->call_gsi, g, GSI_SAME_STMT);
1849 371 : continue;
1850 371 : }
1851 :
1852 1460 : arg = gimple_call_arg (stmt, idx);
1853 1460 : phi = gpi.phi ();
1854 1460 : gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
1855 :
1856 1460 : add_phi_arg (phi, arg, e, gimple_location (stmt));
1857 1460 : gsi_next (&gpi);
1858 : }
1859 1261 : for (unsigned i = 0; i < copies.length (); i += 2)
1860 : {
1861 1 : gimple *g = gimple_build_assign (copies[i], copies[i + 1]);
1862 1 : gsi_insert_before (&t->call_gsi, g, GSI_SAME_STMT);
1863 : }
1864 :
1865 : /* Update the values of accumulators. */
1866 1260 : adjust_accumulator_values (t->call_gsi, t->mult, t->add, e);
1867 :
1868 1260 : call = gsi_stmt (t->call_gsi);
1869 1260 : rslt = gimple_call_lhs (call);
1870 1260 : if (rslt != NULL_TREE && TREE_CODE (rslt) == SSA_NAME)
1871 : {
1872 : /* Result of the call will no longer be defined. So adjust the
1873 : SSA_NAME_DEF_STMT accordingly. */
1874 598 : SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
1875 : }
1876 :
1877 1260 : gsi_remove (&t->call_gsi, true);
1878 1260 : release_defs (call);
1879 1260 : }
1880 :
1881 : /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
1882 : mark the tailcalls for the sibcall optimization. */
1883 :
1884 : static bool
1885 883719 : optimize_tail_call (struct tailcall *t, bool opt_tailcalls,
1886 : class loop *&new_loop)
1887 : {
1888 883719 : if (t->has_tsan_func_exit && (t->tail_recursion || opt_tailcalls))
1889 : {
1890 8 : tree builtin_decl = builtin_decl_implicit (BUILT_IN_TSAN_FUNC_EXIT);
1891 8 : gimple *g = gimple_build_call (builtin_decl, 0);
1892 8 : gimple_set_location (g, cfun->function_end_locus);
1893 8 : gsi_insert_before (&t->call_gsi, g, GSI_SAME_STMT);
1894 : }
1895 :
1896 883719 : if (t->tail_recursion)
1897 : {
1898 1260 : eliminate_tail_call (t, new_loop);
1899 1260 : return true;
1900 : }
1901 :
1902 882459 : if (opt_tailcalls)
1903 : {
1904 178209 : gcall *stmt = as_a <gcall *> (gsi_stmt (t->call_gsi));
1905 :
1906 178209 : gimple_call_set_tail (stmt, true);
1907 178209 : cfun->tail_call_marked = true;
1908 178209 : if (dump_file && (dump_flags & TDF_DETAILS))
1909 : {
1910 25 : fprintf (dump_file, "Found tail call ");
1911 25 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1912 25 : fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
1913 : }
1914 178209 : return t->has_tsan_func_exit;
1915 : }
1916 :
1917 : return false;
1918 : }
1919 :
1920 : /* Creates a tail-call accumulator of the same type as the return type of the
1921 : current function. LABEL is the name used to creating the temporary
1922 : variable for the accumulator. The accumulator will be inserted in the
1923 : phis of a basic block BB with single predecessor with an initial value
1924 : INIT converted to the current function return type. */
1925 :
1926 : static tree
1927 202 : create_tailcall_accumulator (const char *label, basic_block bb, tree init)
1928 : {
1929 202 : tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
1930 202 : if (POINTER_TYPE_P (ret_type))
1931 6 : ret_type = sizetype;
1932 :
1933 202 : tree tmp = make_temp_ssa_name (ret_type, NULL, label);
1934 202 : gphi *phi;
1935 :
1936 202 : phi = create_phi_node (tmp, bb);
1937 202 : add_phi_arg (phi, init, single_pred_edge (bb),
1938 : UNKNOWN_LOCATION);
1939 202 : return PHI_RESULT (phi);
1940 : }
1941 :
1942 : /* Optimizes tail calls in the function, turning the tail recursion
1943 : into iteration. When ONLY_MUSTTAIL is true only optimize musttail
1944 : marked calls. When DIAG_MUSTTAIL, diagnose if musttail calls can't
1945 : be tail call optimized. */
1946 :
1947 : static unsigned int
1948 3495089 : tree_optimize_tail_calls_1 (bool opt_tailcalls, bool only_musttail,
1949 : bool diag_musttail)
1950 : {
1951 3495089 : edge e;
1952 3495089 : bool phis_constructed = false;
1953 3495089 : struct tailcall *tailcalls = NULL, *act, *next;
1954 3495089 : bool changed = false;
1955 3495089 : basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1956 3495089 : tree param;
1957 3495089 : edge_iterator ei;
1958 :
1959 6922866 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
1960 : {
1961 : /* Only traverse the normal exits, i.e. those that end with return
1962 : statement. */
1963 10282481 : if (safe_is_a <greturn *> (*gsi_last_bb (e->src)))
1964 : {
1965 3426927 : int retry_tsan_func_exit = 0;
1966 3426927 : find_tail_calls (e->src, e, &tailcalls, only_musttail, opt_tailcalls,
1967 : diag_musttail, retry_tsan_func_exit, NULL, NULL);
1968 3426927 : if (retry_tsan_func_exit == -1)
1969 : {
1970 8 : retry_tsan_func_exit = 1;
1971 8 : find_tail_calls (e->src, e, &tailcalls, only_musttail,
1972 : opt_tailcalls, diag_musttail,
1973 : retry_tsan_func_exit, NULL, NULL);
1974 : }
1975 : }
1976 : }
1977 3495089 : if (cfun->has_musttail && diag_musttail)
1978 : {
1979 503 : basic_block bb;
1980 503 : int retry_tsan_func_exit = 0;
1981 4815 : FOR_EACH_BB_FN (bb, cfun)
1982 4312 : if (EDGE_COUNT (bb->succs) == 0
1983 4184 : || (single_succ_p (bb)
1984 2859 : && (single_succ_edge (bb)->flags & EDGE_EH)))
1985 236 : if (gimple *c = last_nondebug_stmt (bb))
1986 236 : if (is_gimple_call (c)
1987 16 : && gimple_call_must_tail_p (as_a <gcall *> (c))
1988 252 : && gimple_call_noreturn_p (as_a <gcall *> (c)))
1989 16 : find_tail_calls (bb, NULL, &tailcalls, only_musttail,
1990 : opt_tailcalls, diag_musttail,
1991 : retry_tsan_func_exit, NULL, NULL);
1992 : }
1993 :
1994 3495089 : if (live_vars)
1995 : {
1996 221235 : destroy_live_vars (live_vars_vec);
1997 442470 : delete live_vars;
1998 221235 : live_vars = NULL;
1999 : }
2000 :
2001 3495089 : if (cfun->has_musttail)
2002 : {
2003 : /* We can't mix non-recursive must tail calls with tail recursive
2004 : calls which require accumulators, because in that case we have to
2005 : emit code in between the musttail calls and return, which prevent
2006 : calling them as tail calls. So, in that case give up on the
2007 : tail recursion. */
2008 1130 : for (act = tailcalls; act; act = act->next)
2009 722 : if (!act->tail_recursion)
2010 : {
2011 680 : gcall *call = as_a <gcall *> (gsi_stmt (act->call_gsi));
2012 680 : if (gimple_call_must_tail_p (call))
2013 : break;
2014 : }
2015 1076 : if (act)
2016 1782 : for (struct tailcall **p = &tailcalls; *p; )
2017 : {
2018 1114 : if ((*p)->tail_recursion && ((*p)->add || (*p)->mult))
2019 : {
2020 6 : struct tailcall *a = *p;
2021 6 : *p = (*p)->next;
2022 6 : gcall *call = as_a <gcall *> (gsi_stmt (a->call_gsi));
2023 6 : maybe_error_musttail (call, _("tail recursion with "
2024 : "accumulation mixed with "
2025 : "musttail non-recursive call"),
2026 : diag_musttail);
2027 6 : free (a);
2028 6 : }
2029 : else
2030 1108 : p = &(*p)->next;
2031 : }
2032 : }
2033 : /* Construct the phi nodes and accumulators if necessary. */
2034 3495089 : a_acc = m_acc = NULL_TREE;
2035 4378808 : for (act = tailcalls; act; act = act->next)
2036 : {
2037 883719 : if (!act->tail_recursion)
2038 882459 : continue;
2039 :
2040 1260 : if (!phis_constructed)
2041 : {
2042 : /* Ensure that there is only one predecessor of the block
2043 : or if there are existing degenerate PHI nodes. */
2044 1123 : if (!single_pred_p (first)
2045 1123 : || !gimple_seq_empty_p (phi_nodes (first)))
2046 0 : first
2047 0 : = split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
2048 :
2049 : /* Copy the args if needed. */
2050 1123 : unsigned idx;
2051 1123 : for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
2052 4016 : param;
2053 2893 : param = DECL_CHAIN (param), idx++)
2054 2893 : if (bitmap_bit_p (tailr_arg_needs_copy, idx))
2055 : {
2056 1826 : if (!is_gimple_reg_type (TREE_TYPE (param)))
2057 529 : continue;
2058 1297 : tree name = ssa_default_def (cfun, param);
2059 1297 : tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
2060 1297 : gphi *phi;
2061 :
2062 1297 : set_ssa_default_def (cfun, param, new_name);
2063 1297 : phi = create_phi_node (name, first);
2064 1297 : add_phi_arg (phi, new_name, single_pred_edge (first),
2065 1297 : EXPR_LOCATION (param));
2066 : }
2067 : phis_constructed = true;
2068 : }
2069 1260 : tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
2070 1260 : if (POINTER_TYPE_P (ret_type))
2071 176 : ret_type = sizetype;
2072 :
2073 1260 : if (act->add && !a_acc)
2074 96 : a_acc = create_tailcall_accumulator ("add_acc", first,
2075 : build_zero_cst (ret_type));
2076 :
2077 1260 : if (act->mult && !m_acc)
2078 106 : m_acc = create_tailcall_accumulator ("mult_acc", first,
2079 : build_one_cst (ret_type));
2080 : }
2081 :
2082 3495089 : if (a_acc || m_acc)
2083 : {
2084 : /* When the tail call elimination using accumulators is performed,
2085 : statements adding the accumulated value are inserted at all exits.
2086 : This turns all other tail calls to non-tail ones. */
2087 184 : opt_tailcalls = false;
2088 : }
2089 :
2090 3495089 : class loop *new_loop = NULL;
2091 4378808 : for (; tailcalls; tailcalls = next)
2092 : {
2093 883719 : next = tailcalls->next;
2094 883719 : changed |= optimize_tail_call (tailcalls, opt_tailcalls, new_loop);
2095 883719 : free (tailcalls);
2096 : }
2097 3495089 : if (new_loop)
2098 1123 : add_loop (new_loop, loops_for_fn (cfun)->tree_root);
2099 :
2100 3495089 : if (a_acc || m_acc)
2101 : {
2102 : /* Modify the remaining return statements. */
2103 340 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2104 : {
2105 468 : if (safe_is_a <greturn *> (*gsi_last_bb (e->src)))
2106 156 : adjust_return_value (e->src, m_acc, a_acc);
2107 : }
2108 : }
2109 :
2110 3495089 : if (changed)
2111 1129 : free_dominance_info (CDI_DOMINATORS);
2112 :
2113 : /* Add phi nodes for the virtual operands defined in the function to the
2114 : header of the loop created by tail recursion elimination. Do so
2115 : by triggering the SSA renamer. */
2116 3495089 : if (phis_constructed)
2117 1123 : mark_virtual_operands_for_renaming (cfun);
2118 :
2119 3495089 : if (tailr_arg_needs_copy)
2120 1125 : BITMAP_FREE (tailr_arg_needs_copy);
2121 :
2122 3495089 : if (diag_musttail)
2123 724688 : cfun->has_musttail = false;
2124 :
2125 3495089 : if (changed)
2126 1129 : return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
2127 : return 0;
2128 : }
2129 :
2130 : static bool
2131 4495396 : gate_tail_calls (void)
2132 : {
2133 4495396 : return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
2134 : }
2135 :
2136 : static unsigned int
2137 724453 : execute_tail_calls (void)
2138 : {
2139 0 : return tree_optimize_tail_calls_1 (true, false, true);
2140 : }
2141 :
2142 : namespace {
2143 :
2144 : const pass_data pass_data_tail_recursion =
2145 : {
2146 : GIMPLE_PASS, /* type */
2147 : "tailr", /* name */
2148 : OPTGROUP_NONE, /* optinfo_flags */
2149 : TV_NONE, /* tv_id */
2150 : ( PROP_cfg | PROP_ssa ), /* properties_required */
2151 : 0, /* properties_provided */
2152 : 0, /* properties_destroyed */
2153 : 0, /* todo_flags_start */
2154 : 0, /* todo_flags_finish */
2155 : };
2156 :
2157 : class pass_tail_recursion : public gimple_opt_pass
2158 : {
2159 : public:
2160 571444 : pass_tail_recursion (gcc::context *ctxt)
2161 1142888 : : gimple_opt_pass (pass_data_tail_recursion, ctxt)
2162 : {}
2163 :
2164 : /* opt_pass methods: */
2165 285722 : opt_pass * clone () final override
2166 : {
2167 285722 : return new pass_tail_recursion (m_ctxt);
2168 : }
2169 3453912 : bool gate (function *) final override { return gate_tail_calls (); }
2170 2770401 : unsigned int execute (function *) final override
2171 : {
2172 2770401 : return tree_optimize_tail_calls_1 (false, false, false);
2173 : }
2174 :
2175 : }; // class pass_tail_recursion
2176 :
2177 : } // anon namespace
2178 :
2179 : gimple_opt_pass *
2180 285722 : make_pass_tail_recursion (gcc::context *ctxt)
2181 : {
2182 285722 : return new pass_tail_recursion (ctxt);
2183 : }
2184 :
2185 : namespace {
2186 :
2187 : const pass_data pass_data_tail_calls =
2188 : {
2189 : GIMPLE_PASS, /* type */
2190 : "tailc", /* name */
2191 : OPTGROUP_NONE, /* optinfo_flags */
2192 : TV_NONE, /* tv_id */
2193 : ( PROP_cfg | PROP_ssa ), /* properties_required */
2194 : 0, /* properties_provided */
2195 : 0, /* properties_destroyed */
2196 : 0, /* todo_flags_start */
2197 : 0, /* todo_flags_finish */
2198 : };
2199 :
2200 : class pass_tail_calls : public gimple_opt_pass
2201 : {
2202 : public:
2203 285722 : pass_tail_calls (gcc::context *ctxt)
2204 571444 : : gimple_opt_pass (pass_data_tail_calls, ctxt)
2205 : {}
2206 :
2207 : /* opt_pass methods: */
2208 1041484 : bool gate (function *) final override { return gate_tail_calls (); }
2209 724453 : unsigned int execute (function *) final override
2210 : {
2211 724453 : return execute_tail_calls ();
2212 : }
2213 :
2214 : }; // class pass_tail_calls
2215 :
2216 : } // anon namespace
2217 :
2218 : gimple_opt_pass *
2219 285722 : make_pass_tail_calls (gcc::context *ctxt)
2220 : {
2221 285722 : return new pass_tail_calls (ctxt);
2222 : }
2223 :
2224 : namespace {
2225 :
2226 : const pass_data pass_data_musttail =
2227 : {
2228 : GIMPLE_PASS, /* type */
2229 : "musttail", /* name */
2230 : OPTGROUP_NONE, /* optinfo_flags */
2231 : TV_NONE, /* tv_id */
2232 : ( PROP_cfg | PROP_ssa ), /* properties_required */
2233 : 0, /* properties_provided */
2234 : 0, /* properties_destroyed */
2235 : 0, /* todo_flags_start */
2236 : 0, /* todo_flags_finish */
2237 : };
2238 :
2239 : class pass_musttail : public gimple_opt_pass
2240 : {
2241 : public:
2242 285722 : pass_musttail (gcc::context *ctxt)
2243 571444 : : gimple_opt_pass (pass_data_musttail, ctxt)
2244 : {}
2245 :
2246 : /* opt_pass methods: */
2247 : /* This pass is only used when the other tail call pass
2248 : doesn't run to make [[musttail]] still work. But only
2249 : run it when there is actually a musttail in the function. */
2250 1472150 : bool gate (function *f) final override
2251 : {
2252 1472150 : return f->has_musttail;
2253 : }
2254 235 : unsigned int execute (function *) final override
2255 : {
2256 235 : return tree_optimize_tail_calls_1 (true, true, true);
2257 : }
2258 :
2259 : }; // class pass_musttail
2260 :
2261 : } // anon namespace
2262 :
2263 : gimple_opt_pass *
2264 285722 : make_pass_musttail (gcc::context *ctxt)
2265 : {
2266 285722 : return new pass_musttail (ctxt);
2267 : }
|
