]>
Commit | Line | Data |
---|---|---|
ac534736 | 1 | /* Tail call optimization on trees. |
ebb07520 | 2 | Copyright (C) 2003, 2004, 2005, 2006, 2007 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 | |
8 | the Free Software Foundation; either version 2, 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 COPYING. If not, write to | |
366ccddb KC |
18 | the Free Software Foundation, 51 Franklin Street, Fifth Floor, |
19 | Boston, MA 02110-1301, USA. */ | |
6de9cd9a DN |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "tree.h" | |
26 | #include "rtl.h" | |
27 | #include "tm_p.h" | |
28 | #include "hard-reg-set.h" | |
29 | #include "basic-block.h" | |
30 | #include "function.h" | |
31 | #include "tree-flow.h" | |
32 | #include "tree-dump.h" | |
33 | #include "diagnostic.h" | |
34 | #include "except.h" | |
35 | #include "tree-pass.h" | |
36 | #include "flags.h" | |
37 | #include "langhooks.h" | |
6fb5fa3c | 38 | #include "dbgcnt.h" |
6de9cd9a DN |
39 | |
40 | /* The file implements the tail recursion elimination. It is also used to | |
1ea7e6ad | 41 | analyze the tail calls in general, passing the results to the rtl level |
6de9cd9a DN |
42 | where they are used for sibcall optimization. |
43 | ||
44 | In addition to the standard tail recursion elimination, we handle the most | |
45 | trivial cases of making the call tail recursive by creating accumulators. | |
46 | For example the following function | |
47 | ||
48 | int sum (int n) | |
49 | { | |
50 | if (n > 0) | |
51 | return n + sum (n - 1); | |
52 | else | |
53 | return 0; | |
54 | } | |
55 | ||
56 | is transformed into | |
57 | ||
58 | int sum (int n) | |
59 | { | |
60 | int acc = 0; | |
61 | ||
62 | while (n > 0) | |
63 | acc += n--; | |
64 | ||
65 | return acc; | |
66 | } | |
67 | ||
68 | To do this, we maintain two accumulators (a_acc and m_acc) that indicate | |
69 | when we reach the return x statement, we should return a_acc + x * m_acc | |
70 | instead. They are initially initialized to 0 and 1, respectively, | |
71 | so the semantics of the function is obviously preserved. If we are | |
72 | guaranteed that the value of the accumulator never change, we | |
73 | omit the accumulator. | |
74 | ||
75 | There are three cases how the function may exit. The first one is | |
6ce2bcb7 | 76 | handled in adjust_return_value, the other two in adjust_accumulator_values |
6de9cd9a DN |
77 | (the second case is actually a special case of the third one and we |
78 | present it separately just for clarity): | |
79 | ||
80 | 1) Just return x, where x is not in any of the remaining special shapes. | |
81 | We rewrite this to a gimple equivalent of return m_acc * x + a_acc. | |
82 | ||
83 | 2) return f (...), where f is the current function, is rewritten in a | |
1ea7e6ad | 84 | classical tail-recursion elimination way, into assignment of arguments |
6de9cd9a DN |
85 | and jump to the start of the function. Values of the accumulators |
86 | are unchanged. | |
87 | ||
88 | 3) return a + m * f(...), where a and m do not depend on call to f. | |
89 | To preserve the semantics described before we want this to be rewritten | |
90 | in such a way that we finally return | |
91 | ||
92 | a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...). | |
93 | ||
94 | I.e. we increase a_acc by a * m_acc, multiply m_acc by m and | |
95 | eliminate the tail call to f. Special cases when the value is just | |
96 | added or just multiplied are obtained by setting a = 0 or m = 1. | |
97 | ||
98 | TODO -- it is possible to do similar tricks for other operations. */ | |
99 | ||
100 | /* A structure that describes the tailcall. */ | |
101 | ||
102 | struct tailcall | |
103 | { | |
104 | /* The block in that the call occur. */ | |
105 | basic_block call_block; | |
106 | ||
107 | /* The iterator pointing to the call statement. */ | |
108 | block_stmt_iterator call_bsi; | |
109 | ||
110 | /* True if it is a call to the current function. */ | |
111 | bool tail_recursion; | |
112 | ||
113 | /* The return value of the caller is mult * f + add, where f is the return | |
114 | value of the call. */ | |
115 | tree mult, add; | |
116 | ||
117 | /* Next tailcall in the chain. */ | |
118 | struct tailcall *next; | |
119 | }; | |
120 | ||
121 | /* The variables holding the value of multiplicative and additive | |
122 | accumulator. */ | |
123 | static tree m_acc, a_acc; | |
124 | ||
125 | static bool suitable_for_tail_opt_p (void); | |
126 | static bool optimize_tail_call (struct tailcall *, bool); | |
127 | static void eliminate_tail_call (struct tailcall *); | |
128 | static void find_tail_calls (basic_block, struct tailcall **); | |
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 | { | |
a3648cfc DB |
136 | referenced_var_iterator rvi; |
137 | tree var; | |
6de9cd9a DN |
138 | |
139 | if (current_function_stdarg) | |
140 | return false; | |
141 | ||
9044951e DB |
142 | /* No local variable nor structure field should be call-clobbered. We |
143 | ignore any kind of memory tag, as these are not real variables. */ | |
a3648cfc DB |
144 | |
145 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
6de9cd9a | 146 | { |
326eda4b DB |
147 | if (!is_global_var (var) |
148 | && (!MTAG_P (var) || TREE_CODE (var) == STRUCT_FIELD_TAG) | |
7faade0f JH |
149 | && (gimple_aliases_computed_p (cfun) ? is_call_clobbered (var) |
150 | : TREE_ADDRESSABLE (var))) | |
6de9cd9a DN |
151 | return false; |
152 | } | |
153 | ||
154 | return true; | |
155 | } | |
156 | /* Returns false when the function is not suitable for tail call optimization | |
157 | from some reason (e.g. if it takes variable number of arguments). | |
158 | This test must pass in addition to suitable_for_tail_opt_p in order to make | |
159 | tail call discovery happen. */ | |
160 | ||
161 | static bool | |
162 | suitable_for_tail_call_opt_p (void) | |
163 | { | |
ead553a1 SB |
164 | tree param; |
165 | ||
6de9cd9a DN |
166 | /* alloca (until we have stack slot life analysis) inhibits |
167 | sibling call optimizations, but not tail recursion. */ | |
168 | if (current_function_calls_alloca) | |
169 | return false; | |
170 | ||
171 | /* If we are using sjlj exceptions, we may need to add a call to | |
172 | _Unwind_SjLj_Unregister at exit of the function. Which means | |
173 | that we cannot do any sibcall transformations. */ | |
174 | if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ()) | |
175 | return false; | |
176 | ||
177 | /* Any function that calls setjmp might have longjmp called from | |
178 | any called function. ??? We really should represent this | |
179 | properly in the CFG so that this needn't be special cased. */ | |
180 | if (current_function_calls_setjmp) | |
181 | return false; | |
182 | ||
ead553a1 SB |
183 | /* ??? It is OK if the argument of a function is taken in some cases, |
184 | but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */ | |
185 | for (param = DECL_ARGUMENTS (current_function_decl); | |
186 | param; | |
187 | param = TREE_CHAIN (param)) | |
188 | if (TREE_ADDRESSABLE (param)) | |
189 | return false; | |
190 | ||
6de9cd9a DN |
191 | return true; |
192 | } | |
193 | ||
194 | /* Checks whether the expression EXPR in stmt AT is independent of the | |
206048bd | 195 | statement pointed to by BSI (in a sense that we already know EXPR's value |
6de9cd9a DN |
196 | at BSI). We use the fact that we are only called from the chain of |
197 | basic blocks that have only single successor. Returns the expression | |
198 | containing the value of EXPR at BSI. */ | |
199 | ||
200 | static tree | |
201 | independent_of_stmt_p (tree expr, tree at, block_stmt_iterator bsi) | |
202 | { | |
203 | basic_block bb, call_bb, at_bb; | |
204 | edge e; | |
628f6a4e | 205 | edge_iterator ei; |
6de9cd9a DN |
206 | |
207 | if (is_gimple_min_invariant (expr)) | |
208 | return expr; | |
209 | ||
210 | if (TREE_CODE (expr) != SSA_NAME) | |
211 | return NULL_TREE; | |
212 | ||
213 | /* Mark the blocks in the chain leading to the end. */ | |
214 | at_bb = bb_for_stmt (at); | |
215 | call_bb = bb_for_stmt (bsi_stmt (bsi)); | |
c5cbcccf | 216 | for (bb = call_bb; bb != at_bb; bb = single_succ (bb)) |
6de9cd9a DN |
217 | bb->aux = &bb->aux; |
218 | bb->aux = &bb->aux; | |
219 | ||
220 | while (1) | |
221 | { | |
222 | at = SSA_NAME_DEF_STMT (expr); | |
223 | bb = bb_for_stmt (at); | |
224 | ||
61ada8ae | 225 | /* The default definition or defined before the chain. */ |
6de9cd9a DN |
226 | if (!bb || !bb->aux) |
227 | break; | |
228 | ||
229 | if (bb == call_bb) | |
230 | { | |
231 | for (; !bsi_end_p (bsi); bsi_next (&bsi)) | |
232 | if (bsi_stmt (bsi) == at) | |
233 | break; | |
234 | ||
235 | if (!bsi_end_p (bsi)) | |
236 | expr = NULL_TREE; | |
237 | break; | |
238 | } | |
239 | ||
240 | if (TREE_CODE (at) != PHI_NODE) | |
241 | { | |
242 | expr = NULL_TREE; | |
243 | break; | |
244 | } | |
245 | ||
628f6a4e | 246 | FOR_EACH_EDGE (e, ei, bb->preds) |
6de9cd9a DN |
247 | if (e->src->aux) |
248 | break; | |
1e128c5f | 249 | gcc_assert (e); |
6de9cd9a | 250 | |
d00ad49b | 251 | expr = PHI_ARG_DEF_FROM_EDGE (at, e); |
066a0344 ZD |
252 | if (TREE_CODE (expr) != SSA_NAME) |
253 | { | |
254 | /* The value is a constant. */ | |
255 | break; | |
256 | } | |
6de9cd9a DN |
257 | } |
258 | ||
259 | /* Unmark the blocks. */ | |
c5cbcccf | 260 | for (bb = call_bb; bb != at_bb; bb = single_succ (bb)) |
6de9cd9a DN |
261 | bb->aux = NULL; |
262 | bb->aux = NULL; | |
263 | ||
264 | return expr; | |
265 | } | |
266 | ||
267 | /* Simulates the effect of an assignment of ASS in STMT on the return value | |
268 | of the tail recursive CALL passed in ASS_VAR. M and A are the | |
269 | multiplicative and the additive factor for the real return value. */ | |
270 | ||
271 | static bool | |
272 | process_assignment (tree ass, tree stmt, block_stmt_iterator call, tree *m, | |
273 | tree *a, tree *ass_var) | |
274 | { | |
275 | tree op0, op1, non_ass_var; | |
07beea0d AH |
276 | tree dest = GIMPLE_STMT_OPERAND (ass, 0); |
277 | tree src = GIMPLE_STMT_OPERAND (ass, 1); | |
6de9cd9a | 278 | enum tree_code code = TREE_CODE (src); |
b89e96ac SB |
279 | tree src_var = src; |
280 | ||
281 | /* See if this is a simple copy operation of an SSA name to the function | |
282 | result. In that case we may have a simple tail call. Ignore type | |
283 | conversions that can never produce extra code between the function | |
284 | call and the function return. */ | |
285 | STRIP_NOPS (src_var); | |
286 | if (TREE_CODE (src_var) == SSA_NAME) | |
6de9cd9a | 287 | { |
b89e96ac | 288 | if (src_var != *ass_var) |
6de9cd9a DN |
289 | return false; |
290 | ||
291 | *ass_var = dest; | |
292 | return true; | |
293 | } | |
294 | ||
6615c446 | 295 | if (TREE_CODE_CLASS (code) != tcc_binary) |
6de9cd9a DN |
296 | return false; |
297 | ||
85d62520 RS |
298 | /* Accumulator optimizations will reverse the order of operations. |
299 | We can only do that for floating-point types if we're assuming | |
300 | that addition and multiplication are associative. */ | |
301 | if (!flag_unsafe_math_optimizations) | |
302 | if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl)))) | |
303 | return false; | |
304 | ||
6de9cd9a DN |
305 | /* We only handle the code like |
306 | ||
307 | x = call (); | |
308 | y = m * x; | |
309 | z = y + a; | |
310 | return z; | |
311 | ||
312 | TODO -- Extend it for cases where the linear transformation of the output | |
313 | is expressed in a more complicated way. */ | |
314 | ||
315 | op0 = TREE_OPERAND (src, 0); | |
316 | op1 = TREE_OPERAND (src, 1); | |
317 | ||
318 | if (op0 == *ass_var | |
319 | && (non_ass_var = independent_of_stmt_p (op1, stmt, call))) | |
320 | ; | |
321 | else if (op1 == *ass_var | |
322 | && (non_ass_var = independent_of_stmt_p (op0, stmt, call))) | |
323 | ; | |
324 | else | |
325 | return false; | |
326 | ||
b89e96ac | 327 | switch (code) |
6de9cd9a DN |
328 | { |
329 | case PLUS_EXPR: | |
330 | /* There should be no previous addition. TODO -- it should be fairly | |
331 | straightforward to lift this restriction -- just allow storing | |
332 | more complicated expressions in *A, and gimplify it in | |
333 | adjust_accumulator_values. */ | |
334 | if (*a) | |
335 | return false; | |
336 | *a = non_ass_var; | |
337 | *ass_var = dest; | |
338 | return true; | |
339 | ||
340 | case MULT_EXPR: | |
341 | /* Similar remark applies here. Handling multiplication after addition | |
342 | is just slightly more complicated -- we need to multiply both *A and | |
343 | *M. */ | |
344 | if (*a || *m) | |
345 | return false; | |
346 | *m = non_ass_var; | |
347 | *ass_var = dest; | |
348 | return true; | |
349 | ||
5be014d5 | 350 | /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR, POINTER_PLUS_EXPR). */ |
6de9cd9a DN |
351 | |
352 | default: | |
353 | return false; | |
354 | } | |
355 | } | |
356 | ||
357 | /* Propagate VAR through phis on edge E. */ | |
358 | ||
359 | static tree | |
360 | propagate_through_phis (tree var, edge e) | |
361 | { | |
362 | basic_block dest = e->dest; | |
363 | tree phi; | |
364 | ||
17192884 | 365 | for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) |
d00ad49b | 366 | if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var) |
6de9cd9a DN |
367 | return PHI_RESULT (phi); |
368 | ||
369 | return var; | |
370 | } | |
371 | ||
372 | /* Finds tailcalls falling into basic block BB. The list of found tailcalls is | |
373 | added to the start of RET. */ | |
374 | ||
375 | static void | |
376 | find_tail_calls (basic_block bb, struct tailcall **ret) | |
377 | { | |
5039610b | 378 | tree ass_var, ret_var, stmt, func, param, call = NULL_TREE; |
6de9cd9a DN |
379 | block_stmt_iterator bsi, absi; |
380 | bool tail_recursion; | |
381 | struct tailcall *nw; | |
382 | edge e; | |
383 | tree m, a; | |
384 | basic_block abb; | |
385 | stmt_ann_t ann; | |
386 | ||
c5cbcccf | 387 | if (!single_succ_p (bb)) |
6de9cd9a DN |
388 | return; |
389 | ||
390 | for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) | |
391 | { | |
392 | stmt = bsi_stmt (bsi); | |
393 | ||
394 | /* Ignore labels. */ | |
395 | if (TREE_CODE (stmt) == LABEL_EXPR) | |
396 | continue; | |
397 | ||
6de9cd9a | 398 | /* Check for a call. */ |
07beea0d | 399 | if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) |
6de9cd9a | 400 | { |
07beea0d AH |
401 | ass_var = GIMPLE_STMT_OPERAND (stmt, 0); |
402 | call = GIMPLE_STMT_OPERAND (stmt, 1); | |
d25cee4d RH |
403 | if (TREE_CODE (call) == WITH_SIZE_EXPR) |
404 | call = TREE_OPERAND (call, 0); | |
6de9cd9a DN |
405 | } |
406 | else | |
407 | { | |
408 | ass_var = NULL_TREE; | |
409 | call = stmt; | |
410 | } | |
411 | ||
412 | if (TREE_CODE (call) == CALL_EXPR) | |
413 | break; | |
414 | ||
ba2e294d | 415 | /* If the statement has virtual or volatile operands, fail. */ |
6de9cd9a | 416 | ann = stmt_ann (stmt); |
f47c96aa | 417 | if (!ZERO_SSA_OPERANDS (stmt, (SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS)) |
ba2e294d | 418 | || ann->has_volatile_ops) |
6de9cd9a DN |
419 | return; |
420 | } | |
421 | ||
422 | if (bsi_end_p (bsi)) | |
423 | { | |
628f6a4e | 424 | edge_iterator ei; |
6de9cd9a | 425 | /* Recurse to the predecessors. */ |
628f6a4e | 426 | FOR_EACH_EDGE (e, ei, bb->preds) |
6de9cd9a DN |
427 | find_tail_calls (e->src, ret); |
428 | ||
429 | return; | |
430 | } | |
431 | ||
432 | /* We found the call, check whether it is suitable. */ | |
433 | tail_recursion = false; | |
434 | func = get_callee_fndecl (call); | |
435 | if (func == current_function_decl) | |
436 | { | |
5039610b SL |
437 | call_expr_arg_iterator iter; |
438 | tree arg; | |
439 | for (param = DECL_ARGUMENTS (func), | |
440 | arg = first_call_expr_arg (call, &iter); | |
441 | param && arg; | |
442 | param = TREE_CHAIN (param), arg = next_call_expr_arg (&iter)) | |
6de9cd9a | 443 | { |
14de86fa ZD |
444 | if (param != arg) |
445 | { | |
446 | /* Make sure there are no problems with copying. The parameter | |
6de9cd9a DN |
447 | have a copyable type and the two arguments must have reasonably |
448 | equivalent types. The latter requirement could be relaxed if | |
449 | we emitted a suitable type conversion statement. */ | |
14de86fa | 450 | if (!is_gimple_reg_type (TREE_TYPE (param)) |
6de9cd9a | 451 | || !lang_hooks.types_compatible_p (TREE_TYPE (param), |
14de86fa ZD |
452 | TREE_TYPE (arg))) |
453 | break; | |
454 | ||
455 | /* The parameter should be a real operand, so that phi node | |
456 | created for it at the start of the function has the meaning | |
457 | of copying the value. This test implies is_gimple_reg_type | |
458 | from the previous condition, however this one could be | |
459 | relaxed by being more careful with copying the new value | |
07beea0d | 460 | of the parameter (emitting appropriate GIMPLE_MODIFY_STMT and |
14de86fa ZD |
461 | updating the virtual operands). */ |
462 | if (!is_gimple_reg (param)) | |
463 | break; | |
464 | } | |
6de9cd9a | 465 | } |
5039610b | 466 | if (!arg && !param) |
6de9cd9a DN |
467 | tail_recursion = true; |
468 | } | |
469 | ||
470 | /* Now check the statements after the call. None of them has virtual | |
471 | operands, so they may only depend on the call through its return | |
472 | value. The return value should also be dependent on each of them, | |
473 | since we are running after dce. */ | |
474 | m = NULL_TREE; | |
475 | a = NULL_TREE; | |
476 | ||
477 | abb = bb; | |
478 | absi = bsi; | |
479 | while (1) | |
480 | { | |
481 | bsi_next (&absi); | |
482 | ||
483 | while (bsi_end_p (absi)) | |
484 | { | |
c5cbcccf ZD |
485 | ass_var = propagate_through_phis (ass_var, single_succ_edge (abb)); |
486 | abb = single_succ (abb); | |
6de9cd9a DN |
487 | absi = bsi_start (abb); |
488 | } | |
489 | ||
490 | stmt = bsi_stmt (absi); | |
491 | ||
492 | if (TREE_CODE (stmt) == LABEL_EXPR) | |
493 | continue; | |
494 | ||
495 | if (TREE_CODE (stmt) == RETURN_EXPR) | |
496 | break; | |
497 | ||
07beea0d | 498 | if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT) |
6de9cd9a DN |
499 | return; |
500 | ||
6de9cd9a DN |
501 | if (!process_assignment (stmt, stmt, bsi, &m, &a, &ass_var)) |
502 | return; | |
503 | } | |
504 | ||
b89e96ac | 505 | /* See if this is a tail call we can handle. */ |
6de9cd9a DN |
506 | ret_var = TREE_OPERAND (stmt, 0); |
507 | if (ret_var | |
07beea0d | 508 | && TREE_CODE (ret_var) == GIMPLE_MODIFY_STMT) |
6de9cd9a | 509 | { |
07beea0d | 510 | tree ret_op = GIMPLE_STMT_OPERAND (ret_var, 1); |
b89e96ac | 511 | STRIP_NOPS (ret_op); |
6de9cd9a | 512 | if (!tail_recursion |
b89e96ac | 513 | && TREE_CODE (ret_op) != SSA_NAME) |
6de9cd9a DN |
514 | return; |
515 | ||
516 | if (!process_assignment (ret_var, stmt, bsi, &m, &a, &ass_var)) | |
517 | return; | |
07beea0d | 518 | ret_var = GIMPLE_STMT_OPERAND (ret_var, 0); |
6de9cd9a DN |
519 | } |
520 | ||
521 | /* We may proceed if there either is no return value, or the return value | |
522 | is identical to the call's return. */ | |
523 | if (ret_var | |
524 | && (ret_var != ass_var)) | |
525 | return; | |
526 | ||
4b5b9613 RH |
527 | /* If this is not a tail recursive call, we cannot handle addends or |
528 | multiplicands. */ | |
529 | if (!tail_recursion && (m || a)) | |
530 | return; | |
531 | ||
e1111e8e | 532 | nw = XNEW (struct tailcall); |
6de9cd9a DN |
533 | |
534 | nw->call_block = bb; | |
535 | nw->call_bsi = bsi; | |
536 | ||
537 | nw->tail_recursion = tail_recursion; | |
538 | ||
539 | nw->mult = m; | |
540 | nw->add = a; | |
541 | ||
542 | nw->next = *ret; | |
543 | *ret = nw; | |
544 | } | |
545 | ||
546 | /* Adjust the accumulator values according to A and M after BSI, and update | |
547 | the phi nodes on edge BACK. */ | |
548 | ||
549 | static void | |
550 | adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back) | |
551 | { | |
552 | tree stmt, var, phi, tmp; | |
553 | tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl)); | |
554 | tree a_acc_arg = a_acc, m_acc_arg = m_acc; | |
555 | ||
556 | if (a) | |
557 | { | |
558 | if (m_acc) | |
559 | { | |
560 | if (integer_onep (a)) | |
561 | var = m_acc; | |
562 | else | |
563 | { | |
ebb07520 RS |
564 | stmt = build_gimple_modify_stmt (NULL_TREE, |
565 | build2 (MULT_EXPR, ret_type, | |
566 | m_acc, a)); | |
6de9cd9a DN |
567 | |
568 | tmp = create_tmp_var (ret_type, "acc_tmp"); | |
f004ab02 | 569 | add_referenced_var (tmp); |
6de9cd9a DN |
570 | |
571 | var = make_ssa_name (tmp, stmt); | |
07beea0d | 572 | GIMPLE_STMT_OPERAND (stmt, 0) = var; |
6de9cd9a DN |
573 | bsi_insert_after (&bsi, stmt, BSI_NEW_STMT); |
574 | } | |
575 | } | |
576 | else | |
577 | var = a; | |
578 | ||
ebb07520 RS |
579 | stmt = build_gimple_modify_stmt (NULL_TREE, build2 (PLUS_EXPR, ret_type, |
580 | a_acc, var)); | |
6de9cd9a | 581 | var = make_ssa_name (SSA_NAME_VAR (a_acc), stmt); |
07beea0d | 582 | GIMPLE_STMT_OPERAND (stmt, 0) = var; |
6de9cd9a DN |
583 | bsi_insert_after (&bsi, stmt, BSI_NEW_STMT); |
584 | a_acc_arg = var; | |
585 | } | |
586 | ||
587 | if (m) | |
588 | { | |
ebb07520 RS |
589 | stmt = build_gimple_modify_stmt (NULL_TREE, |
590 | build2 (MULT_EXPR, ret_type, | |
591 | m_acc, m)); | |
6de9cd9a | 592 | var = make_ssa_name (SSA_NAME_VAR (m_acc), stmt); |
07beea0d | 593 | GIMPLE_STMT_OPERAND (stmt, 0) = var; |
6de9cd9a DN |
594 | bsi_insert_after (&bsi, stmt, BSI_NEW_STMT); |
595 | m_acc_arg = var; | |
596 | } | |
597 | ||
598 | if (a_acc) | |
599 | { | |
17192884 | 600 | for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi)) |
6de9cd9a DN |
601 | if (PHI_RESULT (phi) == a_acc) |
602 | break; | |
603 | ||
d2e398df | 604 | add_phi_arg (phi, a_acc_arg, back); |
6de9cd9a DN |
605 | } |
606 | ||
607 | if (m_acc) | |
608 | { | |
17192884 | 609 | for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi)) |
6de9cd9a DN |
610 | if (PHI_RESULT (phi) == m_acc) |
611 | break; | |
612 | ||
d2e398df | 613 | add_phi_arg (phi, m_acc_arg, back); |
6de9cd9a DN |
614 | } |
615 | } | |
616 | ||
1ea7e6ad | 617 | /* Adjust value of the return at the end of BB according to M and A |
6de9cd9a DN |
618 | accumulators. */ |
619 | ||
620 | static void | |
621 | adjust_return_value (basic_block bb, tree m, tree a) | |
622 | { | |
623 | tree ret_stmt = last_stmt (bb), ret_var, var, stmt, tmp; | |
624 | tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl)); | |
bbba68dd | 625 | tree *ret_op; |
6de9cd9a DN |
626 | block_stmt_iterator bsi = bsi_last (bb); |
627 | ||
1e128c5f | 628 | gcc_assert (TREE_CODE (ret_stmt) == RETURN_EXPR); |
6de9cd9a DN |
629 | |
630 | ret_var = TREE_OPERAND (ret_stmt, 0); | |
631 | if (!ret_var) | |
632 | return; | |
633 | ||
07beea0d | 634 | if (TREE_CODE (ret_var) == GIMPLE_MODIFY_STMT) |
6de9cd9a | 635 | { |
bbba68dd JH |
636 | ret_op = &GIMPLE_STMT_OPERAND (ret_var, 1); |
637 | ret_var = *ret_op; | |
6de9cd9a | 638 | } |
bbba68dd JH |
639 | else |
640 | ret_op = &TREE_OPERAND (ret_stmt, 0); | |
6de9cd9a DN |
641 | |
642 | if (m) | |
643 | { | |
ebb07520 RS |
644 | stmt = build_gimple_modify_stmt (NULL_TREE, |
645 | build2 (MULT_EXPR, ret_type, | |
646 | m_acc, ret_var)); | |
6de9cd9a DN |
647 | |
648 | tmp = create_tmp_var (ret_type, "acc_tmp"); | |
f004ab02 | 649 | add_referenced_var (tmp); |
6de9cd9a DN |
650 | |
651 | var = make_ssa_name (tmp, stmt); | |
07beea0d | 652 | GIMPLE_STMT_OPERAND (stmt, 0) = var; |
b1d16eff | 653 | bsi_insert_before (&bsi, stmt, BSI_SAME_STMT); |
6de9cd9a DN |
654 | } |
655 | else | |
656 | var = ret_var; | |
657 | ||
658 | if (a) | |
659 | { | |
ebb07520 RS |
660 | stmt = build_gimple_modify_stmt (NULL_TREE, |
661 | build2 (PLUS_EXPR, ret_type, | |
662 | a_acc, var)); | |
6de9cd9a DN |
663 | |
664 | tmp = create_tmp_var (ret_type, "acc_tmp"); | |
f004ab02 | 665 | add_referenced_var (tmp); |
6de9cd9a DN |
666 | |
667 | var = make_ssa_name (tmp, stmt); | |
07beea0d | 668 | GIMPLE_STMT_OPERAND (stmt, 0) = var; |
b1d16eff | 669 | bsi_insert_before (&bsi, stmt, BSI_SAME_STMT); |
6de9cd9a DN |
670 | } |
671 | ||
bbba68dd | 672 | *ret_op = var; |
f430bae8 | 673 | update_stmt (ret_stmt); |
6de9cd9a DN |
674 | } |
675 | ||
23504559 JH |
676 | /* Subtract COUNT and FREQUENCY from the basic block and it's |
677 | outgoing edge. */ | |
678 | static void | |
679 | decrease_profile (basic_block bb, gcov_type count, int frequency) | |
680 | { | |
681 | edge e; | |
682 | bb->count -= count; | |
683 | if (bb->count < 0) | |
684 | bb->count = 0; | |
685 | bb->frequency -= frequency; | |
686 | if (bb->frequency < 0) | |
687 | bb->frequency = 0; | |
688 | if (!single_succ_p (bb)) | |
689 | { | |
690 | gcc_assert (!EDGE_COUNT (bb->succs)); | |
691 | return; | |
692 | } | |
693 | e = single_succ_edge (bb); | |
694 | e->count -= count; | |
695 | if (e->count < 0) | |
696 | e->count = 0; | |
697 | } | |
698 | ||
016925bc ZD |
699 | /* Returns true if argument PARAM of the tail recursive call needs to be copied |
700 | when the call is eliminated. */ | |
701 | ||
702 | static bool | |
703 | arg_needs_copy_p (tree param) | |
704 | { | |
705 | tree def; | |
706 | ||
707 | if (!is_gimple_reg (param) || !var_ann (param)) | |
708 | return false; | |
709 | ||
710 | /* Parameters that are only defined but never used need not be copied. */ | |
5cd4ec7f | 711 | def = gimple_default_def (cfun, param); |
016925bc ZD |
712 | if (!def) |
713 | return false; | |
714 | ||
715 | return true; | |
716 | } | |
717 | ||
6de9cd9a DN |
718 | /* Eliminates tail call described by T. TMP_VARS is a list of |
719 | temporary variables used to copy the function arguments. */ | |
720 | ||
721 | static void | |
722 | eliminate_tail_call (struct tailcall *t) | |
723 | { | |
5039610b SL |
724 | tree param, stmt, rslt, call; |
725 | tree arg; | |
726 | call_expr_arg_iterator iter; | |
6de9cd9a DN |
727 | basic_block bb, first; |
728 | edge e; | |
729 | tree phi; | |
8d3d51b5 | 730 | block_stmt_iterator bsi; |
f47c96aa | 731 | tree orig_stmt; |
6de9cd9a | 732 | |
f47c96aa | 733 | stmt = orig_stmt = bsi_stmt (t->call_bsi); |
6de9cd9a DN |
734 | bb = t->call_block; |
735 | ||
736 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
737 | { | |
738 | fprintf (dump_file, "Eliminated tail recursion in bb %d : ", | |
739 | bb->index); | |
740 | print_generic_stmt (dump_file, stmt, TDF_SLIM); | |
741 | fprintf (dump_file, "\n"); | |
742 | } | |
743 | ||
07beea0d AH |
744 | if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) |
745 | stmt = GIMPLE_STMT_OPERAND (stmt, 1); | |
6de9cd9a | 746 | |
c5cbcccf | 747 | first = single_succ (ENTRY_BLOCK_PTR); |
6de9cd9a | 748 | |
8d3d51b5 ZD |
749 | /* Remove the code after call_bsi that will become unreachable. The |
750 | possibly unreachable code in other blocks is removed later in | |
751 | cfg cleanup. */ | |
752 | bsi = t->call_bsi; | |
753 | bsi_next (&bsi); | |
754 | while (!bsi_end_p (bsi)) | |
755 | { | |
87527e4b | 756 | tree t = bsi_stmt (bsi); |
8d3d51b5 ZD |
757 | /* Do not remove the return statement, so that redirect_edge_and_branch |
758 | sees how the block ends. */ | |
87527e4b | 759 | if (TREE_CODE (t) == RETURN_EXPR) |
8d3d51b5 ZD |
760 | break; |
761 | ||
736432ee | 762 | bsi_remove (&bsi, true); |
87527e4b | 763 | release_defs (t); |
8d3d51b5 ZD |
764 | } |
765 | ||
23504559 JH |
766 | /* Number of executions of function has reduced by the tailcall. */ |
767 | e = single_succ_edge (t->call_block); | |
768 | decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e)); | |
769 | decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e)); | |
770 | if (e->dest != EXIT_BLOCK_PTR) | |
771 | decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e)); | |
772 | ||
6de9cd9a | 773 | /* Replace the call by a jump to the start of function. */ |
c5cbcccf | 774 | e = redirect_edge_and_branch (single_succ_edge (t->call_block), first); |
1e128c5f | 775 | gcc_assert (e); |
6de9cd9a DN |
776 | PENDING_STMT (e) = NULL_TREE; |
777 | ||
016925bc ZD |
778 | /* Add phi node entries for arguments. The ordering of the phi nodes should |
779 | be the same as the ordering of the arguments. */ | |
6de9cd9a | 780 | for (param = DECL_ARGUMENTS (current_function_decl), |
5039610b SL |
781 | arg = first_call_expr_arg (stmt, &iter), |
782 | phi = phi_nodes (first); | |
6de9cd9a | 783 | param; |
5039610b | 784 | param = TREE_CHAIN (param), arg = next_call_expr_arg (&iter)) |
6de9cd9a | 785 | { |
016925bc | 786 | if (!arg_needs_copy_p (param)) |
6de9cd9a | 787 | continue; |
016925bc | 788 | gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi))); |
6de9cd9a | 789 | |
5039610b | 790 | add_phi_arg (phi, arg, e); |
016925bc | 791 | phi = PHI_CHAIN (phi); |
6de9cd9a DN |
792 | } |
793 | ||
794 | /* Update the values of accumulators. */ | |
795 | adjust_accumulator_values (t->call_bsi, t->mult, t->add, e); | |
796 | ||
797 | call = bsi_stmt (t->call_bsi); | |
07beea0d | 798 | if (TREE_CODE (call) == GIMPLE_MODIFY_STMT) |
6de9cd9a | 799 | { |
07beea0d | 800 | rslt = GIMPLE_STMT_OPERAND (call, 0); |
6de9cd9a DN |
801 | |
802 | /* Result of the call will no longer be defined. So adjust the | |
803 | SSA_NAME_DEF_STMT accordingly. */ | |
804 | SSA_NAME_DEF_STMT (rslt) = build_empty_stmt (); | |
805 | } | |
806 | ||
736432ee | 807 | bsi_remove (&t->call_bsi, true); |
87527e4b | 808 | release_defs (call); |
6de9cd9a DN |
809 | } |
810 | ||
016925bc ZD |
811 | /* Add phi nodes for the virtual operands defined in the function to the |
812 | header of the loop created by tail recursion elimination. | |
813 | ||
814 | Originally, we used to add phi nodes only for call clobbered variables, | |
815 | as the value of the non-call clobbered ones obviously cannot be used | |
816 | or changed within the recursive call. However, the local variables | |
817 | from multiple calls now share the same location, so the virtual ssa form | |
818 | requires us to say that the location dies on further iterations of the loop, | |
819 | which requires adding phi nodes. | |
820 | */ | |
821 | static void | |
822 | add_virtual_phis (void) | |
823 | { | |
824 | referenced_var_iterator rvi; | |
825 | tree var; | |
826 | ||
827 | /* The problematic part is that there is no way how to know what | |
828 | to put into phi nodes (there in fact does not have to be such | |
829 | ssa name available). A solution would be to have an artificial | |
830 | use/kill for all virtual operands in EXIT node. Unless we have | |
831 | this, we cannot do much better than to rebuild the ssa form for | |
832 | possibly affected virtual ssa names from scratch. */ | |
833 | ||
834 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
835 | { | |
5cd4ec7f | 836 | if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE) |
016925bc ZD |
837 | mark_sym_for_renaming (var); |
838 | } | |
016925bc ZD |
839 | } |
840 | ||
6de9cd9a DN |
841 | /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also |
842 | mark the tailcalls for the sibcall optimization. */ | |
843 | ||
844 | static bool | |
845 | optimize_tail_call (struct tailcall *t, bool opt_tailcalls) | |
846 | { | |
847 | if (t->tail_recursion) | |
848 | { | |
849 | eliminate_tail_call (t); | |
850 | return true; | |
851 | } | |
852 | ||
853 | if (opt_tailcalls) | |
854 | { | |
855 | tree stmt = bsi_stmt (t->call_bsi); | |
856 | ||
cd709752 | 857 | stmt = get_call_expr_in (stmt); |
6de9cd9a DN |
858 | CALL_EXPR_TAILCALL (stmt) = 1; |
859 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
860 | { | |
861 | fprintf (dump_file, "Found tail call "); | |
862 | print_generic_expr (dump_file, stmt, dump_flags); | |
863 | fprintf (dump_file, " in bb %i\n", t->call_block->index); | |
864 | } | |
865 | } | |
866 | ||
867 | return false; | |
868 | } | |
869 | ||
870 | /* Optimizes tail calls in the function, turning the tail recursion | |
871 | into iteration. */ | |
872 | ||
1994bfea | 873 | static unsigned int |
6de9cd9a DN |
874 | tree_optimize_tail_calls_1 (bool opt_tailcalls) |
875 | { | |
876 | edge e; | |
877 | bool phis_constructed = false; | |
878 | struct tailcall *tailcalls = NULL, *act, *next; | |
879 | bool changed = false; | |
c5cbcccf | 880 | basic_block first = single_succ (ENTRY_BLOCK_PTR); |
6de9cd9a | 881 | tree stmt, param, ret_type, tmp, phi; |
628f6a4e | 882 | edge_iterator ei; |
6de9cd9a DN |
883 | |
884 | if (!suitable_for_tail_opt_p ()) | |
1994bfea | 885 | return 0; |
6de9cd9a DN |
886 | if (opt_tailcalls) |
887 | opt_tailcalls = suitable_for_tail_call_opt_p (); | |
888 | ||
628f6a4e | 889 | FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) |
6de9cd9a DN |
890 | { |
891 | /* Only traverse the normal exits, i.e. those that end with return | |
892 | statement. */ | |
893 | stmt = last_stmt (e->src); | |
894 | ||
895 | if (stmt | |
896 | && TREE_CODE (stmt) == RETURN_EXPR) | |
897 | find_tail_calls (e->src, &tailcalls); | |
898 | } | |
899 | ||
900 | /* Construct the phi nodes and accumulators if necessary. */ | |
901 | a_acc = m_acc = NULL_TREE; | |
902 | for (act = tailcalls; act; act = act->next) | |
903 | { | |
904 | if (!act->tail_recursion) | |
905 | continue; | |
906 | ||
907 | if (!phis_constructed) | |
908 | { | |
909 | /* Ensure that there is only one predecessor of the block. */ | |
c5cbcccf ZD |
910 | if (!single_pred_p (first)) |
911 | first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR)); | |
6de9cd9a DN |
912 | |
913 | /* Copy the args if needed. */ | |
914 | for (param = DECL_ARGUMENTS (current_function_decl); | |
915 | param; | |
916 | param = TREE_CHAIN (param)) | |
016925bc ZD |
917 | if (arg_needs_copy_p (param)) |
918 | { | |
5cd4ec7f | 919 | tree name = gimple_default_def (cfun, param); |
016925bc ZD |
920 | tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name)); |
921 | tree phi; | |
922 | ||
923 | set_default_def (param, new_name); | |
924 | phi = create_phi_node (name, first); | |
925 | SSA_NAME_DEF_STMT (name) = phi; | |
926 | add_phi_arg (phi, new_name, single_pred_edge (first)); | |
927 | } | |
6de9cd9a DN |
928 | phis_constructed = true; |
929 | } | |
930 | ||
931 | if (act->add && !a_acc) | |
932 | { | |
933 | ret_type = TREE_TYPE (DECL_RESULT (current_function_decl)); | |
934 | ||
935 | tmp = create_tmp_var (ret_type, "add_acc"); | |
f004ab02 | 936 | add_referenced_var (tmp); |
6de9cd9a DN |
937 | |
938 | phi = create_phi_node (tmp, first); | |
d2e398df | 939 | add_phi_arg (phi, |
a58eeb31 NS |
940 | /* RET_TYPE can be a float when -ffast-maths is |
941 | enabled. */ | |
942 | fold_convert (ret_type, integer_zero_node), | |
c5cbcccf | 943 | single_pred_edge (first)); |
6de9cd9a DN |
944 | a_acc = PHI_RESULT (phi); |
945 | } | |
946 | ||
947 | if (act->mult && !m_acc) | |
948 | { | |
949 | ret_type = TREE_TYPE (DECL_RESULT (current_function_decl)); | |
950 | ||
951 | tmp = create_tmp_var (ret_type, "mult_acc"); | |
f004ab02 | 952 | add_referenced_var (tmp); |
6de9cd9a DN |
953 | |
954 | phi = create_phi_node (tmp, first); | |
d2e398df | 955 | add_phi_arg (phi, |
a58eeb31 NS |
956 | /* RET_TYPE can be a float when -ffast-maths is |
957 | enabled. */ | |
958 | fold_convert (ret_type, integer_one_node), | |
c5cbcccf | 959 | single_pred_edge (first)); |
6de9cd9a DN |
960 | m_acc = PHI_RESULT (phi); |
961 | } | |
962 | } | |
963 | ||
016925bc ZD |
964 | |
965 | if (phis_constructed) | |
966 | { | |
967 | /* Reverse the order of the phi nodes, so that it matches the order | |
968 | of operands of the function, as assumed by eliminate_tail_call. */ | |
969 | set_phi_nodes (first, phi_reverse (phi_nodes (first))); | |
970 | } | |
971 | ||
6de9cd9a DN |
972 | for (; tailcalls; tailcalls = next) |
973 | { | |
974 | next = tailcalls->next; | |
975 | changed |= optimize_tail_call (tailcalls, opt_tailcalls); | |
976 | free (tailcalls); | |
977 | } | |
978 | ||
979 | if (a_acc || m_acc) | |
980 | { | |
981 | /* Modify the remaining return statements. */ | |
628f6a4e | 982 | FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) |
6de9cd9a DN |
983 | { |
984 | stmt = last_stmt (e->src); | |
985 | ||
986 | if (stmt | |
987 | && TREE_CODE (stmt) == RETURN_EXPR) | |
988 | adjust_return_value (e->src, m_acc, a_acc); | |
989 | } | |
990 | } | |
991 | ||
992 | if (changed) | |
1994bfea | 993 | free_dominance_info (CDI_DOMINATORS); |
016925bc ZD |
994 | |
995 | if (phis_constructed) | |
996 | add_virtual_phis (); | |
1994bfea JH |
997 | if (changed) |
998 | return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals; | |
999 | return 0; | |
6de9cd9a DN |
1000 | } |
1001 | ||
c2924966 | 1002 | static unsigned int |
6de9cd9a DN |
1003 | execute_tail_recursion (void) |
1004 | { | |
1994bfea | 1005 | return tree_optimize_tail_calls_1 (false); |
6de9cd9a DN |
1006 | } |
1007 | ||
1008 | static bool | |
1009 | gate_tail_calls (void) | |
1010 | { | |
6fb5fa3c | 1011 | return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call); |
6de9cd9a DN |
1012 | } |
1013 | ||
c2924966 | 1014 | static unsigned int |
6de9cd9a DN |
1015 | execute_tail_calls (void) |
1016 | { | |
1994bfea | 1017 | return tree_optimize_tail_calls_1 (true); |
6de9cd9a DN |
1018 | } |
1019 | ||
1020 | struct tree_opt_pass pass_tail_recursion = | |
1021 | { | |
1022 | "tailr", /* name */ | |
e8c3ff97 | 1023 | gate_tail_calls, /* gate */ |
6de9cd9a DN |
1024 | execute_tail_recursion, /* execute */ |
1025 | NULL, /* sub */ | |
1026 | NULL, /* next */ | |
1027 | 0, /* static_pass_number */ | |
1028 | 0, /* tv_id */ | |
7faade0f | 1029 | PROP_cfg | PROP_ssa, /* properties_required */ |
6de9cd9a DN |
1030 | 0, /* properties_provided */ |
1031 | 0, /* properties_destroyed */ | |
1032 | 0, /* todo_flags_start */ | |
9f8628ba PB |
1033 | TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */ |
1034 | 0 /* letter */ | |
6de9cd9a DN |
1035 | }; |
1036 | ||
1037 | struct tree_opt_pass pass_tail_calls = | |
1038 | { | |
1039 | "tailc", /* name */ | |
1040 | gate_tail_calls, /* gate */ | |
1041 | execute_tail_calls, /* execute */ | |
1042 | NULL, /* sub */ | |
1043 | NULL, /* next */ | |
1044 | 0, /* static_pass_number */ | |
1045 | 0, /* tv_id */ | |
c1b763fa | 1046 | PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ |
6de9cd9a DN |
1047 | 0, /* properties_provided */ |
1048 | 0, /* properties_destroyed */ | |
1049 | 0, /* todo_flags_start */ | |
9f8628ba PB |
1050 | TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */ |
1051 | 0 /* letter */ | |
6de9cd9a | 1052 | }; |