]>
Commit | Line | Data |
---|---|---|
1431bff6 | 1 | /* Control and data flow functions for trees. |
d513ec2f | 2 | Copyright 2001, 2002 Free Software Foundation, Inc. |
1431bff6 | 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" | |
e8602e56 | 24 | #include "toplev.h" |
1431bff6 | 25 | #include "tree.h" |
26 | #include "tree-inline.h" | |
e343483a | 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" | |
b0278d39 | 37 | #include "langhooks.h" |
e343483a | 38 | |
39 | /* This should be eventually be generalized to other languages, but | |
40 | this would require a shared function-as-trees infrastructure. */ | |
40570cc2 | 41 | #include "c-common.h" |
1431bff6 | 42 | |
1431bff6 | 43 | /* 0 if we should not perform inlining. |
40570cc2 | 44 | 1 if we should expand functions calls inline at the tree level. |
45 | 2 if we should consider *all* functions to be inline | |
1431bff6 | 46 | candidates. */ |
47 | ||
48 | int flag_inline_trees = 0; | |
e343483a | 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); | |
e8602e56 | 133 | if (! (*lang_hooks.tree_inlining.auto_var_in_fn_p) (decl, fn)) |
e343483a | 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. */ | |
e343483a | 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) | |
e8602e56 | 162 | && (*lang_hooks.tree_inlining.anon_aggr_type_p) (TREE_TYPE (t))) |
e343483a | 163 | { |
164 | /* For a VAR_DECL of anonymous type, we must also copy the | |
165 | member VAR_DECLS here and rechain the | |
88b5b080 | 166 | DECL_ANON_UNION_ELEMS. */ |
e343483a | 167 | tree members = NULL; |
168 | tree src; | |
40570cc2 | 169 | |
e343483a | 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 | } | |
40570cc2 | 181 | |
e343483a | 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. */ | |
20325f61 | 260 | (*lang_hooks.decls.insert_block) (new_block); |
e343483a | 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); | |
0ddab289 | 353 | GOTO_FAKE_P (goto_stmt) = 1; |
e343483a | 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. */ | |
e8602e56 | 374 | else if ((*lang_hooks.tree_inlining.auto_var_in_fn_p) (*tp, fn)) |
e343483a | 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) | |
e8602e56 | 416 | && ((*lang_hooks.tree_inlining.auto_var_in_fn_p) |
417 | (TREE_OPERAND (*tp, 0), fn))) | |
e343483a | 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. */ | |
e619d7b1 | 477 | for (p = parms, a = args; p; |
478 | a = a ? TREE_CHAIN (a) : a, p = TREE_CHAIN (p)) | |
e343483a | 479 | { |
480 | tree init_stmt; | |
481 | tree var; | |
482 | tree value; | |
7b6facbf | 483 | tree cleanup; |
e343483a | 484 | |
485 | /* Find the initializer. */ | |
78b80426 | 486 | value = (*lang_hooks.tree_inlining.convert_parm_for_inlining) |
487 | (p, a ? TREE_VALUE (a) : NULL_TREE, fn); | |
e619d7b1 | 488 | |
e343483a | 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) | |
e619d7b1 | 494 | && value && !TREE_SIDE_EFFECTS (value)) |
e343483a | 495 | { |
496 | /* Simplify the value, if possible. */ | |
e619d7b1 | 497 | value = fold (DECL_P (value) ? decl_constant_value (value) : value); |
e343483a | 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 | } | |
7b6facbf | 563 | |
564 | /* See if we need to clean up the declaration. */ | |
04745efb | 565 | cleanup = (*lang_hooks.maybe_build_cleanup) (var); |
40570cc2 | 566 | if (cleanup) |
7b6facbf | 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 | } | |
e343483a | 576 | } |
577 | ||
e619d7b1 | 578 | /* Evaluate trailing arguments. */ |
579 | for (; a; a = TREE_CHAIN (a)) | |
580 | { | |
581 | tree init_stmt; | |
7b6facbf | 582 | tree value = TREE_VALUE (a); |
e619d7b1 | 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 | ||
e343483a | 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 | ||
e8602e56 | 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)); | |
e343483a | 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 | ||
e619d7b1 | 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)); | |
d513ec2f | 639 | |
640 | TREE_ADDRESSABLE (*use_stmt) = 1; | |
641 | ||
e343483a | 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 | ||
e619d7b1 | 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. */ | |
e343483a | 664 | |
665 | static int | |
666 | inlinable_function_p (fn, id) | |
667 | tree fn; | |
668 | inline_data *id; | |
669 | { | |
670 | int inlinable; | |
6cc4057d | 671 | int currfn_insns; |
e343483a | 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; | |
40570cc2 | 680 | |
a113df96 | 681 | /* The number of instructions (estimated) of current function. */ |
6cc4057d | 682 | currfn_insns = DECL_NUM_STMTS (fn) * INSNS_PER_STMT; |
e343483a | 683 | |
684 | /* If we're not inlining things, then nothing is inlinable. */ | |
e619d7b1 | 685 | if (! flag_inline_trees) |
e343483a | 686 | ; |
e619d7b1 | 687 | /* If we're not inlining all functions and the function was not |
4bbe9a60 | 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)) | |
e343483a | 694 | ; |
695 | /* We can't inline functions that are too big. Only allow a single | |
40570cc2 | 696 | function to be of MAX_INLINE_INSNS_SINGLE size. Make special |
6cc4057d | 697 | allowance for extern inline functions, though. */ |
e8602e56 | 698 | else if (! (*lang_hooks.tree_inlining.disregard_inline_limits) (fn) |
6cc4057d | 699 | && currfn_insns > MAX_INLINE_INSNS_SINGLE) |
e343483a | 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. */ | |
e619d7b1 | 709 | DECL_UNINLINABLE (fn) = ! inlinable; |
e343483a | 710 | |
6cc4057d | 711 | /* In case we don't disregard the inlining limits and we basically |
a113df96 | 712 | can inline this function, investigate further. */ |
e8602e56 | 713 | if (! (*lang_hooks.tree_inlining.disregard_inline_limits) (fn) |
6cc4057d | 714 | && inlinable) |
40570cc2 | 715 | { |
6cc4057d | 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 | |
a113df96 | 720 | in real life. */ |
6cc4057d | 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 | |
a113df96 | 726 | though. */ |
6cc4057d | 727 | else if ((sum_insns > MAX_INLINE_INSNS) |
728 | && (currfn_insns > MIN_INLINE_INSNS)) | |
40570cc2 | 729 | { |
6cc4057d | 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 | } | |
e343483a | 736 | |
e8602e56 | 737 | if (inlinable && (*lang_hooks.tree_inlining.cannot_inline_tree_fn) (&fn)) |
e343483a | 738 | inlinable = 0; |
40570cc2 | 739 | |
e343483a | 740 | /* If we don't have the function body available, we can't inline |
741 | it. */ | |
e619d7b1 | 742 | if (! DECL_SAVED_TREE (fn)) |
e343483a | 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. */ | |
e619d7b1 | 751 | if (id) |
e343483a | 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 | ||
e619d7b1 | 759 | if (DECL_INLINED_FNS (fn)) |
e343483a | 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; | |
8d0b5876 | 785 | tree stmt; |
e343483a | 786 | tree chain; |
787 | tree fn; | |
788 | tree scope_stmt; | |
789 | tree use_stmt; | |
790 | tree arg_inits; | |
791 | tree *inlined_body; | |
792 | splay_tree st; | |
793 | ||
794 | /* See what we've got. */ | |
795 | id = (inline_data *) data; | |
796 | t = *tp; | |
797 | ||
798 | /* Recurse, but letting recursive invocations know that we are | |
799 | inside the body of a TARGET_EXPR. */ | |
800 | if (TREE_CODE (*tp) == TARGET_EXPR) | |
801 | { | |
802 | int i, len = first_rtl_op (TARGET_EXPR); | |
803 | ||
804 | /* We're walking our own subtrees. */ | |
805 | *walk_subtrees = 0; | |
806 | ||
807 | /* Push *TP on the stack of pending TARGET_EXPRs. */ | |
808 | VARRAY_PUSH_TREE (id->target_exprs, *tp); | |
809 | ||
810 | /* Actually walk over them. This loop is the body of | |
811 | walk_trees, omitting the case where the TARGET_EXPR | |
812 | itself is handled. */ | |
813 | for (i = 0; i < len; ++i) | |
814 | { | |
815 | if (i == 2) | |
816 | ++id->in_target_cleanup_p; | |
817 | walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data, | |
818 | id->tree_pruner); | |
819 | if (i == 2) | |
820 | --id->in_target_cleanup_p; | |
821 | } | |
822 | ||
823 | /* We're done with this TARGET_EXPR now. */ | |
824 | VARRAY_POP (id->target_exprs); | |
825 | ||
826 | return NULL_TREE; | |
827 | } | |
828 | ||
829 | if (TYPE_P (t)) | |
830 | /* Because types were not copied in copy_body, CALL_EXPRs beneath | |
831 | them should not be expanded. This can happen if the type is a | |
832 | dynamic array type, for example. */ | |
833 | *walk_subtrees = 0; | |
834 | ||
835 | /* From here on, we're only interested in CALL_EXPRs. */ | |
836 | if (TREE_CODE (t) != CALL_EXPR) | |
837 | return NULL_TREE; | |
838 | ||
839 | /* First, see if we can figure out what function is being called. | |
840 | If we cannot, then there is no hope of inlining the function. */ | |
841 | fn = get_callee_fndecl (t); | |
842 | if (!fn) | |
843 | return NULL_TREE; | |
844 | ||
ad850f1c | 845 | /* If fn is a declaration of a function in a nested scope that was |
846 | globally declared inline, we don't set its DECL_INITIAL. | |
847 | However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the | |
848 | C++ front-end uses it for cdtors to refer to their internal | |
849 | declarations, that are not real functions. Fortunately those | |
850 | don't have trees to be saved, so we can tell by checking their | |
851 | DECL_SAVED_TREE. */ | |
852 | if (! DECL_INITIAL (fn) | |
853 | && DECL_ABSTRACT_ORIGIN (fn) | |
854 | && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn))) | |
855 | fn = DECL_ABSTRACT_ORIGIN (fn); | |
856 | ||
e343483a | 857 | /* Don't try to inline functions that are not well-suited to |
858 | inlining. */ | |
859 | if (!inlinable_function_p (fn, id)) | |
860 | return NULL_TREE; | |
861 | ||
054e01a7 | 862 | if (! (*lang_hooks.tree_inlining.start_inlining) (fn)) |
863 | return NULL_TREE; | |
864 | ||
e343483a | 865 | /* Set the current filename and line number to the function we are |
866 | inlining so that when we create new _STMT nodes here they get | |
867 | line numbers corresponding to the function we are calling. We | |
868 | wrap the whole inlined body in an EXPR_WITH_FILE_AND_LINE as well | |
869 | because individual statements don't record the filename. */ | |
870 | push_srcloc (fn->decl.filename, fn->decl.linenum); | |
871 | ||
872 | /* Build a statement-expression containing code to initialize the | |
873 | arguments, the actual inline expansion of the body, and a label | |
874 | for the return statements within the function to jump to. The | |
875 | type of the statement expression is the return type of the | |
876 | function call. */ | |
8d0b5876 | 877 | expr = build1 (STMT_EXPR, TREE_TYPE (TREE_TYPE (fn)), make_node (COMPOUND_STMT)); |
7e83d989 | 878 | /* There is no scope associated with the statement-expression. */ |
879 | STMT_EXPR_NO_SCOPE (expr) = 1; | |
8d0b5876 | 880 | stmt = STMT_EXPR_STMT (expr); |
e343483a | 881 | /* Local declarations will be replaced by their equivalents in this |
882 | map. */ | |
883 | st = id->decl_map; | |
884 | id->decl_map = splay_tree_new (splay_tree_compare_pointers, | |
885 | NULL, NULL); | |
886 | ||
887 | /* Initialize the parameters. */ | |
888 | arg_inits = initialize_inlined_parameters (id, TREE_OPERAND (t, 1), fn); | |
889 | /* Expand any inlined calls in the initializers. Do this before we | |
890 | push FN on the stack of functions we are inlining; we want to | |
891 | inline calls to FN that appear in the initializers for the | |
892 | parameters. */ | |
893 | expand_calls_inline (&arg_inits, id); | |
894 | /* And add them to the tree. */ | |
8d0b5876 | 895 | COMPOUND_BODY (stmt) = chainon (COMPOUND_BODY (stmt), arg_inits); |
e343483a | 896 | |
897 | /* Record the function we are about to inline so that we can avoid | |
898 | recursing into it. */ | |
899 | VARRAY_PUSH_TREE (id->fns, fn); | |
900 | ||
901 | /* Record the function we are about to inline if optimize_function | |
902 | has not been called on it yet and we don't have it in the list. */ | |
903 | if (! DECL_INLINED_FNS (fn)) | |
904 | { | |
905 | int i; | |
906 | ||
907 | for (i = VARRAY_ACTIVE_SIZE (id->inlined_fns) - 1; i >= 0; i--) | |
908 | if (VARRAY_TREE (id->inlined_fns, i) == fn) | |
909 | break; | |
910 | if (i < 0) | |
911 | VARRAY_PUSH_TREE (id->inlined_fns, fn); | |
912 | } | |
913 | ||
914 | /* Return statements in the function body will be replaced by jumps | |
915 | to the RET_LABEL. */ | |
916 | id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE); | |
917 | DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0); | |
918 | ||
9a0c59e9 | 919 | if (! DECL_INITIAL (fn) |
920 | || TREE_CODE (DECL_INITIAL (fn)) != BLOCK) | |
921 | abort (); | |
922 | ||
e343483a | 923 | /* Create a block to put the parameters in. We have to do this |
924 | after the parameters have been remapped because remapping | |
925 | parameters is different from remapping ordinary variables. */ | |
926 | scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn)); | |
927 | SCOPE_BEGIN_P (scope_stmt) = 1; | |
928 | SCOPE_NO_CLEANUPS_P (scope_stmt) = 1; | |
929 | remap_block (scope_stmt, DECL_ARGUMENTS (fn), id); | |
8d0b5876 | 930 | TREE_CHAIN (scope_stmt) = COMPOUND_BODY (stmt); |
931 | COMPOUND_BODY (stmt) = scope_stmt; | |
e343483a | 932 | |
933 | /* Tell the debugging backends that this block represents the | |
934 | outermost scope of the inlined function. */ | |
935 | if (SCOPE_STMT_BLOCK (scope_stmt)) | |
936 | BLOCK_ABSTRACT_ORIGIN (SCOPE_STMT_BLOCK (scope_stmt)) = DECL_ORIGIN (fn); | |
937 | ||
938 | /* Declare the return variable for the function. */ | |
8d0b5876 | 939 | COMPOUND_BODY (stmt) |
940 | = chainon (COMPOUND_BODY (stmt), | |
e343483a | 941 | declare_return_variable (id, &use_stmt)); |
942 | ||
943 | /* After we've initialized the parameters, we insert the body of the | |
944 | function itself. */ | |
8d0b5876 | 945 | inlined_body = &COMPOUND_BODY (stmt); |
e343483a | 946 | while (*inlined_body) |
947 | inlined_body = &TREE_CHAIN (*inlined_body); | |
948 | *inlined_body = copy_body (id); | |
949 | ||
e343483a | 950 | /* After the body of the function comes the RET_LABEL. This must come |
951 | before we evaluate the returned value below, because that evalulation | |
952 | may cause RTL to be generated. */ | |
8d0b5876 | 953 | COMPOUND_BODY (stmt) |
954 | = chainon (COMPOUND_BODY (stmt), | |
e343483a | 955 | build_stmt (LABEL_STMT, id->ret_label)); |
956 | ||
957 | /* Finally, mention the returned value so that the value of the | |
958 | statement-expression is the returned value of the function. */ | |
8d0b5876 | 959 | COMPOUND_BODY (stmt) = chainon (COMPOUND_BODY (stmt), use_stmt); |
960 | ||
961 | /* Close the block for the parameters. */ | |
962 | scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn)); | |
963 | SCOPE_NO_CLEANUPS_P (scope_stmt) = 1; | |
964 | remap_block (scope_stmt, NULL_TREE, id); | |
965 | COMPOUND_BODY (stmt) | |
966 | = chainon (COMPOUND_BODY (stmt), scope_stmt); | |
e343483a | 967 | |
968 | /* Clean up. */ | |
969 | splay_tree_delete (id->decl_map); | |
970 | id->decl_map = st; | |
971 | ||
972 | /* The new expression has side-effects if the old one did. */ | |
973 | TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t); | |
974 | ||
975 | /* Replace the call by the inlined body. Wrap it in an | |
976 | EXPR_WITH_FILE_LOCATION so that we'll get debugging line notes | |
977 | pointing to the right place. */ | |
978 | chain = TREE_CHAIN (*tp); | |
979 | *tp = build_expr_wfl (expr, DECL_SOURCE_FILE (fn), DECL_SOURCE_LINE (fn), | |
980 | /*col=*/0); | |
981 | EXPR_WFL_EMIT_LINE_NOTE (*tp) = 1; | |
982 | TREE_CHAIN (*tp) = chain; | |
983 | pop_srcloc (); | |
984 | ||
985 | /* If the value of the new expression is ignored, that's OK. We | |
986 | don't warn about this for CALL_EXPRs, so we shouldn't warn about | |
987 | the equivalent inlined version either. */ | |
988 | TREE_USED (*tp) = 1; | |
989 | ||
990 | /* Our function now has more statements than it did before. */ | |
991 | DECL_NUM_STMTS (VARRAY_TREE (id->fns, 0)) += DECL_NUM_STMTS (fn); | |
a113df96 | 992 | /* For accounting, subtract one for the saved call/ret. */ |
6cc4057d | 993 | id->inlined_stmts += DECL_NUM_STMTS (fn) - 1; |
e343483a | 994 | |
995 | /* Recurse into the body of the just inlined function. */ | |
996 | expand_calls_inline (inlined_body, id); | |
997 | VARRAY_POP (id->fns); | |
998 | ||
999 | /* If we've returned to the top level, clear out the record of how | |
1000 | much inlining has been done. */ | |
1001 | if (VARRAY_ACTIVE_SIZE (id->fns) == id->first_inlined_fn) | |
1002 | id->inlined_stmts = 0; | |
1003 | ||
1004 | /* Don't walk into subtrees. We've already handled them above. */ | |
1005 | *walk_subtrees = 0; | |
1006 | ||
054e01a7 | 1007 | (*lang_hooks.tree_inlining.end_inlining) (fn); |
1008 | ||
e343483a | 1009 | /* Keep iterating. */ |
1010 | return NULL_TREE; | |
1011 | } | |
1012 | ||
1013 | /* Walk over the entire tree *TP, replacing CALL_EXPRs with inline | |
1014 | expansions as appropriate. */ | |
1015 | ||
1016 | static void | |
1017 | expand_calls_inline (tp, id) | |
1018 | tree *tp; | |
1019 | inline_data *id; | |
1020 | { | |
1021 | /* Search through *TP, replacing all calls to inline functions by | |
1022 | appropriate equivalents. Use walk_tree in no-duplicates mode | |
1023 | to avoid exponential time complexity. (We can't just use | |
1024 | walk_tree_without_duplicates, because of the special TARGET_EXPR | |
1025 | handling in expand_calls. The hash table is set up in | |
1026 | optimize_function. */ | |
1027 | walk_tree (tp, expand_call_inline, id, id->tree_pruner); | |
1028 | } | |
1029 | ||
1030 | /* Expand calls to inline functions in the body of FN. */ | |
1031 | ||
1032 | void | |
1033 | optimize_inline_calls (fn) | |
1034 | tree fn; | |
1035 | { | |
1036 | inline_data id; | |
1037 | tree prev_fn; | |
40570cc2 | 1038 | |
e343483a | 1039 | /* Clear out ID. */ |
1040 | memset (&id, 0, sizeof (id)); | |
1041 | ||
1042 | /* Don't allow recursion into FN. */ | |
1043 | VARRAY_TREE_INIT (id.fns, 32, "fns"); | |
1044 | VARRAY_PUSH_TREE (id.fns, fn); | |
1045 | /* Or any functions that aren't finished yet. */ | |
1046 | prev_fn = NULL_TREE; | |
1047 | if (current_function_decl) | |
1048 | { | |
1049 | VARRAY_PUSH_TREE (id.fns, current_function_decl); | |
1050 | prev_fn = current_function_decl; | |
1051 | } | |
1052 | ||
e8602e56 | 1053 | prev_fn = ((*lang_hooks.tree_inlining.add_pending_fn_decls) |
1054 | (&id.fns, prev_fn)); | |
40570cc2 | 1055 | |
e343483a | 1056 | /* Create the stack of TARGET_EXPRs. */ |
1057 | VARRAY_TREE_INIT (id.target_exprs, 32, "target_exprs"); | |
1058 | ||
1059 | /* Create the list of functions this call will inline. */ | |
1060 | VARRAY_TREE_INIT (id.inlined_fns, 32, "inlined_fns"); | |
1061 | ||
1062 | /* Keep track of the low-water mark, i.e., the point where the first | |
1063 | real inlining is represented in ID.FNS. */ | |
1064 | id.first_inlined_fn = VARRAY_ACTIVE_SIZE (id.fns); | |
1065 | ||
1066 | /* Replace all calls to inline functions with the bodies of those | |
1067 | functions. */ | |
1068 | id.tree_pruner = htab_create (37, htab_hash_pointer, | |
1069 | htab_eq_pointer, NULL); | |
1070 | expand_calls_inline (&DECL_SAVED_TREE (fn), &id); | |
1071 | ||
1072 | /* Clean up. */ | |
1073 | htab_delete (id.tree_pruner); | |
e343483a | 1074 | if (DECL_LANG_SPECIFIC (fn)) |
1075 | { | |
1076 | tree ifn = make_tree_vec (VARRAY_ACTIVE_SIZE (id.inlined_fns)); | |
40570cc2 | 1077 | |
e343483a | 1078 | memcpy (&TREE_VEC_ELT (ifn, 0), &VARRAY_TREE (id.inlined_fns, 0), |
1079 | VARRAY_ACTIVE_SIZE (id.inlined_fns) * sizeof (tree)); | |
1080 | DECL_INLINED_FNS (fn) = ifn; | |
1081 | } | |
e343483a | 1082 | } |
1083 | ||
1084 | /* FN is a function that has a complete body, and CLONE is a function | |
1085 | whose body is to be set to a copy of FN, mapping argument | |
1086 | declarations according to the ARG_MAP splay_tree. */ | |
1087 | ||
1088 | void | |
1089 | clone_body (clone, fn, arg_map) | |
1090 | tree clone, fn; | |
1091 | void *arg_map; | |
1092 | { | |
1093 | inline_data id; | |
1094 | ||
1095 | /* Clone the body, as if we were making an inline call. But, remap | |
1096 | the parameters in the callee to the parameters of caller. If | |
1097 | there's an in-charge parameter, map it to an appropriate | |
1098 | constant. */ | |
1099 | memset (&id, 0, sizeof (id)); | |
1100 | VARRAY_TREE_INIT (id.fns, 2, "fns"); | |
1101 | VARRAY_PUSH_TREE (id.fns, clone); | |
1102 | VARRAY_PUSH_TREE (id.fns, fn); | |
1103 | id.decl_map = (splay_tree)arg_map; | |
1104 | ||
1105 | /* Cloning is treated slightly differently from inlining. Set | |
1106 | CLONING_P so that it's clear which operation we're performing. */ | |
1107 | id.cloning_p = true; | |
1108 | ||
1109 | /* Actually copy the body. */ | |
1110 | TREE_CHAIN (DECL_SAVED_TREE (clone)) = copy_body (&id); | |
e343483a | 1111 | } |
1112 | ||
1113 | /* Apply FUNC to all the sub-trees of TP in a pre-order traversal. | |
1114 | FUNC is called with the DATA and the address of each sub-tree. If | |
1115 | FUNC returns a non-NULL value, the traversal is aborted, and the | |
1116 | value returned by FUNC is returned. If HTAB is non-NULL it is used | |
1117 | to record the nodes visited, and to avoid visiting a node more than | |
1118 | once. */ | |
1119 | ||
40570cc2 | 1120 | tree |
e343483a | 1121 | walk_tree (tp, func, data, htab_) |
1122 | tree *tp; | |
1123 | walk_tree_fn func; | |
1124 | void *data; | |
1125 | void *htab_; | |
1126 | { | |
1127 | htab_t htab = (htab_t) htab_; | |
1128 | enum tree_code code; | |
1129 | int walk_subtrees; | |
1130 | tree result; | |
40570cc2 | 1131 | |
e343483a | 1132 | #define WALK_SUBTREE(NODE) \ |
1133 | do \ | |
1134 | { \ | |
1135 | result = walk_tree (&(NODE), func, data, htab); \ | |
1136 | if (result) \ | |
1137 | return result; \ | |
1138 | } \ | |
1139 | while (0) | |
1140 | ||
357ec3f0 | 1141 | #define WALK_SUBTREE_TAIL(NODE) \ |
1142 | do \ | |
1143 | { \ | |
1144 | tp = & (NODE); \ | |
1145 | goto tail_recurse; \ | |
1146 | } \ | |
1147 | while (0) | |
1148 | ||
1149 | tail_recurse: | |
e343483a | 1150 | /* Skip empty subtrees. */ |
1151 | if (!*tp) | |
1152 | return NULL_TREE; | |
1153 | ||
1154 | if (htab) | |
1155 | { | |
1156 | void **slot; | |
40570cc2 | 1157 | |
e343483a | 1158 | /* Don't walk the same tree twice, if the user has requested |
88b5b080 | 1159 | that we avoid doing so. */ |
e343483a | 1160 | if (htab_find (htab, *tp)) |
1161 | return NULL_TREE; | |
88b5b080 | 1162 | /* If we haven't already seen this node, add it to the table. */ |
e343483a | 1163 | slot = htab_find_slot (htab, *tp, INSERT); |
1164 | *slot = *tp; | |
1165 | } | |
1166 | ||
1167 | /* Call the function. */ | |
1168 | walk_subtrees = 1; | |
1169 | result = (*func) (tp, &walk_subtrees, data); | |
1170 | ||
1171 | /* If we found something, return it. */ | |
1172 | if (result) | |
1173 | return result; | |
1174 | ||
1175 | code = TREE_CODE (*tp); | |
1176 | ||
1177 | /* Even if we didn't, FUNC may have decided that there was nothing | |
1178 | interesting below this point in the tree. */ | |
1179 | if (!walk_subtrees) | |
1180 | { | |
1181 | if (statement_code_p (code) || code == TREE_LIST | |
e8602e56 | 1182 | || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp)) |
e343483a | 1183 | /* But we still need to check our siblings. */ |
357ec3f0 | 1184 | WALK_SUBTREE_TAIL (TREE_CHAIN (*tp)); |
e343483a | 1185 | else |
1186 | return NULL_TREE; | |
1187 | } | |
1188 | ||
1189 | /* Handle common cases up front. */ | |
1190 | if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)) | |
1191 | || TREE_CODE_CLASS (code) == 'r' | |
1192 | || TREE_CODE_CLASS (code) == 's') | |
1193 | { | |
1194 | int i, len; | |
1195 | ||
1196 | /* Set lineno here so we get the right instantiation context | |
1197 | if we call instantiate_decl from inlinable_function_p. */ | |
1198 | if (statement_code_p (code) && !STMT_LINENO_FOR_FN_P (*tp)) | |
1199 | lineno = STMT_LINENO (*tp); | |
1200 | ||
1201 | /* Walk over all the sub-trees of this operand. */ | |
1202 | len = first_rtl_op (code); | |
1203 | /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same. | |
1204 | But, we only want to walk once. */ | |
1205 | if (code == TARGET_EXPR | |
1206 | && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1)) | |
1207 | --len; | |
1208 | /* Go through the subtrees. We need to do this in forward order so | |
1209 | that the scope of a FOR_EXPR is handled properly. */ | |
1210 | for (i = 0; i < len; ++i) | |
1211 | WALK_SUBTREE (TREE_OPERAND (*tp, i)); | |
1212 | ||
1213 | /* For statements, we also walk the chain so that we cover the | |
1214 | entire statement tree. */ | |
1215 | if (statement_code_p (code)) | |
1216 | { | |
40570cc2 | 1217 | if (code == DECL_STMT |
1218 | && DECL_STMT_DECL (*tp) | |
e343483a | 1219 | && DECL_P (DECL_STMT_DECL (*tp))) |
1220 | { | |
1221 | /* Walk the DECL_INITIAL and DECL_SIZE. We don't want to walk | |
1222 | into declarations that are just mentioned, rather than | |
1223 | declared; they don't really belong to this part of the tree. | |
1224 | And, we can see cycles: the initializer for a declaration can | |
1225 | refer to the declaration itself. */ | |
1226 | WALK_SUBTREE (DECL_INITIAL (DECL_STMT_DECL (*tp))); | |
1227 | WALK_SUBTREE (DECL_SIZE (DECL_STMT_DECL (*tp))); | |
1228 | WALK_SUBTREE (DECL_SIZE_UNIT (DECL_STMT_DECL (*tp))); | |
1229 | } | |
1230 | ||
1231 | /* This can be tail-recursion optimized if we write it this way. */ | |
357ec3f0 | 1232 | WALK_SUBTREE_TAIL (TREE_CHAIN (*tp)); |
e343483a | 1233 | } |
1234 | ||
1235 | /* We didn't find what we were looking for. */ | |
1236 | return NULL_TREE; | |
1237 | } | |
1238 | else if (TREE_CODE_CLASS (code) == 'd') | |
1239 | { | |
357ec3f0 | 1240 | WALK_SUBTREE_TAIL (TREE_TYPE (*tp)); |
e343483a | 1241 | } |
1242 | ||
e8602e56 | 1243 | result = (*lang_hooks.tree_inlining.walk_subtrees) (tp, &walk_subtrees, func, |
1244 | data, htab); | |
e343483a | 1245 | if (result || ! walk_subtrees) |
1246 | return result; | |
1247 | ||
1248 | /* Not one of the easy cases. We must explicitly go through the | |
1249 | children. */ | |
1250 | switch (code) | |
1251 | { | |
1252 | case ERROR_MARK: | |
1253 | case IDENTIFIER_NODE: | |
1254 | case INTEGER_CST: | |
1255 | case REAL_CST: | |
886cfd4f | 1256 | case VECTOR_CST: |
e343483a | 1257 | case STRING_CST: |
1258 | case REAL_TYPE: | |
1259 | case COMPLEX_TYPE: | |
1260 | case VECTOR_TYPE: | |
1261 | case VOID_TYPE: | |
1262 | case BOOLEAN_TYPE: | |
1263 | case UNION_TYPE: | |
1264 | case ENUMERAL_TYPE: | |
1265 | case BLOCK: | |
1266 | case RECORD_TYPE: | |
1267 | /* None of thse have subtrees other than those already walked | |
1268 | above. */ | |
1269 | break; | |
1270 | ||
1271 | case POINTER_TYPE: | |
1272 | case REFERENCE_TYPE: | |
357ec3f0 | 1273 | WALK_SUBTREE_TAIL (TREE_TYPE (*tp)); |
e343483a | 1274 | break; |
1275 | ||
1276 | case TREE_LIST: | |
1277 | WALK_SUBTREE (TREE_VALUE (*tp)); | |
357ec3f0 | 1278 | WALK_SUBTREE_TAIL (TREE_CHAIN (*tp)); |
e343483a | 1279 | break; |
1280 | ||
1281 | case TREE_VEC: | |
1282 | { | |
1283 | int len = TREE_VEC_LENGTH (*tp); | |
357ec3f0 | 1284 | |
1285 | if (len == 0) | |
1286 | break; | |
1287 | ||
1288 | /* Walk all elements but the first. */ | |
1289 | while (--len) | |
e343483a | 1290 | WALK_SUBTREE (TREE_VEC_ELT (*tp, len)); |
357ec3f0 | 1291 | |
1292 | /* Now walk the first one as a tail call. */ | |
1293 | WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0)); | |
e343483a | 1294 | } |
e343483a | 1295 | |
1296 | case COMPLEX_CST: | |
1297 | WALK_SUBTREE (TREE_REALPART (*tp)); | |
357ec3f0 | 1298 | WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp)); |
e343483a | 1299 | |
1300 | case CONSTRUCTOR: | |
357ec3f0 | 1301 | WALK_SUBTREE_TAIL (CONSTRUCTOR_ELTS (*tp)); |
e343483a | 1302 | |
1303 | case METHOD_TYPE: | |
1304 | WALK_SUBTREE (TYPE_METHOD_BASETYPE (*tp)); | |
1305 | /* Fall through. */ | |
1306 | ||
1307 | case FUNCTION_TYPE: | |
1308 | WALK_SUBTREE (TREE_TYPE (*tp)); | |
1309 | { | |
1310 | tree arg = TYPE_ARG_TYPES (*tp); | |
1311 | ||
1312 | /* We never want to walk into default arguments. */ | |
1313 | for (; arg; arg = TREE_CHAIN (arg)) | |
1314 | WALK_SUBTREE (TREE_VALUE (arg)); | |
1315 | } | |
1316 | break; | |
1317 | ||
1318 | case ARRAY_TYPE: | |
1319 | WALK_SUBTREE (TREE_TYPE (*tp)); | |
357ec3f0 | 1320 | WALK_SUBTREE_TAIL (TYPE_DOMAIN (*tp)); |
e343483a | 1321 | |
1322 | case INTEGER_TYPE: | |
1323 | WALK_SUBTREE (TYPE_MIN_VALUE (*tp)); | |
357ec3f0 | 1324 | WALK_SUBTREE_TAIL (TYPE_MAX_VALUE (*tp)); |
e343483a | 1325 | |
1326 | case OFFSET_TYPE: | |
1327 | WALK_SUBTREE (TREE_TYPE (*tp)); | |
357ec3f0 | 1328 | WALK_SUBTREE_TAIL (TYPE_OFFSET_BASETYPE (*tp)); |
e343483a | 1329 | |
1330 | default: | |
1331 | abort (); | |
1332 | } | |
1333 | ||
1334 | /* We didn't find what we were looking for. */ | |
1335 | return NULL_TREE; | |
1336 | ||
1337 | #undef WALK_SUBTREE | |
1338 | } | |
1339 | ||
40570cc2 | 1340 | /* Like walk_tree, but does not walk duplicate nodes more than |
e343483a | 1341 | once. */ |
1342 | ||
40570cc2 | 1343 | tree |
e343483a | 1344 | walk_tree_without_duplicates (tp, func, data) |
1345 | tree *tp; | |
1346 | walk_tree_fn func; | |
1347 | void *data; | |
1348 | { | |
1349 | tree result; | |
1350 | htab_t htab; | |
1351 | ||
1352 | htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL); | |
1353 | result = walk_tree (tp, func, data, htab); | |
1354 | htab_delete (htab); | |
1355 | return result; | |
1356 | } | |
1357 | ||
1358 | /* Passed to walk_tree. Copies the node pointed to, if appropriate. */ | |
1359 | ||
1360 | tree | |
1361 | copy_tree_r (tp, walk_subtrees, data) | |
1362 | tree *tp; | |
1363 | int *walk_subtrees; | |
1364 | void *data ATTRIBUTE_UNUSED; | |
1365 | { | |
1366 | enum tree_code code = TREE_CODE (*tp); | |
1367 | ||
1368 | /* We make copies of most nodes. */ | |
1369 | if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)) | |
1370 | || TREE_CODE_CLASS (code) == 'r' | |
1371 | || TREE_CODE_CLASS (code) == 'c' | |
1372 | || TREE_CODE_CLASS (code) == 's' | |
1373 | || code == TREE_LIST | |
1374 | || code == TREE_VEC | |
e8602e56 | 1375 | || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp)) |
e343483a | 1376 | { |
1377 | /* Because the chain gets clobbered when we make a copy, we save it | |
1378 | here. */ | |
1379 | tree chain = TREE_CHAIN (*tp); | |
1380 | ||
1381 | /* Copy the node. */ | |
1382 | *tp = copy_node (*tp); | |
1383 | ||
1384 | /* Now, restore the chain, if appropriate. That will cause | |
1385 | walk_tree to walk into the chain as well. */ | |
1386 | if (code == PARM_DECL || code == TREE_LIST | |
e8602e56 | 1387 | || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp) |
e343483a | 1388 | || statement_code_p (code)) |
1389 | TREE_CHAIN (*tp) = chain; | |
1390 | ||
1391 | /* For now, we don't update BLOCKs when we make copies. So, we | |
1392 | have to nullify all scope-statements. */ | |
1393 | if (TREE_CODE (*tp) == SCOPE_STMT) | |
1394 | SCOPE_STMT_BLOCK (*tp) = NULL_TREE; | |
1395 | } | |
1396 | else if (TREE_CODE_CLASS (code) == 't') | |
1397 | /* There's no need to copy types, or anything beneath them. */ | |
1398 | *walk_subtrees = 0; | |
1399 | ||
1400 | return NULL_TREE; | |
1401 | } | |
1402 | ||
1403 | /* The SAVE_EXPR pointed to by TP is being copied. If ST contains | |
1404 | information indicating to what new SAVE_EXPR this one should be | |
1405 | mapped, use that one. Otherwise, create a new node and enter it in | |
1406 | ST. FN is the function into which the copy will be placed. */ | |
1407 | ||
1408 | void | |
1409 | remap_save_expr (tp, st_, fn, walk_subtrees) | |
1410 | tree *tp; | |
1411 | void *st_; | |
1412 | tree fn; | |
1413 | int *walk_subtrees; | |
1414 | { | |
1415 | splay_tree st = (splay_tree) st_; | |
1416 | splay_tree_node n; | |
1417 | ||
1418 | /* See if we already encountered this SAVE_EXPR. */ | |
1419 | n = splay_tree_lookup (st, (splay_tree_key) *tp); | |
40570cc2 | 1420 | |
e343483a | 1421 | /* If we didn't already remap this SAVE_EXPR, do so now. */ |
1422 | if (!n) | |
1423 | { | |
1424 | tree t = copy_node (*tp); | |
1425 | ||
1426 | /* The SAVE_EXPR is now part of the function into which we | |
1427 | are inlining this body. */ | |
1428 | SAVE_EXPR_CONTEXT (t) = fn; | |
1429 | /* And we haven't evaluated it yet. */ | |
1430 | SAVE_EXPR_RTL (t) = NULL_RTX; | |
1431 | /* Remember this SAVE_EXPR. */ | |
1432 | n = splay_tree_insert (st, | |
1433 | (splay_tree_key) *tp, | |
1434 | (splay_tree_value) t); | |
da3bde1a | 1435 | /* Make sure we don't remap an already-remapped SAVE_EXPR. */ |
1436 | splay_tree_insert (st, (splay_tree_key) t, | |
1437 | (splay_tree_value) error_mark_node); | |
e343483a | 1438 | } |
1439 | else | |
1440 | /* We've already walked into this SAVE_EXPR, so we needn't do it | |
1441 | again. */ | |
1442 | *walk_subtrees = 0; | |
1443 | ||
1444 | /* Replace this SAVE_EXPR with the copy. */ | |
1445 | *tp = (tree) n->value; | |
1446 | } |