]>
Commit | Line | Data |
---|---|---|
ac534736 | 1 | /* Tail call optimization on trees. |
85ec4feb | 2 | Copyright (C) 2003-2018 Free Software Foundation, Inc. |
6de9cd9a DN |
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 | |
9dcd6f09 | 8 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
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 | |
9dcd6f09 NC |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
19 | |
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
c7131fb2 | 23 | #include "backend.h" |
957060b5 | 24 | #include "rtl.h" |
6de9cd9a | 25 | #include "tree.h" |
c7131fb2 | 26 | #include "gimple.h" |
957060b5 AM |
27 | #include "cfghooks.h" |
28 | #include "tree-pass.h" | |
c7131fb2 | 29 | #include "ssa.h" |
957060b5 AM |
30 | #include "cgraph.h" |
31 | #include "gimple-pretty-print.h" | |
40e23961 | 32 | #include "fold-const.h" |
d8a2d370 | 33 | #include "stor-layout.h" |
5be5c238 | 34 | #include "gimple-iterator.h" |
18f429e2 | 35 | #include "gimplify-me.h" |
442b4905 | 36 | #include "tree-cfg.h" |
442b4905 AM |
37 | #include "tree-into-ssa.h" |
38 | #include "tree-dfa.h" | |
6de9cd9a | 39 | #include "except.h" |
6fb5fa3c | 40 | #include "dbgcnt.h" |
0d5049b2 | 41 | #include "cfgloop.h" |
677f3fa8 | 42 | #include "common/common-target.h" |
fc11f321 | 43 | #include "ipa-utils.h" |
6de9cd9a DN |
44 | |
45 | /* The file implements the tail recursion elimination. It is also used to | |
1ea7e6ad | 46 | analyze the tail calls in general, passing the results to the rtl level |
6de9cd9a DN |
47 | where they are used for sibcall optimization. |
48 | ||
49 | In addition to the standard tail recursion elimination, we handle the most | |
50 | trivial cases of making the call tail recursive by creating accumulators. | |
51 | For example the following function | |
52 | ||
53 | int sum (int n) | |
54 | { | |
55 | if (n > 0) | |
56 | return n + sum (n - 1); | |
57 | else | |
58 | return 0; | |
59 | } | |
60 | ||
61 | is transformed into | |
62 | ||
63 | int sum (int n) | |
64 | { | |
65 | int acc = 0; | |
66 | ||
67 | while (n > 0) | |
68 | acc += n--; | |
69 | ||
70 | return acc; | |
71 | } | |
72 | ||
b8698a0f | 73 | To do this, we maintain two accumulators (a_acc and m_acc) that indicate |
6de9cd9a DN |
74 | when we reach the return x statement, we should return a_acc + x * m_acc |
75 | instead. They are initially initialized to 0 and 1, respectively, | |
76 | so the semantics of the function is obviously preserved. If we are | |
77 | guaranteed that the value of the accumulator never change, we | |
78 | omit the accumulator. | |
79 | ||
80 | There are three cases how the function may exit. The first one is | |
6ce2bcb7 | 81 | handled in adjust_return_value, the other two in adjust_accumulator_values |
6de9cd9a DN |
82 | (the second case is actually a special case of the third one and we |
83 | present it separately just for clarity): | |
84 | ||
85 | 1) Just return x, where x is not in any of the remaining special shapes. | |
86 | We rewrite this to a gimple equivalent of return m_acc * x + a_acc. | |
b8698a0f | 87 | |
6de9cd9a | 88 | 2) return f (...), where f is the current function, is rewritten in a |
1ea7e6ad | 89 | classical tail-recursion elimination way, into assignment of arguments |
6de9cd9a DN |
90 | and jump to the start of the function. Values of the accumulators |
91 | are unchanged. | |
b8698a0f | 92 | |
6de9cd9a DN |
93 | 3) return a + m * f(...), where a and m do not depend on call to f. |
94 | To preserve the semantics described before we want this to be rewritten | |
95 | in such a way that we finally return | |
96 | ||
97 | a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...). | |
98 | ||
99 | I.e. we increase a_acc by a * m_acc, multiply m_acc by m and | |
100 | eliminate the tail call to f. Special cases when the value is just | |
101 | added or just multiplied are obtained by setting a = 0 or m = 1. | |
102 | ||
103 | TODO -- it is possible to do similar tricks for other operations. */ | |
104 | ||
105 | /* A structure that describes the tailcall. */ | |
106 | ||
107 | struct tailcall | |
108 | { | |
6de9cd9a | 109 | /* The iterator pointing to the call statement. */ |
726a989a | 110 | gimple_stmt_iterator call_gsi; |
6de9cd9a DN |
111 | |
112 | /* True if it is a call to the current function. */ | |
113 | bool tail_recursion; | |
114 | ||
115 | /* The return value of the caller is mult * f + add, where f is the return | |
116 | value of the call. */ | |
117 | tree mult, add; | |
118 | ||
119 | /* Next tailcall in the chain. */ | |
120 | struct tailcall *next; | |
121 | }; | |
122 | ||
123 | /* The variables holding the value of multiplicative and additive | |
124 | accumulator. */ | |
125 | static tree m_acc, a_acc; | |
126 | ||
6de9cd9a DN |
127 | static bool optimize_tail_call (struct tailcall *, bool); |
128 | static void eliminate_tail_call (struct tailcall *); | |
6de9cd9a DN |
129 | |
130 | /* Returns false when the function is not suitable for tail call optimization | |
131 | from some reason (e.g. if it takes variable number of arguments). */ | |
132 | ||
133 | static bool | |
134 | suitable_for_tail_opt_p (void) | |
135 | { | |
e3b5732b | 136 | if (cfun->stdarg) |
6de9cd9a DN |
137 | return false; |
138 | ||
6de9cd9a DN |
139 | return true; |
140 | } | |
141 | /* Returns false when the function is not suitable for tail call optimization | |
07cb4ee6 | 142 | for some reason (e.g. if it takes variable number of arguments). |
6de9cd9a DN |
143 | This test must pass in addition to suitable_for_tail_opt_p in order to make |
144 | tail call discovery happen. */ | |
145 | ||
146 | static bool | |
147 | suitable_for_tail_call_opt_p (void) | |
148 | { | |
ead553a1 SB |
149 | tree param; |
150 | ||
6de9cd9a DN |
151 | /* alloca (until we have stack slot life analysis) inhibits |
152 | sibling call optimizations, but not tail recursion. */ | |
e3b5732b | 153 | if (cfun->calls_alloca) |
6de9cd9a DN |
154 | return false; |
155 | ||
156 | /* If we are using sjlj exceptions, we may need to add a call to | |
157 | _Unwind_SjLj_Unregister at exit of the function. Which means | |
158 | that we cannot do any sibcall transformations. */ | |
677f3fa8 | 159 | if (targetm_common.except_unwind_info (&global_options) == UI_SJLJ |
f0a0390e | 160 | && current_function_has_exception_handlers ()) |
6de9cd9a DN |
161 | return false; |
162 | ||
163 | /* Any function that calls setjmp might have longjmp called from | |
164 | any called function. ??? We really should represent this | |
165 | properly in the CFG so that this needn't be special cased. */ | |
e3b5732b | 166 | if (cfun->calls_setjmp) |
6de9cd9a DN |
167 | return false; |
168 | ||
ead553a1 SB |
169 | /* ??? It is OK if the argument of a function is taken in some cases, |
170 | but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */ | |
171 | for (param = DECL_ARGUMENTS (current_function_decl); | |
172 | param; | |
910ad8de | 173 | param = DECL_CHAIN (param)) |
ead553a1 SB |
174 | if (TREE_ADDRESSABLE (param)) |
175 | return false; | |
176 | ||
6de9cd9a DN |
177 | return true; |
178 | } | |
179 | ||
180 | /* Checks whether the expression EXPR in stmt AT is independent of the | |
726a989a RB |
181 | statement pointed to by GSI (in a sense that we already know EXPR's value |
182 | at GSI). We use the fact that we are only called from the chain of | |
6de9cd9a | 183 | basic blocks that have only single successor. Returns the expression |
726a989a | 184 | containing the value of EXPR at GSI. */ |
6de9cd9a DN |
185 | |
186 | static tree | |
48932682 RB |
187 | independent_of_stmt_p (tree expr, gimple *at, gimple_stmt_iterator gsi, |
188 | bitmap to_move) | |
6de9cd9a DN |
189 | { |
190 | basic_block bb, call_bb, at_bb; | |
191 | edge e; | |
628f6a4e | 192 | edge_iterator ei; |
6de9cd9a DN |
193 | |
194 | if (is_gimple_min_invariant (expr)) | |
195 | return expr; | |
196 | ||
197 | if (TREE_CODE (expr) != SSA_NAME) | |
198 | return NULL_TREE; | |
199 | ||
48932682 RB |
200 | if (bitmap_bit_p (to_move, SSA_NAME_VERSION (expr))) |
201 | return expr; | |
202 | ||
6de9cd9a | 203 | /* Mark the blocks in the chain leading to the end. */ |
726a989a RB |
204 | at_bb = gimple_bb (at); |
205 | call_bb = gimple_bb (gsi_stmt (gsi)); | |
c5cbcccf | 206 | for (bb = call_bb; bb != at_bb; bb = single_succ (bb)) |
6de9cd9a DN |
207 | bb->aux = &bb->aux; |
208 | bb->aux = &bb->aux; | |
209 | ||
210 | while (1) | |
b8698a0f | 211 | { |
6de9cd9a | 212 | at = SSA_NAME_DEF_STMT (expr); |
726a989a | 213 | bb = gimple_bb (at); |
6de9cd9a | 214 | |
61ada8ae | 215 | /* The default definition or defined before the chain. */ |
6de9cd9a DN |
216 | if (!bb || !bb->aux) |
217 | break; | |
218 | ||
219 | if (bb == call_bb) | |
220 | { | |
726a989a RB |
221 | for (; !gsi_end_p (gsi); gsi_next (&gsi)) |
222 | if (gsi_stmt (gsi) == at) | |
6de9cd9a DN |
223 | break; |
224 | ||
726a989a | 225 | if (!gsi_end_p (gsi)) |
6de9cd9a DN |
226 | expr = NULL_TREE; |
227 | break; | |
228 | } | |
229 | ||
726a989a | 230 | if (gimple_code (at) != GIMPLE_PHI) |
6de9cd9a DN |
231 | { |
232 | expr = NULL_TREE; | |
233 | break; | |
234 | } | |
235 | ||
628f6a4e | 236 | FOR_EACH_EDGE (e, ei, bb->preds) |
6de9cd9a DN |
237 | if (e->src->aux) |
238 | break; | |
1e128c5f | 239 | gcc_assert (e); |
6de9cd9a | 240 | |
d00ad49b | 241 | expr = PHI_ARG_DEF_FROM_EDGE (at, e); |
066a0344 ZD |
242 | if (TREE_CODE (expr) != SSA_NAME) |
243 | { | |
244 | /* The value is a constant. */ | |
245 | break; | |
246 | } | |
6de9cd9a DN |
247 | } |
248 | ||
249 | /* Unmark the blocks. */ | |
c5cbcccf | 250 | for (bb = call_bb; bb != at_bb; bb = single_succ (bb)) |
6de9cd9a DN |
251 | bb->aux = NULL; |
252 | bb->aux = NULL; | |
253 | ||
254 | return expr; | |
255 | } | |
256 | ||
48932682 RB |
257 | enum par { FAIL, OK, TRY_MOVE }; |
258 | ||
726a989a RB |
259 | /* Simulates the effect of an assignment STMT on the return value of the tail |
260 | recursive CALL passed in ASS_VAR. M and A are the multiplicative and the | |
261 | additive factor for the real return value. */ | |
6de9cd9a | 262 | |
48932682 RB |
263 | static par |
264 | process_assignment (gassign *stmt, | |
265 | gimple_stmt_iterator call, tree *m, | |
266 | tree *a, tree *ass_var, bitmap to_move) | |
6de9cd9a | 267 | { |
68fce4ed | 268 | tree op0, op1 = NULL_TREE, non_ass_var = NULL_TREE; |
726a989a RB |
269 | tree dest = gimple_assign_lhs (stmt); |
270 | enum tree_code code = gimple_assign_rhs_code (stmt); | |
271 | enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code); | |
272 | tree src_var = gimple_assign_rhs1 (stmt); | |
b8698a0f | 273 | |
b89e96ac SB |
274 | /* See if this is a simple copy operation of an SSA name to the function |
275 | result. In that case we may have a simple tail call. Ignore type | |
276 | conversions that can never produce extra code between the function | |
277 | call and the function return. */ | |
726a989a | 278 | if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt)) |
9713daa0 | 279 | && src_var == *ass_var) |
6de9cd9a | 280 | { |
726a989a RB |
281 | /* Reject a tailcall if the type conversion might need |
282 | additional code. */ | |
62fb101e JJ |
283 | if (gimple_assign_cast_p (stmt)) |
284 | { | |
285 | if (TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var))) | |
48932682 | 286 | return FAIL; |
62fb101e JJ |
287 | |
288 | /* Even if the type modes are the same, if the precision of the | |
289 | type is smaller than mode's precision, | |
290 | reduce_to_bit_field_precision would generate additional code. */ | |
291 | if (INTEGRAL_TYPE_P (TREE_TYPE (dest)) | |
2be65d9e | 292 | && !type_has_mode_precision_p (TREE_TYPE (dest))) |
48932682 | 293 | return FAIL; |
62fb101e | 294 | } |
726a989a | 295 | |
6de9cd9a | 296 | *ass_var = dest; |
48932682 | 297 | return OK; |
6de9cd9a DN |
298 | } |
299 | ||
68fce4ed GS |
300 | switch (rhs_class) |
301 | { | |
302 | case GIMPLE_BINARY_RHS: | |
303 | op1 = gimple_assign_rhs2 (stmt); | |
304 | ||
305 | /* Fall through. */ | |
306 | ||
307 | case GIMPLE_UNARY_RHS: | |
308 | op0 = gimple_assign_rhs1 (stmt); | |
309 | break; | |
310 | ||
311 | default: | |
48932682 | 312 | return FAIL; |
68fce4ed | 313 | } |
6de9cd9a | 314 | |
85d62520 RS |
315 | /* Accumulator optimizations will reverse the order of operations. |
316 | We can only do that for floating-point types if we're assuming | |
317 | that addition and multiplication are associative. */ | |
a1a82611 | 318 | if (!flag_associative_math) |
85d62520 | 319 | if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl)))) |
48932682 | 320 | return FAIL; |
85d62520 | 321 | |
48932682 RB |
322 | if (rhs_class == GIMPLE_UNARY_RHS |
323 | && op0 == *ass_var) | |
68fce4ed GS |
324 | ; |
325 | else if (op0 == *ass_var | |
48932682 RB |
326 | && (non_ass_var = independent_of_stmt_p (op1, stmt, call, |
327 | to_move))) | |
6de9cd9a DN |
328 | ; |
329 | else if (op1 == *ass_var | |
48932682 RB |
330 | && (non_ass_var = independent_of_stmt_p (op0, stmt, call, |
331 | to_move))) | |
6de9cd9a DN |
332 | ; |
333 | else | |
48932682 | 334 | return TRY_MOVE; |
6de9cd9a | 335 | |
b89e96ac | 336 | switch (code) |
6de9cd9a DN |
337 | { |
338 | case PLUS_EXPR: | |
6de9cd9a DN |
339 | *a = non_ass_var; |
340 | *ass_var = dest; | |
48932682 | 341 | return OK; |
6de9cd9a | 342 | |
6b00d7dd JJ |
343 | case POINTER_PLUS_EXPR: |
344 | if (op0 != *ass_var) | |
48932682 | 345 | return FAIL; |
6b00d7dd JJ |
346 | *a = non_ass_var; |
347 | *ass_var = dest; | |
48932682 | 348 | return OK; |
6b00d7dd | 349 | |
6de9cd9a | 350 | case MULT_EXPR: |
6de9cd9a DN |
351 | *m = non_ass_var; |
352 | *ass_var = dest; | |
48932682 | 353 | return OK; |
6de9cd9a | 354 | |
68fce4ed | 355 | case NEGATE_EXPR: |
4e115102 | 356 | *m = build_minus_one_cst (TREE_TYPE (op0)); |
68fce4ed | 357 | *ass_var = dest; |
48932682 | 358 | return OK; |
68fce4ed GS |
359 | |
360 | case MINUS_EXPR: | |
361 | if (*ass_var == op0) | |
362 | *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var); | |
363 | else | |
364 | { | |
4e115102 | 365 | *m = build_minus_one_cst (TREE_TYPE (non_ass_var)); |
68fce4ed GS |
366 | *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var); |
367 | } | |
368 | ||
369 | *ass_var = dest; | |
48932682 | 370 | return OK; |
6de9cd9a DN |
371 | |
372 | default: | |
48932682 | 373 | return FAIL; |
6de9cd9a DN |
374 | } |
375 | } | |
376 | ||
377 | /* Propagate VAR through phis on edge E. */ | |
378 | ||
379 | static tree | |
380 | propagate_through_phis (tree var, edge e) | |
381 | { | |
382 | basic_block dest = e->dest; | |
538dd0b7 | 383 | gphi_iterator gsi; |
b8698a0f | 384 | |
726a989a RB |
385 | for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi)) |
386 | { | |
538dd0b7 | 387 | gphi *phi = gsi.phi (); |
726a989a RB |
388 | if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var) |
389 | return PHI_RESULT (phi); | |
390 | } | |
6de9cd9a DN |
391 | return var; |
392 | } | |
393 | ||
394 | /* Finds tailcalls falling into basic block BB. The list of found tailcalls is | |
395 | added to the start of RET. */ | |
396 | ||
397 | static void | |
398 | find_tail_calls (basic_block bb, struct tailcall **ret) | |
399 | { | |
726a989a | 400 | tree ass_var = NULL_TREE, ret_var, func, param; |
355fe088 | 401 | gimple *stmt; |
538dd0b7 | 402 | gcall *call = NULL; |
726a989a | 403 | gimple_stmt_iterator gsi, agsi; |
6de9cd9a DN |
404 | bool tail_recursion; |
405 | struct tailcall *nw; | |
406 | edge e; | |
407 | tree m, a; | |
408 | basic_block abb; | |
726a989a | 409 | size_t idx; |
12de6355 | 410 | tree var; |
6de9cd9a | 411 | |
c5cbcccf | 412 | if (!single_succ_p (bb)) |
6de9cd9a DN |
413 | return; |
414 | ||
726a989a | 415 | for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) |
6de9cd9a | 416 | { |
726a989a | 417 | stmt = gsi_stmt (gsi); |
6de9cd9a | 418 | |
5c246896 | 419 | /* Ignore labels, returns, nops, clobbers and debug stmts. */ |
e106efc7 RG |
420 | if (gimple_code (stmt) == GIMPLE_LABEL |
421 | || gimple_code (stmt) == GIMPLE_RETURN | |
5c246896 | 422 | || gimple_code (stmt) == GIMPLE_NOP |
e59a1c22 | 423 | || gimple_code (stmt) == GIMPLE_PREDICT |
ca786352 | 424 | || gimple_clobber_p (stmt) |
e106efc7 | 425 | || is_gimple_debug (stmt)) |
6de9cd9a DN |
426 | continue; |
427 | ||
6de9cd9a | 428 | /* Check for a call. */ |
726a989a | 429 | if (is_gimple_call (stmt)) |
6de9cd9a | 430 | { |
538dd0b7 DM |
431 | call = as_a <gcall *> (stmt); |
432 | ass_var = gimple_call_lhs (call); | |
726a989a | 433 | break; |
6de9cd9a DN |
434 | } |
435 | ||
9713daa0 RS |
436 | /* Allow simple copies between local variables, even if they're |
437 | aggregates. */ | |
438 | if (is_gimple_assign (stmt) | |
439 | && auto_var_in_fn_p (gimple_assign_lhs (stmt), cfun->decl) | |
440 | && auto_var_in_fn_p (gimple_assign_rhs1 (stmt), cfun->decl)) | |
441 | continue; | |
442 | ||
5006671f RG |
443 | /* If the statement references memory or volatile operands, fail. */ |
444 | if (gimple_references_memory_p (stmt) | |
445 | || gimple_has_volatile_ops (stmt)) | |
6de9cd9a DN |
446 | return; |
447 | } | |
448 | ||
726a989a | 449 | if (gsi_end_p (gsi)) |
6de9cd9a | 450 | { |
628f6a4e | 451 | edge_iterator ei; |
6de9cd9a | 452 | /* Recurse to the predecessors. */ |
628f6a4e | 453 | FOR_EACH_EDGE (e, ei, bb->preds) |
6de9cd9a DN |
454 | find_tail_calls (e->src, ret); |
455 | ||
456 | return; | |
457 | } | |
458 | ||
9713daa0 RS |
459 | /* If the LHS of our call is not just a simple register or local |
460 | variable, we can't transform this into a tail or sibling call. | |
461 | This situation happens, in (e.g.) "*p = foo()" where foo returns a | |
462 | struct. In this case we won't have a temporary here, but we need | |
463 | to carry out the side effect anyway, so tailcall is impossible. | |
bd42a56b MM |
464 | |
465 | ??? In some situations (when the struct is returned in memory via | |
466 | invisible argument) we could deal with this, e.g. by passing 'p' | |
467 | itself as that argument to foo, but it's too early to do this here, | |
468 | and expand_call() will not handle it anyway. If it ever can, then | |
469 | we need to revisit this here, to allow that situation. */ | |
9713daa0 RS |
470 | if (ass_var |
471 | && !is_gimple_reg (ass_var) | |
472 | && !auto_var_in_fn_p (ass_var, cfun->decl)) | |
bd42a56b MM |
473 | return; |
474 | ||
6de9cd9a DN |
475 | /* We found the call, check whether it is suitable. */ |
476 | tail_recursion = false; | |
726a989a | 477 | func = gimple_call_fndecl (call); |
16022041 | 478 | if (func |
3d78e008 | 479 | && !fndecl_built_in_p (func) |
16022041 | 480 | && recursive_call_p (current_function_decl, func)) |
6de9cd9a | 481 | { |
12de6355 | 482 | tree arg; |
d086d311 | 483 | |
686faaec | 484 | for (param = DECL_ARGUMENTS (current_function_decl), idx = 0; |
726a989a | 485 | param && idx < gimple_call_num_args (call); |
910ad8de | 486 | param = DECL_CHAIN (param), idx ++) |
6de9cd9a | 487 | { |
726a989a | 488 | arg = gimple_call_arg (call, idx); |
14de86fa ZD |
489 | if (param != arg) |
490 | { | |
491 | /* Make sure there are no problems with copying. The parameter | |
6de9cd9a DN |
492 | have a copyable type and the two arguments must have reasonably |
493 | equivalent types. The latter requirement could be relaxed if | |
494 | we emitted a suitable type conversion statement. */ | |
14de86fa | 495 | if (!is_gimple_reg_type (TREE_TYPE (param)) |
f4088621 | 496 | || !useless_type_conversion_p (TREE_TYPE (param), |
726a989a | 497 | TREE_TYPE (arg))) |
14de86fa ZD |
498 | break; |
499 | ||
500 | /* The parameter should be a real operand, so that phi node | |
501 | created for it at the start of the function has the meaning | |
502 | of copying the value. This test implies is_gimple_reg_type | |
503 | from the previous condition, however this one could be | |
504 | relaxed by being more careful with copying the new value | |
726a989a | 505 | of the parameter (emitting appropriate GIMPLE_ASSIGN and |
14de86fa ZD |
506 | updating the virtual operands). */ |
507 | if (!is_gimple_reg (param)) | |
508 | break; | |
509 | } | |
6de9cd9a | 510 | } |
726a989a | 511 | if (idx == gimple_call_num_args (call) && !param) |
6de9cd9a | 512 | tail_recursion = true; |
12de6355 | 513 | } |
d086d311 | 514 | |
2c28c3e4 RS |
515 | /* Make sure the tail invocation of this function does not indirectly |
516 | refer to local variables. (Passing variables directly by value | |
517 | is OK.) */ | |
824f71b9 | 518 | FOR_EACH_LOCAL_DECL (cfun, idx, var) |
12de6355 | 519 | { |
4e708ff7 RG |
520 | if (TREE_CODE (var) != PARM_DECL |
521 | && auto_var_in_fn_p (var, cfun->decl) | |
2c28c3e4 | 522 | && may_be_aliased (var) |
52c307ba RG |
523 | && (ref_maybe_used_by_stmt_p (call, var) |
524 | || call_may_clobber_ref_p (call, var))) | |
12de6355 | 525 | return; |
6de9cd9a DN |
526 | } |
527 | ||
528 | /* Now check the statements after the call. None of them has virtual | |
529 | operands, so they may only depend on the call through its return | |
530 | value. The return value should also be dependent on each of them, | |
531 | since we are running after dce. */ | |
532 | m = NULL_TREE; | |
533 | a = NULL_TREE; | |
bd53b257 RB |
534 | auto_bitmap to_move_defs; |
535 | auto_vec<gimple *> to_move_stmts; | |
6de9cd9a DN |
536 | |
537 | abb = bb; | |
726a989a | 538 | agsi = gsi; |
6de9cd9a DN |
539 | while (1) |
540 | { | |
d9334061 GS |
541 | tree tmp_a = NULL_TREE; |
542 | tree tmp_m = NULL_TREE; | |
726a989a | 543 | gsi_next (&agsi); |
6de9cd9a | 544 | |
726a989a | 545 | while (gsi_end_p (agsi)) |
6de9cd9a | 546 | { |
c5cbcccf ZD |
547 | ass_var = propagate_through_phis (ass_var, single_succ_edge (abb)); |
548 | abb = single_succ (abb); | |
726a989a | 549 | agsi = gsi_start_bb (abb); |
6de9cd9a DN |
550 | } |
551 | ||
726a989a | 552 | stmt = gsi_stmt (agsi); |
726a989a | 553 | if (gimple_code (stmt) == GIMPLE_RETURN) |
6de9cd9a DN |
554 | break; |
555 | ||
48932682 RB |
556 | if (gimple_code (stmt) == GIMPLE_LABEL |
557 | || gimple_code (stmt) == GIMPLE_NOP | |
e59a1c22 | 558 | || gimple_code (stmt) == GIMPLE_PREDICT |
48932682 RB |
559 | || gimple_clobber_p (stmt) |
560 | || is_gimple_debug (stmt)) | |
b5b8b0ac AO |
561 | continue; |
562 | ||
726a989a | 563 | if (gimple_code (stmt) != GIMPLE_ASSIGN) |
6de9cd9a DN |
564 | return; |
565 | ||
726a989a | 566 | /* This is a gimple assign. */ |
48932682 | 567 | par ret = process_assignment (as_a <gassign *> (stmt), gsi, |
bd53b257 | 568 | &tmp_m, &tmp_a, &ass_var, to_move_defs); |
48932682 | 569 | if (ret == FAIL) |
6de9cd9a | 570 | return; |
48932682 RB |
571 | else if (ret == TRY_MOVE) |
572 | { | |
573 | if (! tail_recursion) | |
574 | return; | |
75f0112f RB |
575 | /* Do not deal with checking dominance, the real fix is to |
576 | do path isolation for the transform phase anyway, removing | |
577 | the need to compute the accumulators with new stmts. */ | |
578 | if (abb != bb) | |
579 | return; | |
48932682 RB |
580 | for (unsigned opno = 1; opno < gimple_num_ops (stmt); ++opno) |
581 | { | |
582 | tree op = gimple_op (stmt, opno); | |
bd53b257 | 583 | if (independent_of_stmt_p (op, stmt, gsi, to_move_defs) != op) |
48932682 RB |
584 | return; |
585 | } | |
bd53b257 RB |
586 | bitmap_set_bit (to_move_defs, |
587 | SSA_NAME_VERSION (gimple_assign_lhs (stmt))); | |
588 | to_move_stmts.safe_push (stmt); | |
48932682 RB |
589 | continue; |
590 | } | |
d9334061 GS |
591 | |
592 | if (tmp_a) | |
593 | { | |
fdb8b4c0 | 594 | tree type = TREE_TYPE (tmp_a); |
d9334061 | 595 | if (a) |
fdb8b4c0 | 596 | a = fold_build2 (PLUS_EXPR, type, fold_convert (type, a), tmp_a); |
d9334061 GS |
597 | else |
598 | a = tmp_a; | |
599 | } | |
600 | if (tmp_m) | |
601 | { | |
fdb8b4c0 | 602 | tree type = TREE_TYPE (tmp_m); |
d9334061 | 603 | if (m) |
fdb8b4c0 | 604 | m = fold_build2 (MULT_EXPR, type, fold_convert (type, m), tmp_m); |
d9334061 GS |
605 | else |
606 | m = tmp_m; | |
607 | ||
608 | if (a) | |
fdb8b4c0 | 609 | a = fold_build2 (MULT_EXPR, type, fold_convert (type, a), tmp_m); |
d9334061 | 610 | } |
6de9cd9a DN |
611 | } |
612 | ||
b89e96ac | 613 | /* See if this is a tail call we can handle. */ |
538dd0b7 | 614 | ret_var = gimple_return_retval (as_a <greturn *> (stmt)); |
6de9cd9a DN |
615 | |
616 | /* We may proceed if there either is no return value, or the return value | |
617 | is identical to the call's return. */ | |
618 | if (ret_var | |
619 | && (ret_var != ass_var)) | |
620 | return; | |
621 | ||
4b5b9613 RH |
622 | /* If this is not a tail recursive call, we cannot handle addends or |
623 | multiplicands. */ | |
624 | if (!tail_recursion && (m || a)) | |
625 | return; | |
626 | ||
6b00d7dd JJ |
627 | /* For pointers only allow additions. */ |
628 | if (m && POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl)))) | |
629 | return; | |
630 | ||
48932682 RB |
631 | /* Move queued defs. */ |
632 | if (tail_recursion) | |
633 | { | |
48932682 | 634 | unsigned i; |
bd53b257 | 635 | FOR_EACH_VEC_ELT (to_move_stmts, i, stmt) |
48932682 | 636 | { |
48932682 RB |
637 | gimple_stmt_iterator mgsi = gsi_for_stmt (stmt); |
638 | gsi_move_before (&mgsi, &gsi); | |
639 | } | |
640 | } | |
641 | ||
e1111e8e | 642 | nw = XNEW (struct tailcall); |
6de9cd9a | 643 | |
726a989a | 644 | nw->call_gsi = gsi; |
6de9cd9a DN |
645 | |
646 | nw->tail_recursion = tail_recursion; | |
647 | ||
648 | nw->mult = m; | |
649 | nw->add = a; | |
650 | ||
651 | nw->next = *ret; | |
652 | *ret = nw; | |
653 | } | |
654 | ||
726a989a | 655 | /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */ |
6de9cd9a DN |
656 | |
657 | static void | |
726a989a RB |
658 | add_successor_phi_arg (edge e, tree var, tree phi_arg) |
659 | { | |
538dd0b7 | 660 | gphi_iterator gsi; |
726a989a RB |
661 | |
662 | for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) | |
538dd0b7 | 663 | if (PHI_RESULT (gsi.phi ()) == var) |
726a989a RB |
664 | break; |
665 | ||
666 | gcc_assert (!gsi_end_p (gsi)); | |
538dd0b7 | 667 | add_phi_arg (gsi.phi (), phi_arg, e, UNKNOWN_LOCATION); |
726a989a RB |
668 | } |
669 | ||
670 | /* Creates a GIMPLE statement which computes the operation specified by | |
c1781047 JJ |
671 | CODE, ACC and OP1 to a new variable with name LABEL and inserts the |
672 | statement in the position specified by GSI. Returns the | |
726a989a RB |
673 | tree node of the statement's result. */ |
674 | ||
675 | static tree | |
b8698a0f | 676 | adjust_return_value_with_ops (enum tree_code code, const char *label, |
9efc83f4 | 677 | tree acc, tree op1, gimple_stmt_iterator gsi) |
6de9cd9a | 678 | { |
726a989a | 679 | |
6de9cd9a | 680 | tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl)); |
83d5977e | 681 | tree result = make_temp_ssa_name (ret_type, NULL, label); |
538dd0b7 | 682 | gassign *stmt; |
726a989a | 683 | |
6b00d7dd JJ |
684 | if (POINTER_TYPE_P (ret_type)) |
685 | { | |
686 | gcc_assert (code == PLUS_EXPR && TREE_TYPE (acc) == sizetype); | |
687 | code = POINTER_PLUS_EXPR; | |
688 | } | |
689 | if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)) | |
690 | && code != POINTER_PLUS_EXPR) | |
0d0e4a03 | 691 | stmt = gimple_build_assign (result, code, acc, op1); |
9efc83f4 RG |
692 | else |
693 | { | |
6b00d7dd JJ |
694 | tree tem; |
695 | if (code == POINTER_PLUS_EXPR) | |
696 | tem = fold_build2 (code, TREE_TYPE (op1), op1, acc); | |
697 | else | |
698 | tem = fold_build2 (code, TREE_TYPE (op1), | |
699 | fold_convert (TREE_TYPE (op1), acc), op1); | |
700 | tree rhs = fold_convert (ret_type, tem); | |
9efc83f4 | 701 | rhs = force_gimple_operand_gsi (&gsi, rhs, |
c1781047 | 702 | false, NULL, true, GSI_SAME_STMT); |
83d5977e | 703 | stmt = gimple_build_assign (result, rhs); |
9efc83f4 RG |
704 | } |
705 | ||
9efc83f4 | 706 | gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); |
726a989a RB |
707 | return result; |
708 | } | |
709 | ||
b8698a0f | 710 | /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by |
726a989a RB |
711 | the computation specified by CODE and OP1 and insert the statement |
712 | at the position specified by GSI as a new statement. Returns new SSA name | |
713 | of updated accumulator. */ | |
714 | ||
715 | static tree | |
716 | update_accumulator_with_ops (enum tree_code code, tree acc, tree op1, | |
717 | gimple_stmt_iterator gsi) | |
718 | { | |
538dd0b7 | 719 | gassign *stmt; |
b731b390 | 720 | tree var = copy_ssa_name (acc); |
9efc83f4 | 721 | if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1))) |
0d0e4a03 | 722 | stmt = gimple_build_assign (var, code, acc, op1); |
9efc83f4 RG |
723 | else |
724 | { | |
725 | tree rhs = fold_convert (TREE_TYPE (acc), | |
726 | fold_build2 (code, | |
727 | TREE_TYPE (op1), | |
728 | fold_convert (TREE_TYPE (op1), acc), | |
729 | op1)); | |
730 | rhs = force_gimple_operand_gsi (&gsi, rhs, | |
731 | false, NULL, false, GSI_CONTINUE_LINKING); | |
070ecdfd | 732 | stmt = gimple_build_assign (var, rhs); |
9efc83f4 | 733 | } |
726a989a RB |
734 | gsi_insert_after (&gsi, stmt, GSI_NEW_STMT); |
735 | return var; | |
736 | } | |
737 | ||
738 | /* Adjust the accumulator values according to A and M after GSI, and update | |
739 | the phi nodes on edge BACK. */ | |
740 | ||
741 | static void | |
742 | adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back) | |
743 | { | |
d9334061 GS |
744 | tree var, a_acc_arg, m_acc_arg; |
745 | ||
746 | if (m) | |
747 | m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT); | |
748 | if (a) | |
749 | a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT); | |
6de9cd9a | 750 | |
d9334061 GS |
751 | a_acc_arg = a_acc; |
752 | m_acc_arg = m_acc; | |
6de9cd9a DN |
753 | if (a) |
754 | { | |
755 | if (m_acc) | |
756 | { | |
757 | if (integer_onep (a)) | |
758 | var = m_acc; | |
759 | else | |
726a989a | 760 | var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc, |
9efc83f4 | 761 | a, gsi); |
6de9cd9a DN |
762 | } |
763 | else | |
764 | var = a; | |
765 | ||
726a989a | 766 | a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi); |
6de9cd9a DN |
767 | } |
768 | ||
769 | if (m) | |
726a989a | 770 | m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi); |
6de9cd9a DN |
771 | |
772 | if (a_acc) | |
726a989a | 773 | add_successor_phi_arg (back, a_acc, a_acc_arg); |
6de9cd9a DN |
774 | |
775 | if (m_acc) | |
726a989a | 776 | add_successor_phi_arg (back, m_acc, m_acc_arg); |
6de9cd9a DN |
777 | } |
778 | ||
1ea7e6ad | 779 | /* Adjust value of the return at the end of BB according to M and A |
6de9cd9a DN |
780 | accumulators. */ |
781 | ||
782 | static void | |
783 | adjust_return_value (basic_block bb, tree m, tree a) | |
784 | { | |
726a989a | 785 | tree retval; |
538dd0b7 | 786 | greturn *ret_stmt = as_a <greturn *> (gimple_seq_last_stmt (bb_seq (bb))); |
726a989a | 787 | gimple_stmt_iterator gsi = gsi_last_bb (bb); |
6de9cd9a | 788 | |
726a989a | 789 | gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN); |
6de9cd9a | 790 | |
726a989a RB |
791 | retval = gimple_return_retval (ret_stmt); |
792 | if (!retval || retval == error_mark_node) | |
6de9cd9a DN |
793 | return; |
794 | ||
6de9cd9a | 795 | if (m) |
726a989a | 796 | retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval, |
9efc83f4 | 797 | gsi); |
6de9cd9a | 798 | if (a) |
726a989a | 799 | retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval, |
9efc83f4 | 800 | gsi); |
726a989a | 801 | gimple_return_set_retval (ret_stmt, retval); |
f430bae8 | 802 | update_stmt (ret_stmt); |
6de9cd9a DN |
803 | } |
804 | ||
23504559 JH |
805 | /* Subtract COUNT and FREQUENCY from the basic block and it's |
806 | outgoing edge. */ | |
807 | static void | |
e7a74006 | 808 | decrease_profile (basic_block bb, profile_count count) |
23504559 | 809 | { |
3995f3a2 | 810 | bb->count = bb->count - count; |
23504559 JH |
811 | if (!single_succ_p (bb)) |
812 | { | |
813 | gcc_assert (!EDGE_COUNT (bb->succs)); | |
814 | return; | |
815 | } | |
23504559 JH |
816 | } |
817 | ||
016925bc ZD |
818 | /* Returns true if argument PARAM of the tail recursive call needs to be copied |
819 | when the call is eliminated. */ | |
820 | ||
821 | static bool | |
822 | arg_needs_copy_p (tree param) | |
823 | { | |
824 | tree def; | |
825 | ||
5f564b8f | 826 | if (!is_gimple_reg (param)) |
016925bc | 827 | return false; |
b8698a0f | 828 | |
016925bc | 829 | /* Parameters that are only defined but never used need not be copied. */ |
32244553 | 830 | def = ssa_default_def (cfun, param); |
016925bc ZD |
831 | if (!def) |
832 | return false; | |
833 | ||
834 | return true; | |
835 | } | |
836 | ||
6de9cd9a DN |
837 | /* Eliminates tail call described by T. TMP_VARS is a list of |
838 | temporary variables used to copy the function arguments. */ | |
839 | ||
840 | static void | |
841 | eliminate_tail_call (struct tailcall *t) | |
842 | { | |
726a989a | 843 | tree param, rslt; |
355fe088 | 844 | gimple *stmt, *call; |
5039610b | 845 | tree arg; |
726a989a | 846 | size_t idx; |
6de9cd9a DN |
847 | basic_block bb, first; |
848 | edge e; | |
538dd0b7 DM |
849 | gphi *phi; |
850 | gphi_iterator gpi; | |
726a989a | 851 | gimple_stmt_iterator gsi; |
355fe088 | 852 | gimple *orig_stmt; |
6de9cd9a | 853 | |
726a989a RB |
854 | stmt = orig_stmt = gsi_stmt (t->call_gsi); |
855 | bb = gsi_bb (t->call_gsi); | |
6de9cd9a DN |
856 | |
857 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
858 | { | |
859 | fprintf (dump_file, "Eliminated tail recursion in bb %d : ", | |
860 | bb->index); | |
726a989a | 861 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
6de9cd9a DN |
862 | fprintf (dump_file, "\n"); |
863 | } | |
864 | ||
726a989a | 865 | gcc_assert (is_gimple_call (stmt)); |
6de9cd9a | 866 | |
fefa31b5 | 867 | first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)); |
6de9cd9a | 868 | |
726a989a | 869 | /* Remove the code after call_gsi that will become unreachable. The |
8d3d51b5 ZD |
870 | possibly unreachable code in other blocks is removed later in |
871 | cfg cleanup. */ | |
726a989a | 872 | gsi = t->call_gsi; |
d5c1a5f1 RB |
873 | gimple_stmt_iterator gsi2 = gsi_last_bb (gimple_bb (gsi_stmt (gsi))); |
874 | while (gsi_stmt (gsi2) != gsi_stmt (gsi)) | |
8d3d51b5 | 875 | { |
d5c1a5f1 | 876 | gimple *t = gsi_stmt (gsi2); |
8d3d51b5 ZD |
877 | /* Do not remove the return statement, so that redirect_edge_and_branch |
878 | sees how the block ends. */ | |
d5c1a5f1 RB |
879 | if (gimple_code (t) != GIMPLE_RETURN) |
880 | { | |
881 | gimple_stmt_iterator gsi3 = gsi2; | |
882 | gsi_prev (&gsi2); | |
883 | gsi_remove (&gsi3, true); | |
884 | release_defs (t); | |
885 | } | |
886 | else | |
887 | gsi_prev (&gsi2); | |
8d3d51b5 ZD |
888 | } |
889 | ||
23504559 | 890 | /* Number of executions of function has reduced by the tailcall. */ |
726a989a | 891 | e = single_succ_edge (gsi_bb (t->call_gsi)); |
db16c184 JH |
892 | |
893 | profile_count count = e->count (); | |
894 | ||
895 | /* When profile is inconsistent and the recursion edge is more frequent | |
896 | than number of executions of functions, scale it down, so we do not end | |
897 | up with 0 executions of entry block. */ | |
898 | if (count >= ENTRY_BLOCK_PTR_FOR_FN (cfun)->count) | |
899 | count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.apply_scale (7, 8); | |
900 | decrease_profile (EXIT_BLOCK_PTR_FOR_FN (cfun), count); | |
901 | decrease_profile (ENTRY_BLOCK_PTR_FOR_FN (cfun), count); | |
fefa31b5 | 902 | if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) |
db16c184 | 903 | decrease_profile (e->dest, count); |
23504559 | 904 | |
6de9cd9a | 905 | /* Replace the call by a jump to the start of function. */ |
726a989a RB |
906 | e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)), |
907 | first); | |
1e128c5f | 908 | gcc_assert (e); |
726a989a | 909 | PENDING_STMT (e) = NULL; |
6de9cd9a | 910 | |
016925bc ZD |
911 | /* Add phi node entries for arguments. The ordering of the phi nodes should |
912 | be the same as the ordering of the arguments. */ | |
6de9cd9a | 913 | for (param = DECL_ARGUMENTS (current_function_decl), |
538dd0b7 | 914 | idx = 0, gpi = gsi_start_phis (first); |
6de9cd9a | 915 | param; |
910ad8de | 916 | param = DECL_CHAIN (param), idx++) |
6de9cd9a | 917 | { |
016925bc | 918 | if (!arg_needs_copy_p (param)) |
6de9cd9a | 919 | continue; |
726a989a RB |
920 | |
921 | arg = gimple_call_arg (stmt, idx); | |
538dd0b7 | 922 | phi = gpi.phi (); |
016925bc | 923 | gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi))); |
6de9cd9a | 924 | |
9e227d60 | 925 | add_phi_arg (phi, arg, e, gimple_location (stmt)); |
538dd0b7 | 926 | gsi_next (&gpi); |
6de9cd9a DN |
927 | } |
928 | ||
929 | /* Update the values of accumulators. */ | |
726a989a | 930 | adjust_accumulator_values (t->call_gsi, t->mult, t->add, e); |
6de9cd9a | 931 | |
726a989a RB |
932 | call = gsi_stmt (t->call_gsi); |
933 | rslt = gimple_call_lhs (call); | |
9713daa0 | 934 | if (rslt != NULL_TREE && TREE_CODE (rslt) == SSA_NAME) |
6de9cd9a | 935 | { |
6de9cd9a DN |
936 | /* Result of the call will no longer be defined. So adjust the |
937 | SSA_NAME_DEF_STMT accordingly. */ | |
726a989a | 938 | SSA_NAME_DEF_STMT (rslt) = gimple_build_nop (); |
6de9cd9a DN |
939 | } |
940 | ||
726a989a | 941 | gsi_remove (&t->call_gsi, true); |
87527e4b | 942 | release_defs (call); |
6de9cd9a DN |
943 | } |
944 | ||
945 | /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also | |
946 | mark the tailcalls for the sibcall optimization. */ | |
947 | ||
948 | static bool | |
949 | optimize_tail_call (struct tailcall *t, bool opt_tailcalls) | |
950 | { | |
951 | if (t->tail_recursion) | |
952 | { | |
953 | eliminate_tail_call (t); | |
954 | return true; | |
955 | } | |
956 | ||
957 | if (opt_tailcalls) | |
958 | { | |
538dd0b7 | 959 | gcall *stmt = as_a <gcall *> (gsi_stmt (t->call_gsi)); |
6de9cd9a | 960 | |
726a989a | 961 | gimple_call_set_tail (stmt, true); |
e2f0f5f7 | 962 | cfun->tail_call_marked = true; |
6de9cd9a DN |
963 | if (dump_file && (dump_flags & TDF_DETAILS)) |
964 | { | |
965 | fprintf (dump_file, "Found tail call "); | |
726a989a RB |
966 | print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
967 | fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index); | |
6de9cd9a DN |
968 | } |
969 | } | |
970 | ||
971 | return false; | |
972 | } | |
973 | ||
726a989a RB |
974 | /* Creates a tail-call accumulator of the same type as the return type of the |
975 | current function. LABEL is the name used to creating the temporary | |
976 | variable for the accumulator. The accumulator will be inserted in the | |
977 | phis of a basic block BB with single predecessor with an initial value | |
978 | INIT converted to the current function return type. */ | |
979 | ||
980 | static tree | |
981 | create_tailcall_accumulator (const char *label, basic_block bb, tree init) | |
982 | { | |
983 | tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl)); | |
6b00d7dd JJ |
984 | if (POINTER_TYPE_P (ret_type)) |
985 | ret_type = sizetype; | |
986 | ||
83d5977e | 987 | tree tmp = make_temp_ssa_name (ret_type, NULL, label); |
538dd0b7 | 988 | gphi *phi; |
726a989a | 989 | |
726a989a RB |
990 | phi = create_phi_node (tmp, bb); |
991 | /* RET_TYPE can be a float when -ffast-maths is enabled. */ | |
f5045c96 | 992 | add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb), |
9e227d60 | 993 | UNKNOWN_LOCATION); |
726a989a RB |
994 | return PHI_RESULT (phi); |
995 | } | |
b8698a0f | 996 | |
6de9cd9a DN |
997 | /* Optimizes tail calls in the function, turning the tail recursion |
998 | into iteration. */ | |
999 | ||
1994bfea | 1000 | static unsigned int |
6de9cd9a DN |
1001 | tree_optimize_tail_calls_1 (bool opt_tailcalls) |
1002 | { | |
1003 | edge e; | |
1004 | bool phis_constructed = false; | |
1005 | struct tailcall *tailcalls = NULL, *act, *next; | |
1006 | bool changed = false; | |
fefa31b5 | 1007 | basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)); |
726a989a | 1008 | tree param; |
355fe088 | 1009 | gimple *stmt; |
628f6a4e | 1010 | edge_iterator ei; |
6de9cd9a DN |
1011 | |
1012 | if (!suitable_for_tail_opt_p ()) | |
1994bfea | 1013 | return 0; |
6de9cd9a DN |
1014 | if (opt_tailcalls) |
1015 | opt_tailcalls = suitable_for_tail_call_opt_p (); | |
1016 | ||
fefa31b5 | 1017 | FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds) |
6de9cd9a DN |
1018 | { |
1019 | /* Only traverse the normal exits, i.e. those that end with return | |
1020 | statement. */ | |
1021 | stmt = last_stmt (e->src); | |
1022 | ||
1023 | if (stmt | |
726a989a | 1024 | && gimple_code (stmt) == GIMPLE_RETURN) |
6de9cd9a DN |
1025 | find_tail_calls (e->src, &tailcalls); |
1026 | } | |
1027 | ||
1028 | /* Construct the phi nodes and accumulators if necessary. */ | |
1029 | a_acc = m_acc = NULL_TREE; | |
1030 | for (act = tailcalls; act; act = act->next) | |
1031 | { | |
1032 | if (!act->tail_recursion) | |
1033 | continue; | |
1034 | ||
1035 | if (!phis_constructed) | |
1036 | { | |
5006671f RG |
1037 | /* Ensure that there is only one predecessor of the block |
1038 | or if there are existing degenerate PHI nodes. */ | |
1039 | if (!single_pred_p (first) | |
1040 | || !gimple_seq_empty_p (phi_nodes (first))) | |
fefa31b5 DM |
1041 | first = |
1042 | split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))); | |
6de9cd9a DN |
1043 | |
1044 | /* Copy the args if needed. */ | |
1045 | for (param = DECL_ARGUMENTS (current_function_decl); | |
1046 | param; | |
910ad8de | 1047 | param = DECL_CHAIN (param)) |
016925bc ZD |
1048 | if (arg_needs_copy_p (param)) |
1049 | { | |
32244553 | 1050 | tree name = ssa_default_def (cfun, param); |
016925bc | 1051 | tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name)); |
538dd0b7 | 1052 | gphi *phi; |
016925bc | 1053 | |
32244553 | 1054 | set_ssa_default_def (cfun, param, new_name); |
016925bc | 1055 | phi = create_phi_node (name, first); |
b8698a0f | 1056 | add_phi_arg (phi, new_name, single_pred_edge (first), |
9e227d60 | 1057 | EXPR_LOCATION (param)); |
016925bc | 1058 | } |
6de9cd9a DN |
1059 | phis_constructed = true; |
1060 | } | |
1061 | ||
1062 | if (act->add && !a_acc) | |
726a989a RB |
1063 | a_acc = create_tailcall_accumulator ("add_acc", first, |
1064 | integer_zero_node); | |
6de9cd9a DN |
1065 | |
1066 | if (act->mult && !m_acc) | |
726a989a RB |
1067 | m_acc = create_tailcall_accumulator ("mult_acc", first, |
1068 | integer_one_node); | |
016925bc ZD |
1069 | } |
1070 | ||
1400c8e5 ZD |
1071 | if (a_acc || m_acc) |
1072 | { | |
1073 | /* When the tail call elimination using accumulators is performed, | |
1074 | statements adding the accumulated value are inserted at all exits. | |
1075 | This turns all other tail calls to non-tail ones. */ | |
1076 | opt_tailcalls = false; | |
1077 | } | |
1078 | ||
6de9cd9a DN |
1079 | for (; tailcalls; tailcalls = next) |
1080 | { | |
1081 | next = tailcalls->next; | |
1082 | changed |= optimize_tail_call (tailcalls, opt_tailcalls); | |
1083 | free (tailcalls); | |
1084 | } | |
1085 | ||
1086 | if (a_acc || m_acc) | |
1087 | { | |
1088 | /* Modify the remaining return statements. */ | |
fefa31b5 | 1089 | FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds) |
6de9cd9a DN |
1090 | { |
1091 | stmt = last_stmt (e->src); | |
1092 | ||
1093 | if (stmt | |
726a989a | 1094 | && gimple_code (stmt) == GIMPLE_RETURN) |
6de9cd9a DN |
1095 | adjust_return_value (e->src, m_acc, a_acc); |
1096 | } | |
1097 | } | |
1098 | ||
1099 | if (changed) | |
0d5049b2 RB |
1100 | { |
1101 | /* We may have created new loops. Make them magically appear. */ | |
726338f4 | 1102 | loops_state_set (LOOPS_NEED_FIXUP); |
0d5049b2 RB |
1103 | free_dominance_info (CDI_DOMINATORS); |
1104 | } | |
016925bc | 1105 | |
824f71b9 RG |
1106 | /* Add phi nodes for the virtual operands defined in the function to the |
1107 | header of the loop created by tail recursion elimination. Do so | |
1108 | by triggering the SSA renamer. */ | |
016925bc | 1109 | if (phis_constructed) |
525174a2 | 1110 | mark_virtual_operands_for_renaming (cfun); |
824f71b9 | 1111 | |
1994bfea JH |
1112 | if (changed) |
1113 | return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals; | |
1114 | return 0; | |
6de9cd9a DN |
1115 | } |
1116 | ||
6de9cd9a DN |
1117 | static bool |
1118 | gate_tail_calls (void) | |
1119 | { | |
6fb5fa3c | 1120 | return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call); |
6de9cd9a DN |
1121 | } |
1122 | ||
c2924966 | 1123 | static unsigned int |
6de9cd9a DN |
1124 | execute_tail_calls (void) |
1125 | { | |
1994bfea | 1126 | return tree_optimize_tail_calls_1 (true); |
6de9cd9a DN |
1127 | } |
1128 | ||
17795822 TS |
1129 | namespace { |
1130 | ||
1131 | const pass_data pass_data_tail_recursion = | |
6de9cd9a | 1132 | { |
27a4cd48 DM |
1133 | GIMPLE_PASS, /* type */ |
1134 | "tailr", /* name */ | |
1135 | OPTGROUP_NONE, /* optinfo_flags */ | |
27a4cd48 DM |
1136 | TV_NONE, /* tv_id */ |
1137 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
1138 | 0, /* properties_provided */ | |
1139 | 0, /* properties_destroyed */ | |
1140 | 0, /* todo_flags_start */ | |
3bea341f | 1141 | 0, /* todo_flags_finish */ |
6de9cd9a DN |
1142 | }; |
1143 | ||
17795822 | 1144 | class pass_tail_recursion : public gimple_opt_pass |
27a4cd48 DM |
1145 | { |
1146 | public: | |
c3284718 RS |
1147 | pass_tail_recursion (gcc::context *ctxt) |
1148 | : gimple_opt_pass (pass_data_tail_recursion, ctxt) | |
27a4cd48 DM |
1149 | {} |
1150 | ||
1151 | /* opt_pass methods: */ | |
65d3284b | 1152 | opt_pass * clone () { return new pass_tail_recursion (m_ctxt); } |
1a3d085c | 1153 | virtual bool gate (function *) { return gate_tail_calls (); } |
be55bfe6 TS |
1154 | virtual unsigned int execute (function *) |
1155 | { | |
1156 | return tree_optimize_tail_calls_1 (false); | |
1157 | } | |
27a4cd48 DM |
1158 | |
1159 | }; // class pass_tail_recursion | |
1160 | ||
17795822 TS |
1161 | } // anon namespace |
1162 | ||
27a4cd48 DM |
1163 | gimple_opt_pass * |
1164 | make_pass_tail_recursion (gcc::context *ctxt) | |
1165 | { | |
1166 | return new pass_tail_recursion (ctxt); | |
1167 | } | |
1168 | ||
17795822 TS |
1169 | namespace { |
1170 | ||
1171 | const pass_data pass_data_tail_calls = | |
6de9cd9a | 1172 | { |
27a4cd48 DM |
1173 | GIMPLE_PASS, /* type */ |
1174 | "tailc", /* name */ | |
1175 | OPTGROUP_NONE, /* optinfo_flags */ | |
27a4cd48 DM |
1176 | TV_NONE, /* tv_id */ |
1177 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
1178 | 0, /* properties_provided */ | |
1179 | 0, /* properties_destroyed */ | |
1180 | 0, /* todo_flags_start */ | |
3bea341f | 1181 | 0, /* todo_flags_finish */ |
6de9cd9a | 1182 | }; |
27a4cd48 | 1183 | |
17795822 | 1184 | class pass_tail_calls : public gimple_opt_pass |
27a4cd48 DM |
1185 | { |
1186 | public: | |
c3284718 RS |
1187 | pass_tail_calls (gcc::context *ctxt) |
1188 | : gimple_opt_pass (pass_data_tail_calls, ctxt) | |
27a4cd48 DM |
1189 | {} |
1190 | ||
1191 | /* opt_pass methods: */ | |
1a3d085c | 1192 | virtual bool gate (function *) { return gate_tail_calls (); } |
be55bfe6 | 1193 | virtual unsigned int execute (function *) { return execute_tail_calls (); } |
27a4cd48 DM |
1194 | |
1195 | }; // class pass_tail_calls | |
1196 | ||
17795822 TS |
1197 | } // anon namespace |
1198 | ||
27a4cd48 DM |
1199 | gimple_opt_pass * |
1200 | make_pass_tail_calls (gcc::context *ctxt) | |
1201 | { | |
1202 | return new pass_tail_calls (ctxt); | |
1203 | } |