]>
Commit | Line | Data |
---|---|---|
588d3ade | 1 | /* Control and data flow functions for trees. |
1574ef13 | 2 | Copyright 2001, 2002 Free Software Foundation, Inc. |
588d3ade AO |
3 | Contributed by Alexandre Oliva <aoliva@redhat.com> |
4 | ||
5 | This file is part of GNU CC. | |
6 | ||
7 | GNU CC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 2, or (at your option) | |
10 | any later version. | |
11 | ||
12 | GNU CC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GNU CC; see the file COPYING. If not, write to | |
19 | the Free Software Foundation, 59 Temple Place - Suite 330, | |
20 | Boston, MA 02111-1307, USA. */ | |
21 | ||
22 | #include "config.h" | |
23 | #include "system.h" | |
69dcadff | 24 | #include "toplev.h" |
588d3ade AO |
25 | #include "tree.h" |
26 | #include "tree-inline.h" | |
d4e4baa9 AO |
27 | #include "rtl.h" |
28 | #include "expr.h" | |
29 | #include "flags.h" | |
30 | #include "params.h" | |
31 | #include "input.h" | |
32 | #include "insn-config.h" | |
33 | #include "integrate.h" | |
34 | #include "varray.h" | |
35 | #include "hashtab.h" | |
36 | #include "splay-tree.h" | |
d23c55c2 | 37 | #include "langhooks.h" |
d4e4baa9 AO |
38 | |
39 | /* This should be eventually be generalized to other languages, but | |
40 | this would require a shared function-as-trees infrastructure. */ | |
d92b4486 | 41 | #include "c-common.h" |
588d3ade | 42 | |
588d3ade | 43 | /* 0 if we should not perform inlining. |
d92b4486 KH |
44 | 1 if we should expand functions calls inline at the tree level. |
45 | 2 if we should consider *all* functions to be inline | |
588d3ade AO |
46 | candidates. */ |
47 | ||
48 | int flag_inline_trees = 0; | |
d4e4baa9 AO |
49 | |
50 | /* To Do: | |
51 | ||
52 | o In order to make inlining-on-trees work, we pessimized | |
53 | function-local static constants. In particular, they are now | |
54 | always output, even when not addressed. Fix this by treating | |
55 | function-local static constants just like global static | |
56 | constants; the back-end already knows not to output them if they | |
57 | are not needed. | |
58 | ||
59 | o Provide heuristics to clamp inlining of recursive template | |
60 | calls? */ | |
61 | ||
62 | /* Data required for function inlining. */ | |
63 | ||
64 | typedef struct inline_data | |
65 | { | |
66 | /* A stack of the functions we are inlining. For example, if we are | |
67 | compiling `f', which calls `g', which calls `h', and we are | |
68 | inlining the body of `h', the stack will contain, `h', followed | |
69 | by `g', followed by `f'. The first few elements of the stack may | |
70 | contain other functions that we know we should not recurse into, | |
71 | even though they are not directly being inlined. */ | |
72 | varray_type fns; | |
73 | /* The index of the first element of FNS that really represents an | |
74 | inlined function. */ | |
75 | unsigned first_inlined_fn; | |
76 | /* The label to jump to when a return statement is encountered. If | |
77 | this value is NULL, then return statements will simply be | |
78 | remapped as return statements, rather than as jumps. */ | |
79 | tree ret_label; | |
80 | /* The map from local declarations in the inlined function to | |
81 | equivalents in the function into which it is being inlined. */ | |
82 | splay_tree decl_map; | |
83 | /* Nonzero if we are currently within the cleanup for a | |
84 | TARGET_EXPR. */ | |
85 | int in_target_cleanup_p; | |
86 | /* A stack of the TARGET_EXPRs that we are currently processing. */ | |
87 | varray_type target_exprs; | |
88 | /* A list of the functions current function has inlined. */ | |
89 | varray_type inlined_fns; | |
90 | /* The approximate number of statements we have inlined in the | |
91 | current call stack. */ | |
92 | int inlined_stmts; | |
93 | /* We use the same mechanism to build clones that we do to perform | |
94 | inlining. However, there are a few places where we need to | |
95 | distinguish between those two situations. This flag is true if | |
96 | we are cloning, rather than inlining. */ | |
97 | bool cloning_p; | |
98 | /* Hash table used to prevent walk_tree from visiting the same node | |
99 | umpteen million times. */ | |
100 | htab_t tree_pruner; | |
101 | } inline_data; | |
102 | ||
103 | /* Prototypes. */ | |
104 | ||
105 | static tree initialize_inlined_parameters PARAMS ((inline_data *, tree, tree)); | |
106 | static tree declare_return_variable PARAMS ((inline_data *, tree *)); | |
107 | static tree copy_body_r PARAMS ((tree *, int *, void *)); | |
108 | static tree copy_body PARAMS ((inline_data *)); | |
109 | static tree expand_call_inline PARAMS ((tree *, int *, void *)); | |
110 | static void expand_calls_inline PARAMS ((tree *, inline_data *)); | |
111 | static int inlinable_function_p PARAMS ((tree, inline_data *)); | |
112 | static tree remap_decl PARAMS ((tree, inline_data *)); | |
113 | static void remap_block PARAMS ((tree, tree, inline_data *)); | |
114 | static void copy_scope_stmt PARAMS ((tree *, int *, inline_data *)); | |
115 | ||
116 | /* The approximate number of instructions per statement. This number | |
117 | need not be particularly accurate; it is used only to make | |
118 | decisions about when a function is too big to inline. */ | |
119 | #define INSNS_PER_STMT (10) | |
120 | ||
121 | /* Remap DECL during the copying of the BLOCK tree for the function. */ | |
122 | ||
123 | static tree | |
124 | remap_decl (decl, id) | |
125 | tree decl; | |
126 | inline_data *id; | |
127 | { | |
128 | splay_tree_node n; | |
129 | tree fn; | |
130 | ||
131 | /* We only remap local variables in the current function. */ | |
132 | fn = VARRAY_TOP_TREE (id->fns); | |
69dcadff | 133 | if (! (*lang_hooks.tree_inlining.auto_var_in_fn_p) (decl, fn)) |
d4e4baa9 AO |
134 | return NULL_TREE; |
135 | ||
136 | /* See if we have remapped this declaration. */ | |
137 | n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl); | |
138 | /* If we didn't already have an equivalent for this declaration, | |
139 | create one now. */ | |
140 | if (!n) | |
141 | { | |
142 | tree t; | |
143 | ||
144 | /* Make a copy of the variable or label. */ | |
145 | t = copy_decl_for_inlining (decl, fn, | |
146 | VARRAY_TREE (id->fns, 0)); | |
147 | ||
148 | /* The decl T could be a dynamic array or other variable size type, | |
149 | in which case some fields need to be remapped because they may | |
150 | contain SAVE_EXPRs. */ | |
d4e4baa9 AO |
151 | if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE |
152 | && TYPE_DOMAIN (TREE_TYPE (t))) | |
153 | { | |
154 | TREE_TYPE (t) = copy_node (TREE_TYPE (t)); | |
155 | TYPE_DOMAIN (TREE_TYPE (t)) | |
156 | = copy_node (TYPE_DOMAIN (TREE_TYPE (t))); | |
157 | walk_tree (&TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (t))), | |
158 | copy_body_r, id, NULL); | |
159 | } | |
160 | ||
161 | if (! DECL_NAME (t) && TREE_TYPE (t) | |
69dcadff | 162 | && (*lang_hooks.tree_inlining.anon_aggr_type_p) (TREE_TYPE (t))) |
d4e4baa9 AO |
163 | { |
164 | /* For a VAR_DECL of anonymous type, we must also copy the | |
165 | member VAR_DECLS here and rechain the | |
2ba84f36 | 166 | DECL_ANON_UNION_ELEMS. */ |
d4e4baa9 AO |
167 | tree members = NULL; |
168 | tree src; | |
d92b4486 | 169 | |
d4e4baa9 AO |
170 | for (src = DECL_ANON_UNION_ELEMS (t); src; |
171 | src = TREE_CHAIN (src)) | |
172 | { | |
173 | tree member = remap_decl (TREE_VALUE (src), id); | |
174 | ||
175 | if (TREE_PURPOSE (src)) | |
176 | abort (); | |
177 | members = tree_cons (NULL, member, members); | |
178 | } | |
179 | DECL_ANON_UNION_ELEMS (t) = nreverse (members); | |
180 | } | |
d92b4486 | 181 | |
d4e4baa9 AO |
182 | /* Remember it, so that if we encounter this local entity |
183 | again we can reuse this copy. */ | |
184 | n = splay_tree_insert (id->decl_map, | |
185 | (splay_tree_key) decl, | |
186 | (splay_tree_value) t); | |
187 | } | |
188 | ||
189 | return (tree) n->value; | |
190 | } | |
191 | ||
192 | /* Copy the SCOPE_STMT_BLOCK associated with SCOPE_STMT to contain | |
193 | remapped versions of the variables therein. And hook the new block | |
194 | into the block-tree. If non-NULL, the DECLS are declarations to | |
195 | add to use instead of the BLOCK_VARS in the old block. */ | |
196 | ||
197 | static void | |
198 | remap_block (scope_stmt, decls, id) | |
199 | tree scope_stmt; | |
200 | tree decls; | |
201 | inline_data *id; | |
202 | { | |
203 | /* We cannot do this in the cleanup for a TARGET_EXPR since we do | |
204 | not know whether or not expand_expr will actually write out the | |
205 | code we put there. If it does not, then we'll have more BLOCKs | |
206 | than block-notes, and things will go awry. At some point, we | |
207 | should make the back-end handle BLOCK notes in a tidier way, | |
208 | without requiring a strict correspondence to the block-tree; then | |
209 | this check can go. */ | |
210 | if (id->in_target_cleanup_p) | |
211 | { | |
212 | SCOPE_STMT_BLOCK (scope_stmt) = NULL_TREE; | |
213 | return; | |
214 | } | |
215 | ||
216 | /* If this is the beginning of a scope, remap the associated BLOCK. */ | |
217 | if (SCOPE_BEGIN_P (scope_stmt) && SCOPE_STMT_BLOCK (scope_stmt)) | |
218 | { | |
219 | tree old_block; | |
220 | tree new_block; | |
221 | tree old_var; | |
222 | tree fn; | |
223 | ||
224 | /* Make the new block. */ | |
225 | old_block = SCOPE_STMT_BLOCK (scope_stmt); | |
226 | new_block = make_node (BLOCK); | |
227 | TREE_USED (new_block) = TREE_USED (old_block); | |
228 | BLOCK_ABSTRACT_ORIGIN (new_block) = old_block; | |
229 | SCOPE_STMT_BLOCK (scope_stmt) = new_block; | |
230 | ||
231 | /* Remap its variables. */ | |
232 | for (old_var = decls ? decls : BLOCK_VARS (old_block); | |
233 | old_var; | |
234 | old_var = TREE_CHAIN (old_var)) | |
235 | { | |
236 | tree new_var; | |
237 | ||
238 | /* Remap the variable. */ | |
239 | new_var = remap_decl (old_var, id); | |
240 | /* If we didn't remap this variable, so we can't mess with | |
241 | its TREE_CHAIN. If we remapped this variable to | |
242 | something other than a declaration (say, if we mapped it | |
243 | to a constant), then we must similarly omit any mention | |
244 | of it here. */ | |
245 | if (!new_var || !DECL_P (new_var)) | |
246 | ; | |
247 | else | |
248 | { | |
249 | TREE_CHAIN (new_var) = BLOCK_VARS (new_block); | |
250 | BLOCK_VARS (new_block) = new_var; | |
251 | } | |
252 | } | |
253 | /* We put the BLOCK_VARS in reverse order; fix that now. */ | |
254 | BLOCK_VARS (new_block) = nreverse (BLOCK_VARS (new_block)); | |
255 | fn = VARRAY_TREE (id->fns, 0); | |
256 | if (id->cloning_p) | |
257 | /* We're building a clone; DECL_INITIAL is still | |
258 | error_mark_node, and current_binding_level is the parm | |
259 | binding level. */ | |
43577e6b | 260 | (*lang_hooks.decls.insert_block) (new_block); |
d4e4baa9 AO |
261 | else |
262 | { | |
263 | /* Attach this new block after the DECL_INITIAL block for the | |
264 | function into which this block is being inlined. In | |
265 | rest_of_compilation we will straighten out the BLOCK tree. */ | |
266 | tree *first_block; | |
267 | if (DECL_INITIAL (fn)) | |
268 | first_block = &BLOCK_CHAIN (DECL_INITIAL (fn)); | |
269 | else | |
270 | first_block = &DECL_INITIAL (fn); | |
271 | BLOCK_CHAIN (new_block) = *first_block; | |
272 | *first_block = new_block; | |
273 | } | |
274 | /* Remember the remapped block. */ | |
275 | splay_tree_insert (id->decl_map, | |
276 | (splay_tree_key) old_block, | |
277 | (splay_tree_value) new_block); | |
278 | } | |
279 | /* If this is the end of a scope, set the SCOPE_STMT_BLOCK to be the | |
280 | remapped block. */ | |
281 | else if (SCOPE_END_P (scope_stmt) && SCOPE_STMT_BLOCK (scope_stmt)) | |
282 | { | |
283 | splay_tree_node n; | |
284 | ||
285 | /* Find this block in the table of remapped things. */ | |
286 | n = splay_tree_lookup (id->decl_map, | |
287 | (splay_tree_key) SCOPE_STMT_BLOCK (scope_stmt)); | |
288 | if (! n) | |
289 | abort (); | |
290 | SCOPE_STMT_BLOCK (scope_stmt) = (tree) n->value; | |
291 | } | |
292 | } | |
293 | ||
294 | /* Copy the SCOPE_STMT pointed to by TP. */ | |
295 | ||
296 | static void | |
297 | copy_scope_stmt (tp, walk_subtrees, id) | |
298 | tree *tp; | |
299 | int *walk_subtrees; | |
300 | inline_data *id; | |
301 | { | |
302 | tree block; | |
303 | ||
304 | /* Remember whether or not this statement was nullified. When | |
305 | making a copy, copy_tree_r always sets SCOPE_NULLIFIED_P (and | |
306 | doesn't copy the SCOPE_STMT_BLOCK) to free callers from having to | |
307 | deal with copying BLOCKs if they do not wish to do so. */ | |
308 | block = SCOPE_STMT_BLOCK (*tp); | |
309 | /* Copy (and replace) the statement. */ | |
310 | copy_tree_r (tp, walk_subtrees, NULL); | |
311 | /* Restore the SCOPE_STMT_BLOCK. */ | |
312 | SCOPE_STMT_BLOCK (*tp) = block; | |
313 | ||
314 | /* Remap the associated block. */ | |
315 | remap_block (*tp, NULL_TREE, id); | |
316 | } | |
317 | ||
318 | /* Called from copy_body via walk_tree. DATA is really an | |
319 | `inline_data *'. */ | |
320 | ||
321 | static tree | |
322 | copy_body_r (tp, walk_subtrees, data) | |
323 | tree *tp; | |
324 | int *walk_subtrees; | |
325 | void *data; | |
326 | { | |
327 | inline_data* id; | |
328 | tree fn; | |
329 | ||
330 | /* Set up. */ | |
331 | id = (inline_data *) data; | |
332 | fn = VARRAY_TOP_TREE (id->fns); | |
333 | ||
334 | #if 0 | |
335 | /* All automatic variables should have a DECL_CONTEXT indicating | |
336 | what function they come from. */ | |
337 | if ((TREE_CODE (*tp) == VAR_DECL || TREE_CODE (*tp) == LABEL_DECL) | |
338 | && DECL_NAMESPACE_SCOPE_P (*tp)) | |
339 | if (! DECL_EXTERNAL (*tp) && ! TREE_STATIC (*tp)) | |
340 | abort (); | |
341 | #endif | |
342 | ||
343 | /* If this is a RETURN_STMT, change it into an EXPR_STMT and a | |
344 | GOTO_STMT with the RET_LABEL as its target. */ | |
345 | if (TREE_CODE (*tp) == RETURN_STMT && id->ret_label) | |
346 | { | |
347 | tree return_stmt = *tp; | |
348 | tree goto_stmt; | |
349 | ||
350 | /* Build the GOTO_STMT. */ | |
351 | goto_stmt = build_stmt (GOTO_STMT, id->ret_label); | |
352 | TREE_CHAIN (goto_stmt) = TREE_CHAIN (return_stmt); | |
db4a8254 | 353 | GOTO_FAKE_P (goto_stmt) = 1; |
d4e4baa9 AO |
354 | |
355 | /* If we're returning something, just turn that into an | |
356 | assignment into the equivalent of the original | |
357 | RESULT_DECL. */ | |
358 | if (RETURN_EXPR (return_stmt)) | |
359 | { | |
360 | *tp = build_stmt (EXPR_STMT, | |
361 | RETURN_EXPR (return_stmt)); | |
362 | STMT_IS_FULL_EXPR_P (*tp) = 1; | |
363 | /* And then jump to the end of the function. */ | |
364 | TREE_CHAIN (*tp) = goto_stmt; | |
365 | } | |
366 | /* If we're not returning anything just do the jump. */ | |
367 | else | |
368 | *tp = goto_stmt; | |
369 | } | |
370 | /* Local variables and labels need to be replaced by equivalent | |
371 | variables. We don't want to copy static variables; there's only | |
372 | one of those, no matter how many times we inline the containing | |
373 | function. */ | |
69dcadff | 374 | else if ((*lang_hooks.tree_inlining.auto_var_in_fn_p) (*tp, fn)) |
d4e4baa9 AO |
375 | { |
376 | tree new_decl; | |
377 | ||
378 | /* Remap the declaration. */ | |
379 | new_decl = remap_decl (*tp, id); | |
380 | if (! new_decl) | |
381 | abort (); | |
382 | /* Replace this variable with the copy. */ | |
383 | STRIP_TYPE_NOPS (new_decl); | |
384 | *tp = new_decl; | |
385 | } | |
386 | #if 0 | |
387 | else if (nonstatic_local_decl_p (*tp) | |
388 | && DECL_CONTEXT (*tp) != VARRAY_TREE (id->fns, 0)) | |
389 | abort (); | |
390 | #endif | |
391 | else if (TREE_CODE (*tp) == SAVE_EXPR) | |
392 | remap_save_expr (tp, id->decl_map, VARRAY_TREE (id->fns, 0), | |
393 | walk_subtrees); | |
394 | else if (TREE_CODE (*tp) == UNSAVE_EXPR) | |
395 | /* UNSAVE_EXPRs should not be generated until expansion time. */ | |
396 | abort (); | |
397 | /* For a SCOPE_STMT, we must copy the associated block so that we | |
398 | can write out debugging information for the inlined variables. */ | |
399 | else if (TREE_CODE (*tp) == SCOPE_STMT && !id->in_target_cleanup_p) | |
400 | copy_scope_stmt (tp, walk_subtrees, id); | |
401 | /* Otherwise, just copy the node. Note that copy_tree_r already | |
402 | knows not to copy VAR_DECLs, etc., so this is safe. */ | |
403 | else | |
404 | { | |
405 | copy_tree_r (tp, walk_subtrees, NULL); | |
406 | ||
407 | /* The copied TARGET_EXPR has never been expanded, even if the | |
408 | original node was expanded already. */ | |
409 | if (TREE_CODE (*tp) == TARGET_EXPR && TREE_OPERAND (*tp, 3)) | |
410 | { | |
411 | TREE_OPERAND (*tp, 1) = TREE_OPERAND (*tp, 3); | |
412 | TREE_OPERAND (*tp, 3) = NULL_TREE; | |
413 | } | |
414 | else if (TREE_CODE (*tp) == MODIFY_EXPR | |
415 | && TREE_OPERAND (*tp, 0) == TREE_OPERAND (*tp, 1) | |
69dcadff AO |
416 | && ((*lang_hooks.tree_inlining.auto_var_in_fn_p) |
417 | (TREE_OPERAND (*tp, 0), fn))) | |
d4e4baa9 AO |
418 | { |
419 | /* Some assignments VAR = VAR; don't generate any rtl code | |
420 | and thus don't count as variable modification. Avoid | |
421 | keeping bogosities like 0 = 0. */ | |
422 | tree decl = TREE_OPERAND (*tp, 0), value; | |
423 | splay_tree_node n; | |
424 | ||
425 | n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl); | |
426 | if (n) | |
427 | { | |
428 | value = (tree) n->value; | |
429 | STRIP_TYPE_NOPS (value); | |
430 | if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value)) | |
431 | *tp = value; | |
432 | } | |
433 | } | |
434 | } | |
435 | ||
436 | /* Keep iterating. */ | |
437 | return NULL_TREE; | |
438 | } | |
439 | ||
440 | /* Make a copy of the body of FN so that it can be inserted inline in | |
441 | another function. */ | |
442 | ||
443 | static tree | |
444 | copy_body (id) | |
445 | inline_data *id; | |
446 | { | |
447 | tree body; | |
448 | ||
449 | body = DECL_SAVED_TREE (VARRAY_TOP_TREE (id->fns)); | |
450 | walk_tree (&body, copy_body_r, id, NULL); | |
451 | ||
452 | return body; | |
453 | } | |
454 | ||
455 | /* Generate code to initialize the parameters of the function at the | |
456 | top of the stack in ID from the ARGS (presented as a TREE_LIST). */ | |
457 | ||
458 | static tree | |
459 | initialize_inlined_parameters (id, args, fn) | |
460 | inline_data *id; | |
461 | tree args; | |
462 | tree fn; | |
463 | { | |
464 | tree init_stmts; | |
465 | tree parms; | |
466 | tree a; | |
467 | tree p; | |
468 | ||
469 | /* Figure out what the parameters are. */ | |
470 | parms = DECL_ARGUMENTS (fn); | |
471 | ||
472 | /* Start with no initializations whatsoever. */ | |
473 | init_stmts = NULL_TREE; | |
474 | ||
475 | /* Loop through the parameter declarations, replacing each with an | |
476 | equivalent VAR_DECL, appropriately initialized. */ | |
4838c5ee AO |
477 | for (p = parms, a = args; p; |
478 | a = a ? TREE_CHAIN (a) : a, p = TREE_CHAIN (p)) | |
d4e4baa9 AO |
479 | { |
480 | tree init_stmt; | |
481 | tree var; | |
482 | tree value; | |
6e4ae815 | 483 | tree cleanup; |
d4e4baa9 AO |
484 | |
485 | /* Find the initializer. */ | |
f735a153 JJ |
486 | value = (*lang_hooks.tree_inlining.convert_parm_for_inlining) |
487 | (p, a ? TREE_VALUE (a) : NULL_TREE, fn); | |
4838c5ee | 488 | |
d4e4baa9 AO |
489 | /* If the parameter is never assigned to, we may not need to |
490 | create a new variable here at all. Instead, we may be able | |
491 | to just use the argument value. */ | |
492 | if (TREE_READONLY (p) | |
493 | && !TREE_ADDRESSABLE (p) | |
4838c5ee | 494 | && value && !TREE_SIDE_EFFECTS (value)) |
d4e4baa9 AO |
495 | { |
496 | /* Simplify the value, if possible. */ | |
4838c5ee | 497 | value = fold (DECL_P (value) ? decl_constant_value (value) : value); |
d4e4baa9 AO |
498 | |
499 | /* We can't risk substituting complex expressions. They | |
500 | might contain variables that will be assigned to later. | |
501 | Theoretically, we could check the expression to see if | |
502 | all of the variables that determine its value are | |
503 | read-only, but we don't bother. */ | |
504 | if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value)) | |
505 | { | |
506 | /* If this is a declaration, wrap it a NOP_EXPR so that | |
507 | we don't try to put the VALUE on the list of | |
508 | BLOCK_VARS. */ | |
509 | if (DECL_P (value)) | |
510 | value = build1 (NOP_EXPR, TREE_TYPE (value), value); | |
511 | ||
512 | splay_tree_insert (id->decl_map, | |
513 | (splay_tree_key) p, | |
514 | (splay_tree_value) value); | |
515 | continue; | |
516 | } | |
517 | } | |
518 | ||
519 | /* Make an equivalent VAR_DECL. */ | |
520 | var = copy_decl_for_inlining (p, fn, VARRAY_TREE (id->fns, 0)); | |
521 | /* Register the VAR_DECL as the equivalent for the PARM_DECL; | |
522 | that way, when the PARM_DECL is encountered, it will be | |
523 | automatically replaced by the VAR_DECL. */ | |
524 | splay_tree_insert (id->decl_map, | |
525 | (splay_tree_key) p, | |
526 | (splay_tree_value) var); | |
527 | ||
528 | /* Declare this new variable. */ | |
529 | init_stmt = build_stmt (DECL_STMT, var); | |
530 | TREE_CHAIN (init_stmt) = init_stmts; | |
531 | init_stmts = init_stmt; | |
532 | ||
533 | /* Initialize this VAR_DECL from the equivalent argument. If | |
534 | the argument is an object, created via a constructor or copy, | |
535 | this will not result in an extra copy: the TARGET_EXPR | |
536 | representing the argument will be bound to VAR, and the | |
537 | object will be constructed in VAR. */ | |
538 | if (! TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p))) | |
539 | DECL_INITIAL (var) = value; | |
540 | else | |
541 | { | |
542 | /* Even if P was TREE_READONLY, the new VAR should not be. | |
543 | In the original code, we would have constructed a | |
544 | temporary, and then the function body would have never | |
545 | changed the value of P. However, now, we will be | |
546 | constructing VAR directly. The constructor body may | |
547 | change its value multiple times as it is being | |
548 | constructed. Therefore, it must not be TREE_READONLY; | |
549 | the back-end assumes that TREE_READONLY variable is | |
550 | assigned to only once. */ | |
551 | TREE_READONLY (var) = 0; | |
552 | ||
553 | /* Build a run-time initialization. */ | |
554 | init_stmt = build_stmt (EXPR_STMT, | |
555 | build (INIT_EXPR, TREE_TYPE (p), | |
556 | var, value)); | |
557 | /* Add this initialization to the list. Note that we want the | |
558 | declaration *after* the initialization because we are going | |
559 | to reverse all the initialization statements below. */ | |
560 | TREE_CHAIN (init_stmt) = init_stmts; | |
561 | init_stmts = init_stmt; | |
562 | } | |
6e4ae815 MM |
563 | |
564 | /* See if we need to clean up the declaration. */ | |
c88770e9 | 565 | cleanup = (*lang_hooks.maybe_build_cleanup) (var); |
d92b4486 | 566 | if (cleanup) |
6e4ae815 MM |
567 | { |
568 | tree cleanup_stmt; | |
569 | /* Build the cleanup statement. */ | |
570 | cleanup_stmt = build_stmt (CLEANUP_STMT, var, cleanup); | |
571 | /* Add it to the *front* of the list; the list will be | |
572 | reversed below. */ | |
573 | TREE_CHAIN (cleanup_stmt) = init_stmts; | |
574 | init_stmts = cleanup_stmt; | |
575 | } | |
d4e4baa9 AO |
576 | } |
577 | ||
4838c5ee AO |
578 | /* Evaluate trailing arguments. */ |
579 | for (; a; a = TREE_CHAIN (a)) | |
580 | { | |
581 | tree init_stmt; | |
6e4ae815 | 582 | tree value = TREE_VALUE (a); |
4838c5ee AO |
583 | |
584 | if (! value || ! TREE_SIDE_EFFECTS (value)) | |
585 | continue; | |
586 | ||
587 | init_stmt = build_stmt (EXPR_STMT, value); | |
588 | TREE_CHAIN (init_stmt) = init_stmts; | |
589 | init_stmts = init_stmt; | |
590 | } | |
591 | ||
d4e4baa9 AO |
592 | /* The initialization statements have been built up in reverse |
593 | order. Straighten them out now. */ | |
594 | return nreverse (init_stmts); | |
595 | } | |
596 | ||
597 | /* Declare a return variable to replace the RESULT_DECL for the | |
598 | function we are calling. An appropriate DECL_STMT is returned. | |
599 | The USE_STMT is filled in to contain a use of the declaration to | |
600 | indicate the return value of the function. */ | |
601 | ||
602 | static tree | |
603 | declare_return_variable (id, use_stmt) | |
604 | struct inline_data *id; | |
605 | tree *use_stmt; | |
606 | { | |
607 | tree fn = VARRAY_TOP_TREE (id->fns); | |
608 | tree result = DECL_RESULT (fn); | |
609 | tree var; | |
610 | int need_return_decl = 1; | |
611 | ||
612 | /* We don't need to do anything for functions that don't return | |
613 | anything. */ | |
614 | if (!result || VOID_TYPE_P (TREE_TYPE (result))) | |
615 | { | |
616 | *use_stmt = NULL_TREE; | |
617 | return NULL_TREE; | |
618 | } | |
619 | ||
69dcadff AO |
620 | var = ((*lang_hooks.tree_inlining.copy_res_decl_for_inlining) |
621 | (result, fn, VARRAY_TREE (id->fns, 0), id->decl_map, | |
622 | &need_return_decl, &id->target_exprs)); | |
d4e4baa9 AO |
623 | |
624 | /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that | |
625 | way, when the RESULT_DECL is encountered, it will be | |
626 | automatically replaced by the VAR_DECL. */ | |
627 | splay_tree_insert (id->decl_map, | |
628 | (splay_tree_key) result, | |
629 | (splay_tree_value) var); | |
630 | ||
4838c5ee AO |
631 | /* Build the USE_STMT. If the return type of the function was |
632 | promoted, convert it back to the expected type. */ | |
633 | if (TREE_TYPE (var) == TREE_TYPE (TREE_TYPE (fn))) | |
634 | *use_stmt = build_stmt (EXPR_STMT, var); | |
635 | else | |
636 | *use_stmt = build_stmt (EXPR_STMT, | |
637 | build1 (NOP_EXPR, TREE_TYPE (TREE_TYPE (fn)), | |
638 | var)); | |
1574ef13 AO |
639 | |
640 | TREE_ADDRESSABLE (*use_stmt) = 1; | |
641 | ||
d4e4baa9 AO |
642 | /* Build the declaration statement if FN does not return an |
643 | aggregate. */ | |
644 | if (need_return_decl) | |
645 | return build_stmt (DECL_STMT, var); | |
646 | /* If FN does return an aggregate, there's no need to declare the | |
647 | return variable; we're using a variable in our caller's frame. */ | |
648 | else | |
649 | return NULL_TREE; | |
650 | } | |
651 | ||
4838c5ee AO |
652 | /* Returns non-zero if a function can be inlined as a tree. */ |
653 | ||
654 | int | |
655 | tree_inlinable_function_p (fn) | |
656 | tree fn; | |
657 | { | |
658 | return inlinable_function_p (fn, NULL); | |
659 | } | |
660 | ||
661 | /* Returns non-zero if FN is a function that can be inlined into the | |
662 | inlining context ID_. If ID_ is NULL, check whether the function | |
663 | can be inlined at all. */ | |
d4e4baa9 AO |
664 | |
665 | static int | |
666 | inlinable_function_p (fn, id) | |
667 | tree fn; | |
668 | inline_data *id; | |
669 | { | |
670 | int inlinable; | |
a6227154 | 671 | int currfn_insns; |
d4e4baa9 AO |
672 | |
673 | /* If we've already decided this function shouldn't be inlined, | |
674 | there's no need to check again. */ | |
675 | if (DECL_UNINLINABLE (fn)) | |
676 | return 0; | |
677 | ||
678 | /* Assume it is not inlinable. */ | |
679 | inlinable = 0; | |
d92b4486 | 680 | |
1eeeb6a4 | 681 | /* The number of instructions (estimated) of current function. */ |
a6227154 | 682 | currfn_insns = DECL_NUM_STMTS (fn) * INSNS_PER_STMT; |
d4e4baa9 AO |
683 | |
684 | /* If we're not inlining things, then nothing is inlinable. */ | |
4838c5ee | 685 | if (! flag_inline_trees) |
d4e4baa9 | 686 | ; |
4838c5ee | 687 | /* If we're not inlining all functions and the function was not |
e95301f5 AO |
688 | declared `inline', we don't inline it. Don't think of |
689 | disregarding DECL_INLINE when flag_inline_trees == 2; it's the | |
690 | front-end that must set DECL_INLINE in this case, because | |
691 | dwarf2out loses if a function is inlined that doesn't have | |
692 | DECL_INLINE set. */ | |
693 | else if (! DECL_INLINE (fn)) | |
d4e4baa9 AO |
694 | ; |
695 | /* We can't inline functions that are too big. Only allow a single | |
d92b4486 | 696 | function to be of MAX_INLINE_INSNS_SINGLE size. Make special |
a6227154 | 697 | allowance for extern inline functions, though. */ |
69dcadff | 698 | else if (! (*lang_hooks.tree_inlining.disregard_inline_limits) (fn) |
a6227154 | 699 | && currfn_insns > MAX_INLINE_INSNS_SINGLE) |
d4e4baa9 AO |
700 | ; |
701 | /* All is well. We can inline this function. Traditionally, GCC | |
702 | has refused to inline functions using alloca, or functions whose | |
703 | values are returned in a PARALLEL, and a few other such obscure | |
704 | conditions. We are not equally constrained at the tree level. */ | |
705 | else | |
706 | inlinable = 1; | |
707 | ||
708 | /* Squirrel away the result so that we don't have to check again. */ | |
4838c5ee | 709 | DECL_UNINLINABLE (fn) = ! inlinable; |
d4e4baa9 | 710 | |
a6227154 | 711 | /* In case we don't disregard the inlining limits and we basically |
1eeeb6a4 | 712 | can inline this function, investigate further. */ |
69dcadff | 713 | if (! (*lang_hooks.tree_inlining.disregard_inline_limits) (fn) |
a6227154 | 714 | && inlinable) |
d92b4486 | 715 | { |
a6227154 KG |
716 | int sum_insns = (id ? id->inlined_stmts : 0) * INSNS_PER_STMT |
717 | + currfn_insns; | |
718 | /* In the extreme case that we have exceeded the recursive inlining | |
719 | limit by a huge factor (128), we just say no. Should not happen | |
1eeeb6a4 | 720 | in real life. */ |
a6227154 KG |
721 | if (sum_insns > MAX_INLINE_INSNS * 128) |
722 | inlinable = 0; | |
723 | /* If we did not hit the extreme limit, we use a linear function | |
724 | with slope -1/MAX_INLINE_SLOPE to exceedingly decrease the | |
725 | allowable size. We always allow a size of MIN_INLINE_INSNS | |
1eeeb6a4 | 726 | though. */ |
a6227154 KG |
727 | else if ((sum_insns > MAX_INLINE_INSNS) |
728 | && (currfn_insns > MIN_INLINE_INSNS)) | |
d92b4486 | 729 | { |
a6227154 KG |
730 | int max_curr = MAX_INLINE_INSNS_SINGLE |
731 | - (sum_insns - MAX_INLINE_INSNS) / MAX_INLINE_SLOPE; | |
732 | if (currfn_insns > max_curr) | |
733 | inlinable = 0; | |
734 | } | |
735 | } | |
d4e4baa9 | 736 | |
69dcadff | 737 | if (inlinable && (*lang_hooks.tree_inlining.cannot_inline_tree_fn) (&fn)) |
d4e4baa9 | 738 | inlinable = 0; |
d92b4486 | 739 | |
d4e4baa9 AO |
740 | /* If we don't have the function body available, we can't inline |
741 | it. */ | |
4838c5ee | 742 | if (! DECL_SAVED_TREE (fn)) |
d4e4baa9 AO |
743 | inlinable = 0; |
744 | ||
745 | /* Check again, language hooks may have modified it. */ | |
746 | if (! inlinable || DECL_UNINLINABLE (fn)) | |
747 | return 0; | |
748 | ||
749 | /* Don't do recursive inlining, either. We don't record this in | |
750 | DECL_UNINLINABLE; we may be able to inline this function later. */ | |
4838c5ee | 751 | if (id) |
d4e4baa9 AO |
752 | { |
753 | size_t i; | |
754 | ||
755 | for (i = 0; i < VARRAY_ACTIVE_SIZE (id->fns); ++i) | |
756 | if (VARRAY_TREE (id->fns, i) == fn) | |
757 | return 0; | |
758 | ||
4838c5ee | 759 | if (DECL_INLINED_FNS (fn)) |
d4e4baa9 AO |
760 | { |
761 | int j; | |
762 | tree inlined_fns = DECL_INLINED_FNS (fn); | |
763 | ||
764 | for (j = 0; j < TREE_VEC_LENGTH (inlined_fns); ++j) | |
765 | if (TREE_VEC_ELT (inlined_fns, j) == VARRAY_TREE (id->fns, 0)) | |
766 | return 0; | |
767 | } | |
768 | } | |
769 | ||
770 | /* Return the result. */ | |
771 | return inlinable; | |
772 | } | |
773 | ||
774 | /* If *TP is a CALL_EXPR, replace it with its inline expansion. */ | |
775 | ||
776 | static tree | |
777 | expand_call_inline (tp, walk_subtrees, data) | |
778 | tree *tp; | |
779 | int *walk_subtrees; | |
780 | void *data; | |
781 | { | |
782 | inline_data *id; | |
783 | tree t; | |
784 | tree expr; | |
785 | tree chain; | |
786 | tree fn; | |
787 | tree scope_stmt; | |
788 | tree use_stmt; | |
789 | tree arg_inits; | |
790 | tree *inlined_body; | |
791 | splay_tree st; | |
792 | ||
793 | /* See what we've got. */ | |
794 | id = (inline_data *) data; | |
795 | t = *tp; | |
796 | ||
797 | /* Recurse, but letting recursive invocations know that we are | |
798 | inside the body of a TARGET_EXPR. */ | |
799 | if (TREE_CODE (*tp) == TARGET_EXPR) | |
800 | { | |
801 | int i, len = first_rtl_op (TARGET_EXPR); | |
802 | ||
803 | /* We're walking our own subtrees. */ | |
804 | *walk_subtrees = 0; | |
805 | ||
806 | /* Push *TP on the stack of pending TARGET_EXPRs. */ | |
807 | VARRAY_PUSH_TREE (id->target_exprs, *tp); | |
808 | ||
809 | /* Actually walk over them. This loop is the body of | |
810 | walk_trees, omitting the case where the TARGET_EXPR | |
811 | itself is handled. */ | |
812 | for (i = 0; i < len; ++i) | |
813 | { | |
814 | if (i == 2) | |
815 | ++id->in_target_cleanup_p; | |
816 | walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data, | |
817 | id->tree_pruner); | |
818 | if (i == 2) | |
819 | --id->in_target_cleanup_p; | |
820 | } | |
821 | ||
822 | /* We're done with this TARGET_EXPR now. */ | |
823 | VARRAY_POP (id->target_exprs); | |
824 | ||
825 | return NULL_TREE; | |
826 | } | |
827 | ||
828 | if (TYPE_P (t)) | |
829 | /* Because types were not copied in copy_body, CALL_EXPRs beneath | |
830 | them should not be expanded. This can happen if the type is a | |
831 | dynamic array type, for example. */ | |
832 | *walk_subtrees = 0; | |
833 | ||
834 | /* From here on, we're only interested in CALL_EXPRs. */ | |
835 | if (TREE_CODE (t) != CALL_EXPR) | |
836 | return NULL_TREE; | |
837 | ||
838 | /* First, see if we can figure out what function is being called. | |
839 | If we cannot, then there is no hope of inlining the function. */ | |
840 | fn = get_callee_fndecl (t); | |
841 | if (!fn) | |
842 | return NULL_TREE; | |
843 | ||
a1a0fd4e AO |
844 | /* If fn is a declaration of a function in a nested scope that was |
845 | globally declared inline, we don't set its DECL_INITIAL. | |
846 | However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the | |
847 | C++ front-end uses it for cdtors to refer to their internal | |
848 | declarations, that are not real functions. Fortunately those | |
849 | don't have trees to be saved, so we can tell by checking their | |
850 | DECL_SAVED_TREE. */ | |
851 | if (! DECL_INITIAL (fn) | |
852 | && DECL_ABSTRACT_ORIGIN (fn) | |
853 | && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn))) | |
854 | fn = DECL_ABSTRACT_ORIGIN (fn); | |
855 | ||
d4e4baa9 AO |
856 | /* Don't try to inline functions that are not well-suited to |
857 | inlining. */ | |
858 | if (!inlinable_function_p (fn, id)) | |
859 | return NULL_TREE; | |
860 | ||
742a37d5 JM |
861 | if (! (*lang_hooks.tree_inlining.start_inlining) (fn)) |
862 | return NULL_TREE; | |
863 | ||
d4e4baa9 AO |
864 | /* Set the current filename and line number to the function we are |
865 | inlining so that when we create new _STMT nodes here they get | |
866 | line numbers corresponding to the function we are calling. We | |
867 | wrap the whole inlined body in an EXPR_WITH_FILE_AND_LINE as well | |
868 | because individual statements don't record the filename. */ | |
869 | push_srcloc (fn->decl.filename, fn->decl.linenum); | |
870 | ||
871 | /* Build a statement-expression containing code to initialize the | |
872 | arguments, the actual inline expansion of the body, and a label | |
873 | for the return statements within the function to jump to. The | |
874 | type of the statement expression is the return type of the | |
875 | function call. */ | |
876 | expr = build1 (STMT_EXPR, TREE_TYPE (TREE_TYPE (fn)), NULL_TREE); | |
b2123dc0 MM |
877 | /* There is no scope associated with the statement-expression. */ |
878 | STMT_EXPR_NO_SCOPE (expr) = 1; | |
d4e4baa9 AO |
879 | |
880 | /* Local declarations will be replaced by their equivalents in this | |
881 | map. */ | |
882 | st = id->decl_map; | |
883 | id->decl_map = splay_tree_new (splay_tree_compare_pointers, | |
884 | NULL, NULL); | |
885 | ||
886 | /* Initialize the parameters. */ | |
887 | arg_inits = initialize_inlined_parameters (id, TREE_OPERAND (t, 1), fn); | |
888 | /* Expand any inlined calls in the initializers. Do this before we | |
889 | push FN on the stack of functions we are inlining; we want to | |
890 | inline calls to FN that appear in the initializers for the | |
891 | parameters. */ | |
892 | expand_calls_inline (&arg_inits, id); | |
893 | /* And add them to the tree. */ | |
894 | STMT_EXPR_STMT (expr) = chainon (STMT_EXPR_STMT (expr), arg_inits); | |
895 | ||
896 | /* Record the function we are about to inline so that we can avoid | |
897 | recursing into it. */ | |
898 | VARRAY_PUSH_TREE (id->fns, fn); | |
899 | ||
900 | /* Record the function we are about to inline if optimize_function | |
901 | has not been called on it yet and we don't have it in the list. */ | |
902 | if (! DECL_INLINED_FNS (fn)) | |
903 | { | |
904 | int i; | |
905 | ||
906 | for (i = VARRAY_ACTIVE_SIZE (id->inlined_fns) - 1; i >= 0; i--) | |
907 | if (VARRAY_TREE (id->inlined_fns, i) == fn) | |
908 | break; | |
909 | if (i < 0) | |
910 | VARRAY_PUSH_TREE (id->inlined_fns, fn); | |
911 | } | |
912 | ||
913 | /* Return statements in the function body will be replaced by jumps | |
914 | to the RET_LABEL. */ | |
915 | id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE); | |
916 | DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0); | |
917 | ||
23700f65 AO |
918 | if (! DECL_INITIAL (fn) |
919 | || TREE_CODE (DECL_INITIAL (fn)) != BLOCK) | |
920 | abort (); | |
921 | ||
d4e4baa9 AO |
922 | /* Create a block to put the parameters in. We have to do this |
923 | after the parameters have been remapped because remapping | |
924 | parameters is different from remapping ordinary variables. */ | |
925 | scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn)); | |
926 | SCOPE_BEGIN_P (scope_stmt) = 1; | |
927 | SCOPE_NO_CLEANUPS_P (scope_stmt) = 1; | |
928 | remap_block (scope_stmt, DECL_ARGUMENTS (fn), id); | |
929 | TREE_CHAIN (scope_stmt) = STMT_EXPR_STMT (expr); | |
930 | STMT_EXPR_STMT (expr) = scope_stmt; | |
931 | ||
932 | /* Tell the debugging backends that this block represents the | |
933 | outermost scope of the inlined function. */ | |
934 | if (SCOPE_STMT_BLOCK (scope_stmt)) | |
935 | BLOCK_ABSTRACT_ORIGIN (SCOPE_STMT_BLOCK (scope_stmt)) = DECL_ORIGIN (fn); | |
936 | ||
937 | /* Declare the return variable for the function. */ | |
938 | STMT_EXPR_STMT (expr) | |
939 | = chainon (STMT_EXPR_STMT (expr), | |
940 | declare_return_variable (id, &use_stmt)); | |
941 | ||
942 | /* After we've initialized the parameters, we insert the body of the | |
943 | function itself. */ | |
944 | inlined_body = &STMT_EXPR_STMT (expr); | |
945 | while (*inlined_body) | |
946 | inlined_body = &TREE_CHAIN (*inlined_body); | |
947 | *inlined_body = copy_body (id); | |
948 | ||
949 | /* Close the block for the parameters. */ | |
950 | scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn)); | |
951 | SCOPE_NO_CLEANUPS_P (scope_stmt) = 1; | |
d4e4baa9 AO |
952 | remap_block (scope_stmt, NULL_TREE, id); |
953 | STMT_EXPR_STMT (expr) | |
954 | = chainon (STMT_EXPR_STMT (expr), scope_stmt); | |
955 | ||
956 | /* After the body of the function comes the RET_LABEL. This must come | |
957 | before we evaluate the returned value below, because that evalulation | |
958 | may cause RTL to be generated. */ | |
959 | STMT_EXPR_STMT (expr) | |
960 | = chainon (STMT_EXPR_STMT (expr), | |
961 | build_stmt (LABEL_STMT, id->ret_label)); | |
962 | ||
963 | /* Finally, mention the returned value so that the value of the | |
964 | statement-expression is the returned value of the function. */ | |
965 | STMT_EXPR_STMT (expr) = chainon (STMT_EXPR_STMT (expr), use_stmt); | |
966 | ||
967 | /* Clean up. */ | |
968 | splay_tree_delete (id->decl_map); | |
969 | id->decl_map = st; | |
970 | ||
971 | /* The new expression has side-effects if the old one did. */ | |
972 | TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t); | |
973 | ||
974 | /* Replace the call by the inlined body. Wrap it in an | |
975 | EXPR_WITH_FILE_LOCATION so that we'll get debugging line notes | |
976 | pointing to the right place. */ | |
977 | chain = TREE_CHAIN (*tp); | |
978 | *tp = build_expr_wfl (expr, DECL_SOURCE_FILE (fn), DECL_SOURCE_LINE (fn), | |
979 | /*col=*/0); | |
980 | EXPR_WFL_EMIT_LINE_NOTE (*tp) = 1; | |
981 | TREE_CHAIN (*tp) = chain; | |
982 | pop_srcloc (); | |
983 | ||
984 | /* If the value of the new expression is ignored, that's OK. We | |
985 | don't warn about this for CALL_EXPRs, so we shouldn't warn about | |
986 | the equivalent inlined version either. */ | |
987 | TREE_USED (*tp) = 1; | |
988 | ||
989 | /* Our function now has more statements than it did before. */ | |
990 | DECL_NUM_STMTS (VARRAY_TREE (id->fns, 0)) += DECL_NUM_STMTS (fn); | |
1eeeb6a4 | 991 | /* For accounting, subtract one for the saved call/ret. */ |
a6227154 | 992 | id->inlined_stmts += DECL_NUM_STMTS (fn) - 1; |
d4e4baa9 AO |
993 | |
994 | /* Recurse into the body of the just inlined function. */ | |
995 | expand_calls_inline (inlined_body, id); | |
996 | VARRAY_POP (id->fns); | |
997 | ||
998 | /* If we've returned to the top level, clear out the record of how | |
999 | much inlining has been done. */ | |
1000 | if (VARRAY_ACTIVE_SIZE (id->fns) == id->first_inlined_fn) | |
1001 | id->inlined_stmts = 0; | |
1002 | ||
1003 | /* Don't walk into subtrees. We've already handled them above. */ | |
1004 | *walk_subtrees = 0; | |
1005 | ||
742a37d5 JM |
1006 | (*lang_hooks.tree_inlining.end_inlining) (fn); |
1007 | ||
d4e4baa9 AO |
1008 | /* Keep iterating. */ |
1009 | return NULL_TREE; | |
1010 | } | |
1011 | ||
1012 | /* Walk over the entire tree *TP, replacing CALL_EXPRs with inline | |
1013 | expansions as appropriate. */ | |
1014 | ||
1015 | static void | |
1016 | expand_calls_inline (tp, id) | |
1017 | tree *tp; | |
1018 | inline_data *id; | |
1019 | { | |
1020 | /* Search through *TP, replacing all calls to inline functions by | |
1021 | appropriate equivalents. Use walk_tree in no-duplicates mode | |
1022 | to avoid exponential time complexity. (We can't just use | |
1023 | walk_tree_without_duplicates, because of the special TARGET_EXPR | |
1024 | handling in expand_calls. The hash table is set up in | |
1025 | optimize_function. */ | |
1026 | walk_tree (tp, expand_call_inline, id, id->tree_pruner); | |
1027 | } | |
1028 | ||
1029 | /* Expand calls to inline functions in the body of FN. */ | |
1030 | ||
1031 | void | |
1032 | optimize_inline_calls (fn) | |
1033 | tree fn; | |
1034 | { | |
1035 | inline_data id; | |
1036 | tree prev_fn; | |
d92b4486 | 1037 | |
d4e4baa9 AO |
1038 | /* Clear out ID. */ |
1039 | memset (&id, 0, sizeof (id)); | |
1040 | ||
1041 | /* Don't allow recursion into FN. */ | |
1042 | VARRAY_TREE_INIT (id.fns, 32, "fns"); | |
1043 | VARRAY_PUSH_TREE (id.fns, fn); | |
1044 | /* Or any functions that aren't finished yet. */ | |
1045 | prev_fn = NULL_TREE; | |
1046 | if (current_function_decl) | |
1047 | { | |
1048 | VARRAY_PUSH_TREE (id.fns, current_function_decl); | |
1049 | prev_fn = current_function_decl; | |
1050 | } | |
1051 | ||
69dcadff AO |
1052 | prev_fn = ((*lang_hooks.tree_inlining.add_pending_fn_decls) |
1053 | (&id.fns, prev_fn)); | |
d92b4486 | 1054 | |
d4e4baa9 AO |
1055 | /* Create the stack of TARGET_EXPRs. */ |
1056 | VARRAY_TREE_INIT (id.target_exprs, 32, "target_exprs"); | |
1057 | ||
1058 | /* Create the list of functions this call will inline. */ | |
1059 | VARRAY_TREE_INIT (id.inlined_fns, 32, "inlined_fns"); | |
1060 | ||
1061 | /* Keep track of the low-water mark, i.e., the point where the first | |
1062 | real inlining is represented in ID.FNS. */ | |
1063 | id.first_inlined_fn = VARRAY_ACTIVE_SIZE (id.fns); | |
1064 | ||
1065 | /* Replace all calls to inline functions with the bodies of those | |
1066 | functions. */ | |
1067 | id.tree_pruner = htab_create (37, htab_hash_pointer, | |
1068 | htab_eq_pointer, NULL); | |
1069 | expand_calls_inline (&DECL_SAVED_TREE (fn), &id); | |
1070 | ||
1071 | /* Clean up. */ | |
1072 | htab_delete (id.tree_pruner); | |
1073 | VARRAY_FREE (id.fns); | |
1074 | VARRAY_FREE (id.target_exprs); | |
1075 | if (DECL_LANG_SPECIFIC (fn)) | |
1076 | { | |
1077 | tree ifn = make_tree_vec (VARRAY_ACTIVE_SIZE (id.inlined_fns)); | |
d92b4486 | 1078 | |
d4e4baa9 AO |
1079 | memcpy (&TREE_VEC_ELT (ifn, 0), &VARRAY_TREE (id.inlined_fns, 0), |
1080 | VARRAY_ACTIVE_SIZE (id.inlined_fns) * sizeof (tree)); | |
1081 | DECL_INLINED_FNS (fn) = ifn; | |
1082 | } | |
1083 | VARRAY_FREE (id.inlined_fns); | |
1084 | } | |
1085 | ||
1086 | /* FN is a function that has a complete body, and CLONE is a function | |
1087 | whose body is to be set to a copy of FN, mapping argument | |
1088 | declarations according to the ARG_MAP splay_tree. */ | |
1089 | ||
1090 | void | |
1091 | clone_body (clone, fn, arg_map) | |
1092 | tree clone, fn; | |
1093 | void *arg_map; | |
1094 | { | |
1095 | inline_data id; | |
1096 | ||
1097 | /* Clone the body, as if we were making an inline call. But, remap | |
1098 | the parameters in the callee to the parameters of caller. If | |
1099 | there's an in-charge parameter, map it to an appropriate | |
1100 | constant. */ | |
1101 | memset (&id, 0, sizeof (id)); | |
1102 | VARRAY_TREE_INIT (id.fns, 2, "fns"); | |
1103 | VARRAY_PUSH_TREE (id.fns, clone); | |
1104 | VARRAY_PUSH_TREE (id.fns, fn); | |
1105 | id.decl_map = (splay_tree)arg_map; | |
1106 | ||
1107 | /* Cloning is treated slightly differently from inlining. Set | |
1108 | CLONING_P so that it's clear which operation we're performing. */ | |
1109 | id.cloning_p = true; | |
1110 | ||
1111 | /* Actually copy the body. */ | |
1112 | TREE_CHAIN (DECL_SAVED_TREE (clone)) = copy_body (&id); | |
1113 | ||
1114 | /* Clean up. */ | |
1115 | VARRAY_FREE (id.fns); | |
1116 | } | |
1117 | ||
1118 | /* Apply FUNC to all the sub-trees of TP in a pre-order traversal. | |
1119 | FUNC is called with the DATA and the address of each sub-tree. If | |
1120 | FUNC returns a non-NULL value, the traversal is aborted, and the | |
1121 | value returned by FUNC is returned. If HTAB is non-NULL it is used | |
1122 | to record the nodes visited, and to avoid visiting a node more than | |
1123 | once. */ | |
1124 | ||
d92b4486 | 1125 | tree |
d4e4baa9 AO |
1126 | walk_tree (tp, func, data, htab_) |
1127 | tree *tp; | |
1128 | walk_tree_fn func; | |
1129 | void *data; | |
1130 | void *htab_; | |
1131 | { | |
1132 | htab_t htab = (htab_t) htab_; | |
1133 | enum tree_code code; | |
1134 | int walk_subtrees; | |
1135 | tree result; | |
d92b4486 | 1136 | |
d4e4baa9 AO |
1137 | #define WALK_SUBTREE(NODE) \ |
1138 | do \ | |
1139 | { \ | |
1140 | result = walk_tree (&(NODE), func, data, htab); \ | |
1141 | if (result) \ | |
1142 | return result; \ | |
1143 | } \ | |
1144 | while (0) | |
1145 | ||
6c624f7f AO |
1146 | #define WALK_SUBTREE_TAIL(NODE) \ |
1147 | do \ | |
1148 | { \ | |
1149 | tp = & (NODE); \ | |
1150 | goto tail_recurse; \ | |
1151 | } \ | |
1152 | while (0) | |
1153 | ||
1154 | tail_recurse: | |
d4e4baa9 AO |
1155 | /* Skip empty subtrees. */ |
1156 | if (!*tp) | |
1157 | return NULL_TREE; | |
1158 | ||
1159 | if (htab) | |
1160 | { | |
1161 | void **slot; | |
d92b4486 | 1162 | |
d4e4baa9 | 1163 | /* Don't walk the same tree twice, if the user has requested |
2ba84f36 | 1164 | that we avoid doing so. */ |
d4e4baa9 AO |
1165 | if (htab_find (htab, *tp)) |
1166 | return NULL_TREE; | |
2ba84f36 | 1167 | /* If we haven't already seen this node, add it to the table. */ |
d4e4baa9 AO |
1168 | slot = htab_find_slot (htab, *tp, INSERT); |
1169 | *slot = *tp; | |
1170 | } | |
1171 | ||
1172 | /* Call the function. */ | |
1173 | walk_subtrees = 1; | |
1174 | result = (*func) (tp, &walk_subtrees, data); | |
1175 | ||
1176 | /* If we found something, return it. */ | |
1177 | if (result) | |
1178 | return result; | |
1179 | ||
1180 | code = TREE_CODE (*tp); | |
1181 | ||
1182 | /* Even if we didn't, FUNC may have decided that there was nothing | |
1183 | interesting below this point in the tree. */ | |
1184 | if (!walk_subtrees) | |
1185 | { | |
1186 | if (statement_code_p (code) || code == TREE_LIST | |
69dcadff | 1187 | || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp)) |
d4e4baa9 | 1188 | /* But we still need to check our siblings. */ |
6c624f7f | 1189 | WALK_SUBTREE_TAIL (TREE_CHAIN (*tp)); |
d4e4baa9 AO |
1190 | else |
1191 | return NULL_TREE; | |
1192 | } | |
1193 | ||
1194 | /* Handle common cases up front. */ | |
1195 | if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)) | |
1196 | || TREE_CODE_CLASS (code) == 'r' | |
1197 | || TREE_CODE_CLASS (code) == 's') | |
1198 | { | |
1199 | int i, len; | |
1200 | ||
1201 | /* Set lineno here so we get the right instantiation context | |
1202 | if we call instantiate_decl from inlinable_function_p. */ | |
1203 | if (statement_code_p (code) && !STMT_LINENO_FOR_FN_P (*tp)) | |
1204 | lineno = STMT_LINENO (*tp); | |
1205 | ||
1206 | /* Walk over all the sub-trees of this operand. */ | |
1207 | len = first_rtl_op (code); | |
1208 | /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same. | |
1209 | But, we only want to walk once. */ | |
1210 | if (code == TARGET_EXPR | |
1211 | && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1)) | |
1212 | --len; | |
1213 | /* Go through the subtrees. We need to do this in forward order so | |
1214 | that the scope of a FOR_EXPR is handled properly. */ | |
1215 | for (i = 0; i < len; ++i) | |
1216 | WALK_SUBTREE (TREE_OPERAND (*tp, i)); | |
1217 | ||
1218 | /* For statements, we also walk the chain so that we cover the | |
1219 | entire statement tree. */ | |
1220 | if (statement_code_p (code)) | |
1221 | { | |
d92b4486 KH |
1222 | if (code == DECL_STMT |
1223 | && DECL_STMT_DECL (*tp) | |
d4e4baa9 AO |
1224 | && DECL_P (DECL_STMT_DECL (*tp))) |
1225 | { | |
1226 | /* Walk the DECL_INITIAL and DECL_SIZE. We don't want to walk | |
1227 | into declarations that are just mentioned, rather than | |
1228 | declared; they don't really belong to this part of the tree. | |
1229 | And, we can see cycles: the initializer for a declaration can | |
1230 | refer to the declaration itself. */ | |
1231 | WALK_SUBTREE (DECL_INITIAL (DECL_STMT_DECL (*tp))); | |
1232 | WALK_SUBTREE (DECL_SIZE (DECL_STMT_DECL (*tp))); | |
1233 | WALK_SUBTREE (DECL_SIZE_UNIT (DECL_STMT_DECL (*tp))); | |
1234 | } | |
1235 | ||
1236 | /* This can be tail-recursion optimized if we write it this way. */ | |
6c624f7f | 1237 | WALK_SUBTREE_TAIL (TREE_CHAIN (*tp)); |
d4e4baa9 AO |
1238 | } |
1239 | ||
1240 | /* We didn't find what we were looking for. */ | |
1241 | return NULL_TREE; | |
1242 | } | |
1243 | else if (TREE_CODE_CLASS (code) == 'd') | |
1244 | { | |
6c624f7f | 1245 | WALK_SUBTREE_TAIL (TREE_TYPE (*tp)); |
d4e4baa9 AO |
1246 | } |
1247 | ||
69dcadff AO |
1248 | result = (*lang_hooks.tree_inlining.walk_subtrees) (tp, &walk_subtrees, func, |
1249 | data, htab); | |
d4e4baa9 AO |
1250 | if (result || ! walk_subtrees) |
1251 | return result; | |
1252 | ||
1253 | /* Not one of the easy cases. We must explicitly go through the | |
1254 | children. */ | |
1255 | switch (code) | |
1256 | { | |
1257 | case ERROR_MARK: | |
1258 | case IDENTIFIER_NODE: | |
1259 | case INTEGER_CST: | |
1260 | case REAL_CST: | |
69ef87e2 | 1261 | case VECTOR_CST: |
d4e4baa9 AO |
1262 | case STRING_CST: |
1263 | case REAL_TYPE: | |
1264 | case COMPLEX_TYPE: | |
1265 | case VECTOR_TYPE: | |
1266 | case VOID_TYPE: | |
1267 | case BOOLEAN_TYPE: | |
1268 | case UNION_TYPE: | |
1269 | case ENUMERAL_TYPE: | |
1270 | case BLOCK: | |
1271 | case RECORD_TYPE: | |
1272 | /* None of thse have subtrees other than those already walked | |
1273 | above. */ | |
1274 | break; | |
1275 | ||
1276 | case POINTER_TYPE: | |
1277 | case REFERENCE_TYPE: | |
6c624f7f | 1278 | WALK_SUBTREE_TAIL (TREE_TYPE (*tp)); |
d4e4baa9 AO |
1279 | break; |
1280 | ||
1281 | case TREE_LIST: | |
1282 | WALK_SUBTREE (TREE_VALUE (*tp)); | |
6c624f7f | 1283 | WALK_SUBTREE_TAIL (TREE_CHAIN (*tp)); |
d4e4baa9 AO |
1284 | break; |
1285 | ||
1286 | case TREE_VEC: | |
1287 | { | |
1288 | int len = TREE_VEC_LENGTH (*tp); | |
6c624f7f AO |
1289 | |
1290 | if (len == 0) | |
1291 | break; | |
1292 | ||
1293 | /* Walk all elements but the first. */ | |
1294 | while (--len) | |
d4e4baa9 | 1295 | WALK_SUBTREE (TREE_VEC_ELT (*tp, len)); |
6c624f7f AO |
1296 | |
1297 | /* Now walk the first one as a tail call. */ | |
1298 | WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0)); | |
d4e4baa9 | 1299 | } |
d4e4baa9 AO |
1300 | |
1301 | case COMPLEX_CST: | |
1302 | WALK_SUBTREE (TREE_REALPART (*tp)); | |
6c624f7f | 1303 | WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp)); |
d4e4baa9 AO |
1304 | |
1305 | case CONSTRUCTOR: | |
6c624f7f | 1306 | WALK_SUBTREE_TAIL (CONSTRUCTOR_ELTS (*tp)); |
d4e4baa9 AO |
1307 | |
1308 | case METHOD_TYPE: | |
1309 | WALK_SUBTREE (TYPE_METHOD_BASETYPE (*tp)); | |
1310 | /* Fall through. */ | |
1311 | ||
1312 | case FUNCTION_TYPE: | |
1313 | WALK_SUBTREE (TREE_TYPE (*tp)); | |
1314 | { | |
1315 | tree arg = TYPE_ARG_TYPES (*tp); | |
1316 | ||
1317 | /* We never want to walk into default arguments. */ | |
1318 | for (; arg; arg = TREE_CHAIN (arg)) | |
1319 | WALK_SUBTREE (TREE_VALUE (arg)); | |
1320 | } | |
1321 | break; | |
1322 | ||
1323 | case ARRAY_TYPE: | |
1324 | WALK_SUBTREE (TREE_TYPE (*tp)); | |
6c624f7f | 1325 | WALK_SUBTREE_TAIL (TYPE_DOMAIN (*tp)); |
d4e4baa9 AO |
1326 | |
1327 | case INTEGER_TYPE: | |
1328 | WALK_SUBTREE (TYPE_MIN_VALUE (*tp)); | |
6c624f7f | 1329 | WALK_SUBTREE_TAIL (TYPE_MAX_VALUE (*tp)); |
d4e4baa9 AO |
1330 | |
1331 | case OFFSET_TYPE: | |
1332 | WALK_SUBTREE (TREE_TYPE (*tp)); | |
6c624f7f | 1333 | WALK_SUBTREE_TAIL (TYPE_OFFSET_BASETYPE (*tp)); |
d4e4baa9 AO |
1334 | |
1335 | default: | |
1336 | abort (); | |
1337 | } | |
1338 | ||
1339 | /* We didn't find what we were looking for. */ | |
1340 | return NULL_TREE; | |
1341 | ||
1342 | #undef WALK_SUBTREE | |
1343 | } | |
1344 | ||
d92b4486 | 1345 | /* Like walk_tree, but does not walk duplicate nodes more than |
d4e4baa9 AO |
1346 | once. */ |
1347 | ||
d92b4486 | 1348 | tree |
d4e4baa9 AO |
1349 | walk_tree_without_duplicates (tp, func, data) |
1350 | tree *tp; | |
1351 | walk_tree_fn func; | |
1352 | void *data; | |
1353 | { | |
1354 | tree result; | |
1355 | htab_t htab; | |
1356 | ||
1357 | htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL); | |
1358 | result = walk_tree (tp, func, data, htab); | |
1359 | htab_delete (htab); | |
1360 | return result; | |
1361 | } | |
1362 | ||
1363 | /* Passed to walk_tree. Copies the node pointed to, if appropriate. */ | |
1364 | ||
1365 | tree | |
1366 | copy_tree_r (tp, walk_subtrees, data) | |
1367 | tree *tp; | |
1368 | int *walk_subtrees; | |
1369 | void *data ATTRIBUTE_UNUSED; | |
1370 | { | |
1371 | enum tree_code code = TREE_CODE (*tp); | |
1372 | ||
1373 | /* We make copies of most nodes. */ | |
1374 | if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)) | |
1375 | || TREE_CODE_CLASS (code) == 'r' | |
1376 | || TREE_CODE_CLASS (code) == 'c' | |
1377 | || TREE_CODE_CLASS (code) == 's' | |
1378 | || code == TREE_LIST | |
1379 | || code == TREE_VEC | |
69dcadff | 1380 | || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp)) |
d4e4baa9 AO |
1381 | { |
1382 | /* Because the chain gets clobbered when we make a copy, we save it | |
1383 | here. */ | |
1384 | tree chain = TREE_CHAIN (*tp); | |
1385 | ||
1386 | /* Copy the node. */ | |
1387 | *tp = copy_node (*tp); | |
1388 | ||
1389 | /* Now, restore the chain, if appropriate. That will cause | |
1390 | walk_tree to walk into the chain as well. */ | |
1391 | if (code == PARM_DECL || code == TREE_LIST | |
69dcadff | 1392 | || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp) |
d4e4baa9 AO |
1393 | || statement_code_p (code)) |
1394 | TREE_CHAIN (*tp) = chain; | |
1395 | ||
1396 | /* For now, we don't update BLOCKs when we make copies. So, we | |
1397 | have to nullify all scope-statements. */ | |
1398 | if (TREE_CODE (*tp) == SCOPE_STMT) | |
1399 | SCOPE_STMT_BLOCK (*tp) = NULL_TREE; | |
1400 | } | |
1401 | else if (TREE_CODE_CLASS (code) == 't') | |
1402 | /* There's no need to copy types, or anything beneath them. */ | |
1403 | *walk_subtrees = 0; | |
1404 | ||
1405 | return NULL_TREE; | |
1406 | } | |
1407 | ||
1408 | /* The SAVE_EXPR pointed to by TP is being copied. If ST contains | |
1409 | information indicating to what new SAVE_EXPR this one should be | |
1410 | mapped, use that one. Otherwise, create a new node and enter it in | |
1411 | ST. FN is the function into which the copy will be placed. */ | |
1412 | ||
1413 | void | |
1414 | remap_save_expr (tp, st_, fn, walk_subtrees) | |
1415 | tree *tp; | |
1416 | void *st_; | |
1417 | tree fn; | |
1418 | int *walk_subtrees; | |
1419 | { | |
1420 | splay_tree st = (splay_tree) st_; | |
1421 | splay_tree_node n; | |
1422 | ||
1423 | /* See if we already encountered this SAVE_EXPR. */ | |
1424 | n = splay_tree_lookup (st, (splay_tree_key) *tp); | |
d92b4486 | 1425 | |
d4e4baa9 AO |
1426 | /* If we didn't already remap this SAVE_EXPR, do so now. */ |
1427 | if (!n) | |
1428 | { | |
1429 | tree t = copy_node (*tp); | |
1430 | ||
1431 | /* The SAVE_EXPR is now part of the function into which we | |
1432 | are inlining this body. */ | |
1433 | SAVE_EXPR_CONTEXT (t) = fn; | |
1434 | /* And we haven't evaluated it yet. */ | |
1435 | SAVE_EXPR_RTL (t) = NULL_RTX; | |
1436 | /* Remember this SAVE_EXPR. */ | |
1437 | n = splay_tree_insert (st, | |
1438 | (splay_tree_key) *tp, | |
1439 | (splay_tree_value) t); | |
350ebd54 AO |
1440 | /* Make sure we don't remap an already-remapped SAVE_EXPR. */ |
1441 | splay_tree_insert (st, (splay_tree_key) t, | |
1442 | (splay_tree_value) error_mark_node); | |
d4e4baa9 AO |
1443 | } |
1444 | else | |
1445 | /* We've already walked into this SAVE_EXPR, so we needn't do it | |
1446 | again. */ | |
1447 | *walk_subtrees = 0; | |
1448 | ||
1449 | /* Replace this SAVE_EXPR with the copy. */ | |
1450 | *tp = (tree) n->value; | |
1451 | } |