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