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