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