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