|
0
|
1 /* Tail call optimization on trees.
|
|
|
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
|
|
|
3 Free Software Foundation, Inc.
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
7 GCC is free software; you can redistribute it and/or modify
|
|
|
8 it under the terms of the GNU General Public License as published by
|
|
|
9 the Free Software Foundation; either version 3, or (at your option)
|
|
|
10 any later version.
|
|
|
11
|
|
|
12 GCC is distributed in the hope that it will be useful,
|
|
|
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
15 GNU General Public License for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with GCC; see the file COPYING3. If not see
|
|
|
19 <http://www.gnu.org/licenses/>. */
|
|
|
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"
|
|
|
38 #include "dbgcnt.h"
|
|
|
39
|
|
|
40 /* The file implements the tail recursion elimination. It is also used to
|
|
|
41 analyze the tail calls in general, passing the results to the rtl level
|
|
|
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
|
|
|
76 handled in adjust_return_value, the other two in adjust_accumulator_values
|
|
|
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
|
|
|
84 classical tail-recursion elimination way, into assignment of arguments
|
|
|
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 iterator pointing to the call statement. */
|
|
|
105 gimple_stmt_iterator call_gsi;
|
|
|
106
|
|
|
107 /* True if it is a call to the current function. */
|
|
|
108 bool tail_recursion;
|
|
|
109
|
|
|
110 /* The return value of the caller is mult * f + add, where f is the return
|
|
|
111 value of the call. */
|
|
|
112 tree mult, add;
|
|
|
113
|
|
|
114 /* Next tailcall in the chain. */
|
|
|
115 struct tailcall *next;
|
|
|
116 };
|
|
|
117
|
|
|
118 /* The variables holding the value of multiplicative and additive
|
|
|
119 accumulator. */
|
|
|
120 static tree m_acc, a_acc;
|
|
|
121
|
|
|
122 static bool suitable_for_tail_opt_p (void);
|
|
|
123 static bool optimize_tail_call (struct tailcall *, bool);
|
|
|
124 static void eliminate_tail_call (struct tailcall *);
|
|
|
125 static void find_tail_calls (basic_block, struct tailcall **);
|
|
|
126
|
|
|
127 /* Returns false when the function is not suitable for tail call optimization
|
|
|
128 from some reason (e.g. if it takes variable number of arguments). */
|
|
|
129
|
|
|
130 static bool
|
|
|
131 suitable_for_tail_opt_p (void)
|
|
|
132 {
|
|
|
133 referenced_var_iterator rvi;
|
|
|
134 tree var;
|
|
|
135
|
|
|
136 if (cfun->stdarg)
|
|
|
137 return false;
|
|
|
138
|
|
|
139 /* No local variable nor structure field should be call-used. We
|
|
|
140 ignore any kind of memory tag, as these are not real variables. */
|
|
|
141
|
|
|
142 FOR_EACH_REFERENCED_VAR (var, rvi)
|
|
|
143 {
|
|
|
144 if (!is_global_var (var)
|
|
|
145 && !MTAG_P (var)
|
|
|
146 && (gimple_aliases_computed_p (cfun)? is_call_used (var)
|
|
|
147 : TREE_ADDRESSABLE (var)))
|
|
|
148 return false;
|
|
|
149 }
|
|
|
150
|
|
|
151 return true;
|
|
|
152 }
|
|
|
153 /* Returns false when the function is not suitable for tail call optimization
|
|
|
154 from some reason (e.g. if it takes variable number of arguments).
|
|
|
155 This test must pass in addition to suitable_for_tail_opt_p in order to make
|
|
|
156 tail call discovery happen. */
|
|
|
157
|
|
|
158 static bool
|
|
|
159 suitable_for_tail_call_opt_p (void)
|
|
|
160 {
|
|
|
161 tree param;
|
|
|
162
|
|
|
163 /* alloca (until we have stack slot life analysis) inhibits
|
|
|
164 sibling call optimizations, but not tail recursion. */
|
|
|
165 if (cfun->calls_alloca)
|
|
|
166 return false;
|
|
|
167
|
|
|
168 /* If we are using sjlj exceptions, we may need to add a call to
|
|
|
169 _Unwind_SjLj_Unregister at exit of the function. Which means
|
|
|
170 that we cannot do any sibcall transformations. */
|
|
|
171 if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ())
|
|
|
172 return false;
|
|
|
173
|
|
|
174 /* Any function that calls setjmp might have longjmp called from
|
|
|
175 any called function. ??? We really should represent this
|
|
|
176 properly in the CFG so that this needn't be special cased. */
|
|
|
177 if (cfun->calls_setjmp)
|
|
|
178 return false;
|
|
|
179
|
|
|
180 /* ??? It is OK if the argument of a function is taken in some cases,
|
|
|
181 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
|
|
|
182 for (param = DECL_ARGUMENTS (current_function_decl);
|
|
|
183 param;
|
|
|
184 param = TREE_CHAIN (param))
|
|
|
185 if (TREE_ADDRESSABLE (param))
|
|
|
186 return false;
|
|
|
187
|
|
|
188 return true;
|
|
|
189 }
|
|
|
190
|
|
|
191 /* Checks whether the expression EXPR in stmt AT is independent of the
|
|
|
192 statement pointed to by GSI (in a sense that we already know EXPR's value
|
|
|
193 at GSI). We use the fact that we are only called from the chain of
|
|
|
194 basic blocks that have only single successor. Returns the expression
|
|
|
195 containing the value of EXPR at GSI. */
|
|
|
196
|
|
|
197 static tree
|
|
|
198 independent_of_stmt_p (tree expr, gimple at, gimple_stmt_iterator gsi)
|
|
|
199 {
|
|
|
200 basic_block bb, call_bb, at_bb;
|
|
|
201 edge e;
|
|
|
202 edge_iterator ei;
|
|
|
203
|
|
|
204 if (is_gimple_min_invariant (expr))
|
|
|
205 return expr;
|
|
|
206
|
|
|
207 if (TREE_CODE (expr) != SSA_NAME)
|
|
|
208 return NULL_TREE;
|
|
|
209
|
|
|
210 /* Mark the blocks in the chain leading to the end. */
|
|
|
211 at_bb = gimple_bb (at);
|
|
|
212 call_bb = gimple_bb (gsi_stmt (gsi));
|
|
|
213 for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
|
|
|
214 bb->aux = &bb->aux;
|
|
|
215 bb->aux = &bb->aux;
|
|
|
216
|
|
|
217 while (1)
|
|
|
218 {
|
|
|
219 at = SSA_NAME_DEF_STMT (expr);
|
|
|
220 bb = gimple_bb (at);
|
|
|
221
|
|
|
222 /* The default definition or defined before the chain. */
|
|
|
223 if (!bb || !bb->aux)
|
|
|
224 break;
|
|
|
225
|
|
|
226 if (bb == call_bb)
|
|
|
227 {
|
|
|
228 for (; !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
229 if (gsi_stmt (gsi) == at)
|
|
|
230 break;
|
|
|
231
|
|
|
232 if (!gsi_end_p (gsi))
|
|
|
233 expr = NULL_TREE;
|
|
|
234 break;
|
|
|
235 }
|
|
|
236
|
|
|
237 if (gimple_code (at) != GIMPLE_PHI)
|
|
|
238 {
|
|
|
239 expr = NULL_TREE;
|
|
|
240 break;
|
|
|
241 }
|
|
|
242
|
|
|
243 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
244 if (e->src->aux)
|
|
|
245 break;
|
|
|
246 gcc_assert (e);
|
|
|
247
|
|
|
248 expr = PHI_ARG_DEF_FROM_EDGE (at, e);
|
|
|
249 if (TREE_CODE (expr) != SSA_NAME)
|
|
|
250 {
|
|
|
251 /* The value is a constant. */
|
|
|
252 break;
|
|
|
253 }
|
|
|
254 }
|
|
|
255
|
|
|
256 /* Unmark the blocks. */
|
|
|
257 for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
|
|
|
258 bb->aux = NULL;
|
|
|
259 bb->aux = NULL;
|
|
|
260
|
|
|
261 return expr;
|
|
|
262 }
|
|
|
263
|
|
|
264 /* Simulates the effect of an assignment STMT on the return value of the tail
|
|
|
265 recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
|
|
|
266 additive factor for the real return value. */
|
|
|
267
|
|
|
268 static bool
|
|
|
269 process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
|
|
|
270 tree *a, tree *ass_var)
|
|
|
271 {
|
|
|
272 tree op0, op1, non_ass_var;
|
|
|
273 tree dest = gimple_assign_lhs (stmt);
|
|
|
274 enum tree_code code = gimple_assign_rhs_code (stmt);
|
|
|
275 enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
|
|
|
276 tree src_var = gimple_assign_rhs1 (stmt);
|
|
|
277
|
|
|
278 /* See if this is a simple copy operation of an SSA name to the function
|
|
|
279 result. In that case we may have a simple tail call. Ignore type
|
|
|
280 conversions that can never produce extra code between the function
|
|
|
281 call and the function return. */
|
|
|
282 if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt))
|
|
|
283 && (TREE_CODE (src_var) == SSA_NAME))
|
|
|
284 {
|
|
|
285 /* Reject a tailcall if the type conversion might need
|
|
|
286 additional code. */
|
|
|
287 if (gimple_assign_cast_p (stmt)
|
|
|
288 && TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var)))
|
|
|
289 return false;
|
|
|
290
|
|
|
291 if (src_var != *ass_var)
|
|
|
292 return false;
|
|
|
293
|
|
|
294 *ass_var = dest;
|
|
|
295 return true;
|
|
|
296 }
|
|
|
297
|
|
|
298 if (rhs_class != GIMPLE_BINARY_RHS)
|
|
|
299 return false;
|
|
|
300
|
|
|
301 /* Accumulator optimizations will reverse the order of operations.
|
|
|
302 We can only do that for floating-point types if we're assuming
|
|
|
303 that addition and multiplication are associative. */
|
|
|
304 if (!flag_associative_math)
|
|
|
305 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
|
|
|
306 return false;
|
|
|
307
|
|
|
308 /* We only handle the code like
|
|
|
309
|
|
|
310 x = call ();
|
|
|
311 y = m * x;
|
|
|
312 z = y + a;
|
|
|
313 return z;
|
|
|
314
|
|
|
315 TODO -- Extend it for cases where the linear transformation of the output
|
|
|
316 is expressed in a more complicated way. */
|
|
|
317
|
|
|
318 op0 = gimple_assign_rhs1 (stmt);
|
|
|
319 op1 = gimple_assign_rhs2 (stmt);
|
|
|
320
|
|
|
321 if (op0 == *ass_var
|
|
|
322 && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
|
|
|
323 ;
|
|
|
324 else if (op1 == *ass_var
|
|
|
325 && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
|
|
|
326 ;
|
|
|
327 else
|
|
|
328 return false;
|
|
|
329
|
|
|
330 switch (code)
|
|
|
331 {
|
|
|
332 case PLUS_EXPR:
|
|
|
333 /* There should be no previous addition. TODO -- it should be fairly
|
|
|
334 straightforward to lift this restriction -- just allow storing
|
|
|
335 more complicated expressions in *A, and gimplify it in
|
|
|
336 adjust_accumulator_values. */
|
|
|
337 if (*a)
|
|
|
338 return false;
|
|
|
339 *a = non_ass_var;
|
|
|
340 *ass_var = dest;
|
|
|
341 return true;
|
|
|
342
|
|
|
343 case MULT_EXPR:
|
|
|
344 /* Similar remark applies here. Handling multiplication after addition
|
|
|
345 is just slightly more complicated -- we need to multiply both *A and
|
|
|
346 *M. */
|
|
|
347 if (*a || *m)
|
|
|
348 return false;
|
|
|
349 *m = non_ass_var;
|
|
|
350 *ass_var = dest;
|
|
|
351 return true;
|
|
|
352
|
|
|
353 /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR,
|
|
|
354 POINTER_PLUS_EXPR). */
|
|
|
355
|
|
|
356 default:
|
|
|
357 return false;
|
|
|
358 }
|
|
|
359 }
|
|
|
360
|
|
|
361 /* Propagate VAR through phis on edge E. */
|
|
|
362
|
|
|
363 static tree
|
|
|
364 propagate_through_phis (tree var, edge e)
|
|
|
365 {
|
|
|
366 basic_block dest = e->dest;
|
|
|
367 gimple_stmt_iterator gsi;
|
|
|
368
|
|
|
369 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
370 {
|
|
|
371 gimple phi = gsi_stmt (gsi);
|
|
|
372 if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
|
|
|
373 return PHI_RESULT (phi);
|
|
|
374 }
|
|
|
375 return var;
|
|
|
376 }
|
|
|
377
|
|
|
378 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
|
|
|
379 added to the start of RET. */
|
|
|
380
|
|
|
381 static void
|
|
|
382 find_tail_calls (basic_block bb, struct tailcall **ret)
|
|
|
383 {
|
|
|
384 tree ass_var = NULL_TREE, ret_var, func, param;
|
|
|
385 gimple stmt, call = NULL;
|
|
|
386 gimple_stmt_iterator gsi, agsi;
|
|
|
387 bool tail_recursion;
|
|
|
388 struct tailcall *nw;
|
|
|
389 edge e;
|
|
|
390 tree m, a;
|
|
|
391 basic_block abb;
|
|
|
392 size_t idx;
|
|
|
393
|
|
|
394 if (!single_succ_p (bb))
|
|
|
395 return;
|
|
|
396
|
|
|
397 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
|
|
|
398 {
|
|
|
399 stmt = gsi_stmt (gsi);
|
|
|
400
|
|
|
401 /* Ignore labels. */
|
|
|
402 if (gimple_code (stmt) == GIMPLE_LABEL)
|
|
|
403 continue;
|
|
|
404
|
|
|
405 /* Check for a call. */
|
|
|
406 if (is_gimple_call (stmt))
|
|
|
407 {
|
|
|
408 call = stmt;
|
|
|
409 ass_var = gimple_call_lhs (stmt);
|
|
|
410 break;
|
|
|
411 }
|
|
|
412
|
|
|
413 /* If the statement has virtual or volatile operands, fail. */
|
|
|
414 if (!ZERO_SSA_OPERANDS (stmt, (SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS))
|
|
|
415 || gimple_has_volatile_ops (stmt)
|
|
|
416 || (!gimple_aliases_computed_p (cfun)
|
|
|
417 && gimple_references_memory_p (stmt)))
|
|
|
418 return;
|
|
|
419 }
|
|
|
420
|
|
|
421 if (gsi_end_p (gsi))
|
|
|
422 {
|
|
|
423 edge_iterator ei;
|
|
|
424 /* Recurse to the predecessors. */
|
|
|
425 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
426 find_tail_calls (e->src, ret);
|
|
|
427
|
|
|
428 return;
|
|
|
429 }
|
|
|
430
|
|
|
431 /* If the LHS of our call is not just a simple register, we can't
|
|
|
432 transform this into a tail or sibling call. This situation happens,
|
|
|
433 in (e.g.) "*p = foo()" where foo returns a struct. In this case
|
|
|
434 we won't have a temporary here, but we need to carry out the side
|
|
|
435 effect anyway, so tailcall is impossible.
|
|
|
436
|
|
|
437 ??? In some situations (when the struct is returned in memory via
|
|
|
438 invisible argument) we could deal with this, e.g. by passing 'p'
|
|
|
439 itself as that argument to foo, but it's too early to do this here,
|
|
|
440 and expand_call() will not handle it anyway. If it ever can, then
|
|
|
441 we need to revisit this here, to allow that situation. */
|
|
|
442 if (ass_var && !is_gimple_reg (ass_var))
|
|
|
443 return;
|
|
|
444
|
|
|
445 /* We found the call, check whether it is suitable. */
|
|
|
446 tail_recursion = false;
|
|
|
447 func = gimple_call_fndecl (call);
|
|
|
448 if (func == current_function_decl)
|
|
|
449 {
|
|
|
450 tree arg;
|
|
|
451 for (param = DECL_ARGUMENTS (func), idx = 0;
|
|
|
452 param && idx < gimple_call_num_args (call);
|
|
|
453 param = TREE_CHAIN (param), idx ++)
|
|
|
454 {
|
|
|
455 arg = gimple_call_arg (call, idx);
|
|
|
456 if (param != arg)
|
|
|
457 {
|
|
|
458 /* Make sure there are no problems with copying. The parameter
|
|
|
459 have a copyable type and the two arguments must have reasonably
|
|
|
460 equivalent types. The latter requirement could be relaxed if
|
|
|
461 we emitted a suitable type conversion statement. */
|
|
|
462 if (!is_gimple_reg_type (TREE_TYPE (param))
|
|
|
463 || !useless_type_conversion_p (TREE_TYPE (param),
|
|
|
464 TREE_TYPE (arg)))
|
|
|
465 break;
|
|
|
466
|
|
|
467 /* The parameter should be a real operand, so that phi node
|
|
|
468 created for it at the start of the function has the meaning
|
|
|
469 of copying the value. This test implies is_gimple_reg_type
|
|
|
470 from the previous condition, however this one could be
|
|
|
471 relaxed by being more careful with copying the new value
|
|
|
472 of the parameter (emitting appropriate GIMPLE_ASSIGN and
|
|
|
473 updating the virtual operands). */
|
|
|
474 if (!is_gimple_reg (param))
|
|
|
475 break;
|
|
|
476 }
|
|
|
477 }
|
|
|
478 if (idx == gimple_call_num_args (call) && !param)
|
|
|
479 tail_recursion = true;
|
|
|
480 }
|
|
|
481
|
|
|
482 /* Now check the statements after the call. None of them has virtual
|
|
|
483 operands, so they may only depend on the call through its return
|
|
|
484 value. The return value should also be dependent on each of them,
|
|
|
485 since we are running after dce. */
|
|
|
486 m = NULL_TREE;
|
|
|
487 a = NULL_TREE;
|
|
|
488
|
|
|
489 abb = bb;
|
|
|
490 agsi = gsi;
|
|
|
491 while (1)
|
|
|
492 {
|
|
|
493 gsi_next (&agsi);
|
|
|
494
|
|
|
495 while (gsi_end_p (agsi))
|
|
|
496 {
|
|
|
497 ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
|
|
|
498 abb = single_succ (abb);
|
|
|
499 agsi = gsi_start_bb (abb);
|
|
|
500 }
|
|
|
501
|
|
|
502 stmt = gsi_stmt (agsi);
|
|
|
503
|
|
|
504 if (gimple_code (stmt) == GIMPLE_LABEL)
|
|
|
505 continue;
|
|
|
506
|
|
|
507 if (gimple_code (stmt) == GIMPLE_RETURN)
|
|
|
508 break;
|
|
|
509
|
|
|
510 if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
|
|
511 return;
|
|
|
512
|
|
|
513 /* This is a gimple assign. */
|
|
|
514 if (! process_assignment (stmt, gsi, &m, &a, &ass_var))
|
|
|
515 return;
|
|
|
516 }
|
|
|
517
|
|
|
518 /* See if this is a tail call we can handle. */
|
|
|
519 ret_var = gimple_return_retval (stmt);
|
|
|
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
|
|
|
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
|
|
|
532 nw = XNEW (struct tailcall);
|
|
|
533
|
|
|
534 nw->call_gsi = gsi;
|
|
|
535
|
|
|
536 nw->tail_recursion = tail_recursion;
|
|
|
537
|
|
|
538 nw->mult = m;
|
|
|
539 nw->add = a;
|
|
|
540
|
|
|
541 nw->next = *ret;
|
|
|
542 *ret = nw;
|
|
|
543 }
|
|
|
544
|
|
|
545 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
|
|
|
546
|
|
|
547 static void
|
|
|
548 add_successor_phi_arg (edge e, tree var, tree phi_arg)
|
|
|
549 {
|
|
|
550 gimple_stmt_iterator gsi;
|
|
|
551
|
|
|
552 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
553 if (PHI_RESULT (gsi_stmt (gsi)) == var)
|
|
|
554 break;
|
|
|
555
|
|
|
556 gcc_assert (!gsi_end_p (gsi));
|
|
|
557 add_phi_arg (gsi_stmt (gsi), phi_arg, e);
|
|
|
558 }
|
|
|
559
|
|
|
560 /* Creates a GIMPLE statement which computes the operation specified by
|
|
|
561 CODE, OP0 and OP1 to a new variable with name LABEL and inserts the
|
|
|
562 statement in the position specified by GSI and UPDATE. Returns the
|
|
|
563 tree node of the statement's result. */
|
|
|
564
|
|
|
565 static tree
|
|
|
566 adjust_return_value_with_ops (enum tree_code code, const char *label,
|
|
|
567 tree op0, tree op1, gimple_stmt_iterator gsi,
|
|
|
568 enum gsi_iterator_update update)
|
|
|
569 {
|
|
|
570
|
|
|
571 tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
|
|
|
572 tree tmp = create_tmp_var (ret_type, label);
|
|
|
573 gimple stmt = gimple_build_assign_with_ops (code, tmp, op0, op1);
|
|
|
574 tree result;
|
|
|
575
|
|
|
576 add_referenced_var (tmp);
|
|
|
577 result = make_ssa_name (tmp, stmt);
|
|
|
578 gimple_assign_set_lhs (stmt, result);
|
|
|
579 update_stmt (stmt);
|
|
|
580 gsi_insert_before (&gsi, stmt, update);
|
|
|
581 return result;
|
|
|
582 }
|
|
|
583
|
|
|
584 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
|
|
|
585 the computation specified by CODE and OP1 and insert the statement
|
|
|
586 at the position specified by GSI as a new statement. Returns new SSA name
|
|
|
587 of updated accumulator. */
|
|
|
588
|
|
|
589 static tree
|
|
|
590 update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
|
|
|
591 gimple_stmt_iterator gsi)
|
|
|
592 {
|
|
|
593 gimple stmt = gimple_build_assign_with_ops (code, SSA_NAME_VAR (acc), acc,
|
|
|
594 op1);
|
|
|
595 tree var = make_ssa_name (SSA_NAME_VAR (acc), stmt);
|
|
|
596 gimple_assign_set_lhs (stmt, var);
|
|
|
597 update_stmt (stmt);
|
|
|
598 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
|
|
|
599 return var;
|
|
|
600 }
|
|
|
601
|
|
|
602 /* Adjust the accumulator values according to A and M after GSI, and update
|
|
|
603 the phi nodes on edge BACK. */
|
|
|
604
|
|
|
605 static void
|
|
|
606 adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
|
|
|
607 {
|
|
|
608 tree var, a_acc_arg = a_acc, m_acc_arg = m_acc;
|
|
|
609
|
|
|
610 if (a)
|
|
|
611 {
|
|
|
612 if (m_acc)
|
|
|
613 {
|
|
|
614 if (integer_onep (a))
|
|
|
615 var = m_acc;
|
|
|
616 else
|
|
|
617 var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
|
|
|
618 a, gsi, GSI_NEW_STMT);
|
|
|
619 }
|
|
|
620 else
|
|
|
621 var = a;
|
|
|
622
|
|
|
623 a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
|
|
|
624 }
|
|
|
625
|
|
|
626 if (m)
|
|
|
627 m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
|
|
|
628
|
|
|
629 if (a_acc)
|
|
|
630 add_successor_phi_arg (back, a_acc, a_acc_arg);
|
|
|
631
|
|
|
632 if (m_acc)
|
|
|
633 add_successor_phi_arg (back, m_acc, m_acc_arg);
|
|
|
634 }
|
|
|
635
|
|
|
636 /* Adjust value of the return at the end of BB according to M and A
|
|
|
637 accumulators. */
|
|
|
638
|
|
|
639 static void
|
|
|
640 adjust_return_value (basic_block bb, tree m, tree a)
|
|
|
641 {
|
|
|
642 tree retval;
|
|
|
643 gimple ret_stmt = gimple_seq_last_stmt (bb_seq (bb));
|
|
|
644 gimple_stmt_iterator gsi = gsi_last_bb (bb);
|
|
|
645
|
|
|
646 gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
|
|
|
647
|
|
|
648 retval = gimple_return_retval (ret_stmt);
|
|
|
649 if (!retval || retval == error_mark_node)
|
|
|
650 return;
|
|
|
651
|
|
|
652 if (m)
|
|
|
653 retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
|
|
|
654 gsi, GSI_SAME_STMT);
|
|
|
655 if (a)
|
|
|
656 retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
|
|
|
657 gsi, GSI_SAME_STMT);
|
|
|
658 gimple_return_set_retval (ret_stmt, retval);
|
|
|
659 update_stmt (ret_stmt);
|
|
|
660 }
|
|
|
661
|
|
|
662 /* Subtract COUNT and FREQUENCY from the basic block and it's
|
|
|
663 outgoing edge. */
|
|
|
664 static void
|
|
|
665 decrease_profile (basic_block bb, gcov_type count, int frequency)
|
|
|
666 {
|
|
|
667 edge e;
|
|
|
668 bb->count -= count;
|
|
|
669 if (bb->count < 0)
|
|
|
670 bb->count = 0;
|
|
|
671 bb->frequency -= frequency;
|
|
|
672 if (bb->frequency < 0)
|
|
|
673 bb->frequency = 0;
|
|
|
674 if (!single_succ_p (bb))
|
|
|
675 {
|
|
|
676 gcc_assert (!EDGE_COUNT (bb->succs));
|
|
|
677 return;
|
|
|
678 }
|
|
|
679 e = single_succ_edge (bb);
|
|
|
680 e->count -= count;
|
|
|
681 if (e->count < 0)
|
|
|
682 e->count = 0;
|
|
|
683 }
|
|
|
684
|
|
|
685 /* Returns true if argument PARAM of the tail recursive call needs to be copied
|
|
|
686 when the call is eliminated. */
|
|
|
687
|
|
|
688 static bool
|
|
|
689 arg_needs_copy_p (tree param)
|
|
|
690 {
|
|
|
691 tree def;
|
|
|
692
|
|
|
693 if (!is_gimple_reg (param) || !var_ann (param))
|
|
|
694 return false;
|
|
|
695
|
|
|
696 /* Parameters that are only defined but never used need not be copied. */
|
|
|
697 def = gimple_default_def (cfun, param);
|
|
|
698 if (!def)
|
|
|
699 return false;
|
|
|
700
|
|
|
701 return true;
|
|
|
702 }
|
|
|
703
|
|
|
704 /* Eliminates tail call described by T. TMP_VARS is a list of
|
|
|
705 temporary variables used to copy the function arguments. */
|
|
|
706
|
|
|
707 static void
|
|
|
708 eliminate_tail_call (struct tailcall *t)
|
|
|
709 {
|
|
|
710 tree param, rslt;
|
|
|
711 gimple stmt, call;
|
|
|
712 tree arg;
|
|
|
713 size_t idx;
|
|
|
714 basic_block bb, first;
|
|
|
715 edge e;
|
|
|
716 gimple phi;
|
|
|
717 gimple_stmt_iterator gsi;
|
|
|
718 gimple orig_stmt;
|
|
|
719
|
|
|
720 stmt = orig_stmt = gsi_stmt (t->call_gsi);
|
|
|
721 bb = gsi_bb (t->call_gsi);
|
|
|
722
|
|
|
723 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
724 {
|
|
|
725 fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
|
|
|
726 bb->index);
|
|
|
727 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
|
|
728 fprintf (dump_file, "\n");
|
|
|
729 }
|
|
|
730
|
|
|
731 gcc_assert (is_gimple_call (stmt));
|
|
|
732
|
|
|
733 first = single_succ (ENTRY_BLOCK_PTR);
|
|
|
734
|
|
|
735 /* Remove the code after call_gsi that will become unreachable. The
|
|
|
736 possibly unreachable code in other blocks is removed later in
|
|
|
737 cfg cleanup. */
|
|
|
738 gsi = t->call_gsi;
|
|
|
739 gsi_next (&gsi);
|
|
|
740 while (!gsi_end_p (gsi))
|
|
|
741 {
|
|
|
742 gimple t = gsi_stmt (gsi);
|
|
|
743 /* Do not remove the return statement, so that redirect_edge_and_branch
|
|
|
744 sees how the block ends. */
|
|
|
745 if (gimple_code (t) == GIMPLE_RETURN)
|
|
|
746 break;
|
|
|
747
|
|
|
748 gsi_remove (&gsi, true);
|
|
|
749 release_defs (t);
|
|
|
750 }
|
|
|
751
|
|
|
752 /* Number of executions of function has reduced by the tailcall. */
|
|
|
753 e = single_succ_edge (gsi_bb (t->call_gsi));
|
|
|
754 decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
|
|
|
755 decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
|
|
|
756 if (e->dest != EXIT_BLOCK_PTR)
|
|
|
757 decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
|
|
|
758
|
|
|
759 /* Replace the call by a jump to the start of function. */
|
|
|
760 e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)),
|
|
|
761 first);
|
|
|
762 gcc_assert (e);
|
|
|
763 PENDING_STMT (e) = NULL;
|
|
|
764
|
|
|
765 /* Add phi node entries for arguments. The ordering of the phi nodes should
|
|
|
766 be the same as the ordering of the arguments. */
|
|
|
767 for (param = DECL_ARGUMENTS (current_function_decl),
|
|
|
768 idx = 0, gsi = gsi_start_phis (first);
|
|
|
769 param;
|
|
|
770 param = TREE_CHAIN (param), idx++)
|
|
|
771 {
|
|
|
772 if (!arg_needs_copy_p (param))
|
|
|
773 continue;
|
|
|
774
|
|
|
775 arg = gimple_call_arg (stmt, idx);
|
|
|
776 phi = gsi_stmt (gsi);
|
|
|
777 gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
|
|
|
778
|
|
|
779 add_phi_arg (phi, arg, e);
|
|
|
780 gsi_next (&gsi);
|
|
|
781 }
|
|
|
782
|
|
|
783 /* Update the values of accumulators. */
|
|
|
784 adjust_accumulator_values (t->call_gsi, t->mult, t->add, e);
|
|
|
785
|
|
|
786 call = gsi_stmt (t->call_gsi);
|
|
|
787 rslt = gimple_call_lhs (call);
|
|
|
788 if (rslt != NULL_TREE)
|
|
|
789 {
|
|
|
790 /* Result of the call will no longer be defined. So adjust the
|
|
|
791 SSA_NAME_DEF_STMT accordingly. */
|
|
|
792 SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
|
|
|
793 }
|
|
|
794
|
|
|
795 gsi_remove (&t->call_gsi, true);
|
|
|
796 release_defs (call);
|
|
|
797 }
|
|
|
798
|
|
|
799 /* Add phi nodes for the virtual operands defined in the function to the
|
|
|
800 header of the loop created by tail recursion elimination.
|
|
|
801
|
|
|
802 Originally, we used to add phi nodes only for call clobbered variables,
|
|
|
803 as the value of the non-call clobbered ones obviously cannot be used
|
|
|
804 or changed within the recursive call. However, the local variables
|
|
|
805 from multiple calls now share the same location, so the virtual ssa form
|
|
|
806 requires us to say that the location dies on further iterations of the loop,
|
|
|
807 which requires adding phi nodes.
|
|
|
808 */
|
|
|
809 static void
|
|
|
810 add_virtual_phis (void)
|
|
|
811 {
|
|
|
812 referenced_var_iterator rvi;
|
|
|
813 tree var;
|
|
|
814
|
|
|
815 /* The problematic part is that there is no way how to know what
|
|
|
816 to put into phi nodes (there in fact does not have to be such
|
|
|
817 ssa name available). A solution would be to have an artificial
|
|
|
818 use/kill for all virtual operands in EXIT node. Unless we have
|
|
|
819 this, we cannot do much better than to rebuild the ssa form for
|
|
|
820 possibly affected virtual ssa names from scratch. */
|
|
|
821
|
|
|
822 FOR_EACH_REFERENCED_VAR (var, rvi)
|
|
|
823 {
|
|
|
824 if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
|
|
|
825 mark_sym_for_renaming (var);
|
|
|
826 }
|
|
|
827 }
|
|
|
828
|
|
|
829 /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
|
|
|
830 mark the tailcalls for the sibcall optimization. */
|
|
|
831
|
|
|
832 static bool
|
|
|
833 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
|
|
|
834 {
|
|
|
835 if (t->tail_recursion)
|
|
|
836 {
|
|
|
837 eliminate_tail_call (t);
|
|
|
838 return true;
|
|
|
839 }
|
|
|
840
|
|
|
841 if (opt_tailcalls)
|
|
|
842 {
|
|
|
843 gimple stmt = gsi_stmt (t->call_gsi);
|
|
|
844
|
|
|
845 gimple_call_set_tail (stmt, true);
|
|
|
846 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
847 {
|
|
|
848 fprintf (dump_file, "Found tail call ");
|
|
|
849 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
|
|
|
850 fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
|
|
|
851 }
|
|
|
852 }
|
|
|
853
|
|
|
854 return false;
|
|
|
855 }
|
|
|
856
|
|
|
857 /* Creates a tail-call accumulator of the same type as the return type of the
|
|
|
858 current function. LABEL is the name used to creating the temporary
|
|
|
859 variable for the accumulator. The accumulator will be inserted in the
|
|
|
860 phis of a basic block BB with single predecessor with an initial value
|
|
|
861 INIT converted to the current function return type. */
|
|
|
862
|
|
|
863 static tree
|
|
|
864 create_tailcall_accumulator (const char *label, basic_block bb, tree init)
|
|
|
865 {
|
|
|
866 tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
|
|
|
867 tree tmp = create_tmp_var (ret_type, label);
|
|
|
868 gimple phi;
|
|
|
869
|
|
|
870 add_referenced_var (tmp);
|
|
|
871 phi = create_phi_node (tmp, bb);
|
|
|
872 /* RET_TYPE can be a float when -ffast-maths is enabled. */
|
|
|
873 add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb));
|
|
|
874 return PHI_RESULT (phi);
|
|
|
875 }
|
|
|
876
|
|
|
877 /* Optimizes tail calls in the function, turning the tail recursion
|
|
|
878 into iteration. */
|
|
|
879
|
|
|
880 static unsigned int
|
|
|
881 tree_optimize_tail_calls_1 (bool opt_tailcalls)
|
|
|
882 {
|
|
|
883 edge e;
|
|
|
884 bool phis_constructed = false;
|
|
|
885 struct tailcall *tailcalls = NULL, *act, *next;
|
|
|
886 bool changed = false;
|
|
|
887 basic_block first = single_succ (ENTRY_BLOCK_PTR);
|
|
|
888 tree param;
|
|
|
889 gimple stmt;
|
|
|
890 edge_iterator ei;
|
|
|
891
|
|
|
892 if (!suitable_for_tail_opt_p ())
|
|
|
893 return 0;
|
|
|
894 if (opt_tailcalls)
|
|
|
895 opt_tailcalls = suitable_for_tail_call_opt_p ();
|
|
|
896
|
|
|
897 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
|
|
|
898 {
|
|
|
899 /* Only traverse the normal exits, i.e. those that end with return
|
|
|
900 statement. */
|
|
|
901 stmt = last_stmt (e->src);
|
|
|
902
|
|
|
903 if (stmt
|
|
|
904 && gimple_code (stmt) == GIMPLE_RETURN)
|
|
|
905 find_tail_calls (e->src, &tailcalls);
|
|
|
906 }
|
|
|
907
|
|
|
908 /* Construct the phi nodes and accumulators if necessary. */
|
|
|
909 a_acc = m_acc = NULL_TREE;
|
|
|
910 for (act = tailcalls; act; act = act->next)
|
|
|
911 {
|
|
|
912 if (!act->tail_recursion)
|
|
|
913 continue;
|
|
|
914
|
|
|
915 if (!phis_constructed)
|
|
|
916 {
|
|
|
917 /* Ensure that there is only one predecessor of the block. */
|
|
|
918 if (!single_pred_p (first))
|
|
|
919 first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
|
|
|
920
|
|
|
921 /* Copy the args if needed. */
|
|
|
922 for (param = DECL_ARGUMENTS (current_function_decl);
|
|
|
923 param;
|
|
|
924 param = TREE_CHAIN (param))
|
|
|
925 if (arg_needs_copy_p (param))
|
|
|
926 {
|
|
|
927 tree name = gimple_default_def (cfun, param);
|
|
|
928 tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
|
|
|
929 gimple phi;
|
|
|
930
|
|
|
931 set_default_def (param, new_name);
|
|
|
932 phi = create_phi_node (name, first);
|
|
|
933 SSA_NAME_DEF_STMT (name) = phi;
|
|
|
934 add_phi_arg (phi, new_name, single_pred_edge (first));
|
|
|
935 }
|
|
|
936 phis_constructed = true;
|
|
|
937 }
|
|
|
938
|
|
|
939 if (act->add && !a_acc)
|
|
|
940 a_acc = create_tailcall_accumulator ("add_acc", first,
|
|
|
941 integer_zero_node);
|
|
|
942
|
|
|
943 if (act->mult && !m_acc)
|
|
|
944 m_acc = create_tailcall_accumulator ("mult_acc", first,
|
|
|
945 integer_one_node);
|
|
|
946 }
|
|
|
947
|
|
|
948 for (; tailcalls; tailcalls = next)
|
|
|
949 {
|
|
|
950 next = tailcalls->next;
|
|
|
951 changed |= optimize_tail_call (tailcalls, opt_tailcalls);
|
|
|
952 free (tailcalls);
|
|
|
953 }
|
|
|
954
|
|
|
955 if (a_acc || m_acc)
|
|
|
956 {
|
|
|
957 /* Modify the remaining return statements. */
|
|
|
958 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
|
|
|
959 {
|
|
|
960 stmt = last_stmt (e->src);
|
|
|
961
|
|
|
962 if (stmt
|
|
|
963 && gimple_code (stmt) == GIMPLE_RETURN)
|
|
|
964 adjust_return_value (e->src, m_acc, a_acc);
|
|
|
965 }
|
|
|
966 }
|
|
|
967
|
|
|
968 if (changed)
|
|
|
969 free_dominance_info (CDI_DOMINATORS);
|
|
|
970
|
|
|
971 if (phis_constructed)
|
|
|
972 add_virtual_phis ();
|
|
|
973 if (changed)
|
|
|
974 return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
|
|
|
975 return 0;
|
|
|
976 }
|
|
|
977
|
|
|
978 static unsigned int
|
|
|
979 execute_tail_recursion (void)
|
|
|
980 {
|
|
|
981 return tree_optimize_tail_calls_1 (false);
|
|
|
982 }
|
|
|
983
|
|
|
984 static bool
|
|
|
985 gate_tail_calls (void)
|
|
|
986 {
|
|
|
987 return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
|
|
|
988 }
|
|
|
989
|
|
|
990 static unsigned int
|
|
|
991 execute_tail_calls (void)
|
|
|
992 {
|
|
|
993 return tree_optimize_tail_calls_1 (true);
|
|
|
994 }
|
|
|
995
|
|
|
996 struct gimple_opt_pass pass_tail_recursion =
|
|
|
997 {
|
|
|
998 {
|
|
|
999 GIMPLE_PASS,
|
|
|
1000 "tailr", /* name */
|
|
|
1001 gate_tail_calls, /* gate */
|
|
|
1002 execute_tail_recursion, /* execute */
|
|
|
1003 NULL, /* sub */
|
|
|
1004 NULL, /* next */
|
|
|
1005 0, /* static_pass_number */
|
|
|
1006 0, /* tv_id */
|
|
|
1007 PROP_cfg | PROP_ssa, /* properties_required */
|
|
|
1008 0, /* properties_provided */
|
|
|
1009 0, /* properties_destroyed */
|
|
|
1010 0, /* todo_flags_start */
|
|
|
1011 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
|
|
|
1012 }
|
|
|
1013 };
|
|
|
1014
|
|
|
1015 struct gimple_opt_pass pass_tail_calls =
|
|
|
1016 {
|
|
|
1017 {
|
|
|
1018 GIMPLE_PASS,
|
|
|
1019 "tailc", /* name */
|
|
|
1020 gate_tail_calls, /* gate */
|
|
|
1021 execute_tail_calls, /* execute */
|
|
|
1022 NULL, /* sub */
|
|
|
1023 NULL, /* next */
|
|
|
1024 0, /* static_pass_number */
|
|
|
1025 0, /* tv_id */
|
|
|
1026 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
|
|
|
1027 0, /* properties_provided */
|
|
|
1028 0, /* properties_destroyed */
|
|
|
1029 0, /* todo_flags_start */
|
|
|
1030 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
|
|
|
1031 }
|
|
|
1032 };
|
