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