]>
Commit | Line | Data |
---|---|---|
d7c6d889 | 1 | /* Callgraph based intraprocedural optimizations. |
ae01b312 | 2 | Copyright (C) 2003 Free Software Foundation, Inc. |
3 | Contributed by Jan Hubicka | |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it under | |
8 | the terms of the GNU General Public License as published by the Free | |
9 | Software Foundation; either version 2, or (at your option) any later | |
10 | version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GCC; see the file COPYING. If not, write to the Free | |
19 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
20 | 02111-1307, USA. */ | |
21 | ||
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "tm.h" | |
26 | #include "tree.h" | |
27 | #include "tree-inline.h" | |
28 | #include "langhooks.h" | |
29 | #include "hashtab.h" | |
30 | #include "toplev.h" | |
31 | #include "flags.h" | |
32 | #include "ggc.h" | |
33 | #include "debug.h" | |
34 | #include "target.h" | |
35 | #include "cgraph.h" | |
80a85d8a | 36 | #include "diagnostic.h" |
f79b6507 | 37 | #include "timevar.h" |
d7c6d889 | 38 | #include "params.h" |
39 | #include "fibheap.h" | |
40 | #include "c-common.h" | |
41 | ||
42 | #define INSNS_PER_CALL 10 | |
ae01b312 | 43 | |
d9d9733a | 44 | static void cgraph_expand_functions (void); |
45 | static void cgraph_mark_functions_to_output (void); | |
46 | static void cgraph_expand_function (struct cgraph_node *); | |
47 | static tree record_call_1 (tree *, int *, void *); | |
48 | static void cgraph_mark_local_functions (void); | |
49 | static void cgraph_optimize_function (struct cgraph_node *); | |
2ff66ee0 | 50 | static bool cgraph_default_inline_p (struct cgraph_node *n); |
51 | static void cgraph_analyze_function (struct cgraph_node *node); | |
ae01b312 | 52 | |
d7c6d889 | 53 | /* Statistics we collect about inlining algorithm. */ |
54 | static int ncalls_inlined; | |
55 | static int nfunctions_inlined; | |
56 | static int initial_insns; | |
57 | static int overall_insns; | |
58 | ||
25bb88de | 59 | /* Records tree nodes seen in cgraph_create_edges. Simply using |
60 | walk_tree_without_duplicates doesn't guarantee each node is visited | |
61 | once because it gets a new htab upon each recursive call from | |
62 | record_calls_1. */ | |
63 | static htab_t visited_nodes; | |
64 | ||
2c0b522d | 65 | /* Determine if function DECL is needed. That is, visible to something |
66 | either outside this translation unit, something magic in the system | |
67 | configury, or (if not doing unit-at-a-time) to something we havn't | |
68 | seen yet. */ | |
69 | ||
70 | static bool | |
71 | decide_is_function_needed (struct cgraph_node *node, tree decl) | |
72 | { | |
73 | /* If we decided it was needed before, but at the time we didn't have | |
74 | the body of the function available, then it's still needed. We have | |
75 | to go back and re-check its dependencies now. */ | |
76 | if (node->needed) | |
77 | return true; | |
78 | ||
79 | /* Externally visible functions must be output. The exception is | |
80 | COMDAT functions that must be output only when they are needed. */ | |
81 | if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)) | |
82 | return true; | |
83 | ||
84 | /* Constructors and destructors are reachable from the runtime by | |
85 | some mechanism. */ | |
86 | if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl)) | |
87 | return true; | |
88 | ||
89 | /* If the user told us it is used, then it must be so. */ | |
90 | if (lookup_attribute ("used", DECL_ATTRIBUTES (decl))) | |
91 | return true; | |
92 | ||
93 | /* ??? If the assembler name is set by hand, it is possible to assemble | |
94 | the name later after finalizing the function and the fact is noticed | |
95 | in assemble_name then. This is arguably a bug. */ | |
96 | if (DECL_ASSEMBLER_NAME_SET_P (decl) | |
97 | && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))) | |
98 | return true; | |
99 | ||
100 | if (flag_unit_at_a_time) | |
101 | return false; | |
102 | ||
103 | /* If not doing unit at a time, then we'll only defer this function | |
104 | if its marked for inlining. Otherwise we want to emit it now. */ | |
105 | ||
106 | /* "extern inline" functions are never output locally. */ | |
107 | if (DECL_EXTERNAL (decl)) | |
108 | return false; | |
c08871a9 | 109 | /* We want to emit COMDAT functions only when they turns out to be neccesary. */ |
110 | if (DECL_COMDAT (decl)) | |
2c0b522d | 111 | return false; |
112 | if (!DECL_INLINE (decl) | |
113 | || (!node->local.disregard_inline_limits | |
114 | /* When declared inline, defer even the uninlinable functions. | |
115 | This allows them to be elliminated when unused. */ | |
116 | && !DECL_DECLARED_INLINE_P (decl) | |
117 | && (node->local.inlinable || !cgraph_default_inline_p (node)))) | |
118 | return true; | |
119 | ||
120 | return false; | |
121 | } | |
122 | ||
c08871a9 | 123 | /* When not doing unit-at-a-time, output all functions enqueued. |
124 | Return true when such a functions were found. */ | |
125 | static bool | |
126 | cgraph_assemble_pending_functions (void) | |
127 | { | |
128 | bool output = false; | |
129 | ||
130 | if (flag_unit_at_a_time) | |
131 | return false; | |
132 | ||
133 | while (cgraph_nodes_queue) | |
134 | { | |
135 | struct cgraph_node *n = cgraph_nodes_queue; | |
136 | ||
137 | cgraph_nodes_queue = cgraph_nodes_queue->next_needed; | |
138 | if (!n->origin && !DECL_EXTERNAL (n->decl)) | |
139 | cgraph_expand_function (n); | |
140 | output = true; | |
141 | } | |
142 | return output; | |
143 | } | |
144 | ||
ae01b312 | 145 | /* Analyze function once it is parsed. Set up the local information |
d01481af | 146 | available - create cgraph edges for function calls via BODY. */ |
ae01b312 | 147 | |
148 | void | |
0e4b8226 | 149 | cgraph_finalize_function (tree decl) |
ae01b312 | 150 | { |
151 | struct cgraph_node *node = cgraph_node (decl); | |
152 | ||
c08871a9 | 153 | if (node->local.finalized) |
154 | { | |
155 | /* As an GCC extension we allow redefinition of the function. The | |
156 | semantics when both copies of bodies differ is not well defined. We | |
157 | replace the old body with new body so in unit at a time mode we always | |
158 | use new body, while in normal mode we may end up with old body inlined | |
159 | into some functions and new body expanded and inlined in others. | |
160 | ||
161 | ??? It may make more sense to use one body for inlining and other body | |
162 | for expanding the function but this is dificult to do. */ | |
638531ad | 163 | /* Reset our datastructures so we can analyze the function body |
164 | again. */ | |
165 | memset (&node->local, 0, sizeof (node->local)); | |
166 | memset (&node->global, 0, sizeof (node->global)); | |
167 | memset (&node->rtl, 0, sizeof (node->rtl)); | |
ec1e35b2 | 168 | node->analyzed = false; |
638531ad | 169 | if (node->output) |
170 | abort (); | |
171 | while (node->callees) | |
172 | cgraph_remove_call (node->decl, node->callees->callee->decl); | |
173 | /* We may need to re-queue the node for assembling in case | |
174 | we already proceeded it and ignored as not needed. */ | |
175 | if (node->reachable && !flag_unit_at_a_time) | |
c08871a9 | 176 | { |
638531ad | 177 | struct cgraph_node *n; |
178 | ||
179 | for (n = cgraph_nodes_queue; n; n = n->next_needed) | |
180 | if (n == node) | |
181 | break; | |
182 | if (!n) | |
183 | node->reachable = 0; | |
c08871a9 | 184 | } |
c08871a9 | 185 | } |
186 | notice_global_symbol (decl); | |
ae01b312 | 187 | node->decl = decl; |
79bb87b4 | 188 | node->local.finalized = true; |
ae01b312 | 189 | |
2c0b522d | 190 | /* If not unit at a time, then we need to create the call graph |
191 | now, so that called functions can be queued and emitted now. */ | |
2ff66ee0 | 192 | if (!flag_unit_at_a_time) |
193 | cgraph_analyze_function (node); | |
2ff66ee0 | 194 | |
2c0b522d | 195 | if (decide_is_function_needed (node, decl)) |
196 | cgraph_mark_needed_node (node); | |
197 | ||
198 | /* If not unit at a time, go ahead and emit everything we've | |
c08871a9 | 199 | found to be reachable at this time. Do this only at top-level. */ |
200 | if (!node->origin) | |
201 | cgraph_assemble_pending_functions (); | |
3d7bfc56 | 202 | |
2c0b522d | 203 | /* If we've not yet emitted decl, tell the debug info about it. */ |
204 | if (flag_unit_at_a_time || !node->reachable) | |
205 | (*debug_hooks->deferred_inline_function) (decl); | |
ae01b312 | 206 | } |
207 | ||
ae01b312 | 208 | /* Walk tree and record all calls. Called via walk_tree. */ |
209 | static tree | |
d9d9733a | 210 | record_call_1 (tree *tp, int *walk_subtrees, void *data) |
ae01b312 | 211 | { |
ec1e35b2 | 212 | tree t = *tp; |
213 | ||
214 | switch (TREE_CODE (t)) | |
ae01b312 | 215 | { |
ec1e35b2 | 216 | case VAR_DECL: |
217 | /* ??? Really, we should mark this decl as *potentially* referenced | |
218 | by this function and re-examine whether the decl is actually used | |
219 | after rtl has been generated. */ | |
220 | if (TREE_STATIC (t)) | |
221 | cgraph_varpool_mark_needed_node (cgraph_varpool_node (t)); | |
222 | break; | |
223 | ||
224 | case ADDR_EXPR: | |
225 | if (flag_unit_at_a_time) | |
226 | { | |
227 | /* Record dereferences to the functions. This makes the | |
228 | functions reachable unconditionally. */ | |
229 | tree decl = TREE_OPERAND (*tp, 0); | |
230 | if (TREE_CODE (decl) == FUNCTION_DECL) | |
231 | cgraph_mark_needed_node (cgraph_node (decl)); | |
232 | } | |
233 | break; | |
234 | ||
235 | case CALL_EXPR: | |
236 | { | |
237 | tree decl = get_callee_fndecl (*tp); | |
238 | if (decl && TREE_CODE (decl) == FUNCTION_DECL) | |
239 | { | |
240 | if (DECL_BUILT_IN (decl)) | |
241 | return NULL; | |
242 | cgraph_record_call (data, decl); | |
243 | ||
244 | /* When we see a function call, we don't want to look at the | |
245 | function reference in the ADDR_EXPR that is hanging from | |
246 | the CALL_EXPR we're examining here, because we would | |
247 | conclude incorrectly that the function's address could be | |
248 | taken by something that is not a function call. So only | |
249 | walk the function parameter list, skip the other subtrees. */ | |
250 | ||
251 | walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data, | |
252 | visited_nodes); | |
253 | *walk_subtrees = 0; | |
254 | } | |
255 | break; | |
256 | } | |
257 | ||
258 | default: | |
259 | /* Save some cycles by not walking types and declaration as we | |
260 | won't find anything useful there anyway. */ | |
261 | if (DECL_P (*tp) || TYPE_P (*tp)) | |
ae01b312 | 262 | { |
ae01b312 | 263 | *walk_subtrees = 0; |
ec1e35b2 | 264 | break; |
ae01b312 | 265 | } |
ec1e35b2 | 266 | |
267 | if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE) | |
268 | return (*lang_hooks.callgraph.analyze_expr) (tp, walk_subtrees, data); | |
269 | break; | |
ae01b312 | 270 | } |
ec1e35b2 | 271 | |
ae01b312 | 272 | return NULL; |
273 | } | |
274 | ||
e6d2b2d8 | 275 | /* Create cgraph edges for function calls inside BODY from DECL. */ |
ae01b312 | 276 | |
277 | void | |
d9d9733a | 278 | cgraph_create_edges (tree decl, tree body) |
ae01b312 | 279 | { |
e6d2b2d8 | 280 | /* The nodes we're interested in are never shared, so walk |
281 | the tree ignoring duplicates. */ | |
25bb88de | 282 | visited_nodes = htab_create (37, htab_hash_pointer, |
283 | htab_eq_pointer, NULL); | |
284 | walk_tree (&body, record_call_1, decl, visited_nodes); | |
285 | htab_delete (visited_nodes); | |
286 | visited_nodes = NULL; | |
ae01b312 | 287 | } |
288 | ||
0785e435 | 289 | /* Analyze the function scheduled to be output. */ |
290 | static void | |
291 | cgraph_analyze_function (struct cgraph_node *node) | |
292 | { | |
293 | tree decl = node->decl; | |
294 | ||
ec1e35b2 | 295 | current_function_decl = decl; |
0785e435 | 296 | |
297 | /* First kill forward declaration so reverse inlining works properly. */ | |
298 | cgraph_create_edges (decl, DECL_SAVED_TREE (decl)); | |
299 | ||
300 | node->local.inlinable = tree_inlinable_function_p (decl); | |
301 | if (!DECL_ESTIMATED_INSNS (decl)) | |
302 | DECL_ESTIMATED_INSNS (decl) | |
303 | = (*lang_hooks.tree_inlining.estimate_num_insns) (decl); | |
304 | node->local.self_insns = DECL_ESTIMATED_INSNS (decl); | |
305 | if (node->local.inlinable) | |
306 | node->local.disregard_inline_limits | |
307 | = (*lang_hooks.tree_inlining.disregard_inline_limits) (decl); | |
308 | ||
309 | /* Inlining characteristics are maintained by the cgraph_mark_inline. */ | |
310 | node->global.insns = node->local.self_insns; | |
ec1e35b2 | 311 | if (!DECL_EXTERNAL (decl)) |
0785e435 | 312 | { |
313 | node->global.cloned_times = 1; | |
314 | node->global.will_be_output = true; | |
315 | } | |
316 | ||
ec1e35b2 | 317 | node->analyzed = true; |
c08871a9 | 318 | current_function_decl = NULL; |
0785e435 | 319 | } |
320 | ||
ae01b312 | 321 | /* Analyze the whole compilation unit once it is parsed completely. */ |
322 | ||
323 | void | |
d9d9733a | 324 | cgraph_finalize_compilation_unit (void) |
ae01b312 | 325 | { |
326 | struct cgraph_node *node; | |
ae01b312 | 327 | |
2ff66ee0 | 328 | if (!flag_unit_at_a_time) |
c08871a9 | 329 | { |
330 | cgraph_assemble_pending_functions (); | |
331 | return; | |
332 | } | |
2ff66ee0 | 333 | |
229dcfae | 334 | cgraph_varpool_assemble_pending_decls (); |
d7c6d889 | 335 | if (!quiet_flag) |
336 | fprintf (stderr, "\nAnalyzing compilation unit\n"); | |
229dcfae | 337 | |
f79b6507 | 338 | timevar_push (TV_CGRAPH); |
339 | if (cgraph_dump_file) | |
ae01b312 | 340 | { |
f79b6507 | 341 | fprintf (cgraph_dump_file, "\nInitial entry points:"); |
3d7bfc56 | 342 | for (node = cgraph_nodes; node; node = node->next) |
343 | if (node->needed && DECL_SAVED_TREE (node->decl)) | |
f79b6507 | 344 | fprintf (cgraph_dump_file, " %s", cgraph_node_name (node)); |
345 | fprintf (cgraph_dump_file, "\n"); | |
ae01b312 | 346 | } |
347 | ||
e6d2b2d8 | 348 | /* Propagate reachability flag and lower representation of all reachable |
349 | functions. In the future, lowering will introduce new functions and | |
350 | new entry points on the way (by template instantiation and virtual | |
351 | method table generation for instance). */ | |
3d7bfc56 | 352 | while (cgraph_nodes_queue) |
ae01b312 | 353 | { |
0785e435 | 354 | struct cgraph_edge *edge; |
3d7bfc56 | 355 | tree decl = cgraph_nodes_queue->decl; |
356 | ||
357 | node = cgraph_nodes_queue; | |
d87976fb | 358 | cgraph_nodes_queue = cgraph_nodes_queue->next_needed; |
ae01b312 | 359 | |
638531ad | 360 | /* ??? It is possible to create extern inline function and later using |
361 | weak alas attribute to kill it's body. See | |
362 | gcc.c-torture/compile/20011119-1.c */ | |
363 | if (!DECL_SAVED_TREE (decl)) | |
364 | continue; | |
365 | ||
ec1e35b2 | 366 | if (node->analyzed || !node->reachable || !DECL_SAVED_TREE (decl)) |
ae01b312 | 367 | abort (); |
368 | ||
0785e435 | 369 | cgraph_analyze_function (node); |
2c0b522d | 370 | |
ae01b312 | 371 | for (edge = node->callees; edge; edge = edge->next_callee) |
0785e435 | 372 | if (!edge->callee->reachable) |
2c0b522d | 373 | cgraph_mark_reachable_node (edge->callee); |
374 | ||
229dcfae | 375 | cgraph_varpool_assemble_pending_decls (); |
ae01b312 | 376 | } |
2c0b522d | 377 | |
3d7bfc56 | 378 | /* Collect entry points to the unit. */ |
379 | ||
f79b6507 | 380 | if (cgraph_dump_file) |
3d7bfc56 | 381 | { |
f79b6507 | 382 | fprintf (cgraph_dump_file, "\nUnit entry points:"); |
3d7bfc56 | 383 | for (node = cgraph_nodes; node; node = node->next) |
384 | if (node->needed && DECL_SAVED_TREE (node->decl)) | |
f79b6507 | 385 | fprintf (cgraph_dump_file, " %s", cgraph_node_name (node)); |
386 | fprintf (cgraph_dump_file, "\n"); | |
0785e435 | 387 | dump_cgraph (cgraph_dump_file); |
3d7bfc56 | 388 | } |
e6d2b2d8 | 389 | |
f79b6507 | 390 | if (cgraph_dump_file) |
391 | fprintf (cgraph_dump_file, "\nReclaiming functions:"); | |
ae01b312 | 392 | |
393 | for (node = cgraph_nodes; node; node = node->next) | |
394 | { | |
395 | tree decl = node->decl; | |
396 | ||
397 | if (!node->reachable && DECL_SAVED_TREE (decl)) | |
398 | { | |
961e3b13 | 399 | cgraph_remove_node (node); |
f79b6507 | 400 | if (cgraph_dump_file) |
401 | fprintf (cgraph_dump_file, " %s", cgraph_node_name (node)); | |
ae01b312 | 402 | } |
403 | } | |
f79b6507 | 404 | if (cgraph_dump_file) |
405 | fprintf (cgraph_dump_file, "\n"); | |
ae01b312 | 406 | ggc_collect (); |
f79b6507 | 407 | timevar_pop (TV_CGRAPH); |
ae01b312 | 408 | } |
409 | ||
410 | /* Figure out what functions we want to assemble. */ | |
411 | ||
412 | static void | |
d9d9733a | 413 | cgraph_mark_functions_to_output (void) |
ae01b312 | 414 | { |
415 | struct cgraph_node *node; | |
416 | ||
ae01b312 | 417 | for (node = cgraph_nodes; node; node = node->next) |
418 | { | |
419 | tree decl = node->decl; | |
d7c6d889 | 420 | struct cgraph_edge *e; |
421 | if (node->output) | |
422 | abort (); | |
423 | ||
424 | for (e = node->callers; e; e = e->next_caller) | |
425 | if (!e->inline_call) | |
426 | break; | |
ae01b312 | 427 | |
e6d2b2d8 | 428 | /* We need to output all local functions that are used and not |
429 | always inlined, as well as those that are reachable from | |
430 | outside the current compilation unit. */ | |
ae01b312 | 431 | if (DECL_SAVED_TREE (decl) |
432 | && (node->needed | |
d7c6d889 | 433 | || (e && node->reachable)) |
ae01b312 | 434 | && !TREE_ASM_WRITTEN (decl) && !node->origin |
435 | && !DECL_EXTERNAL (decl)) | |
436 | node->output = 1; | |
437 | } | |
438 | } | |
439 | ||
961e3b13 | 440 | /* Optimize the function before expansion. */ |
e6d2b2d8 | 441 | |
961e3b13 | 442 | static void |
d9d9733a | 443 | cgraph_optimize_function (struct cgraph_node *node) |
961e3b13 | 444 | { |
445 | tree decl = node->decl; | |
446 | ||
f79b6507 | 447 | timevar_push (TV_INTEGRATION); |
d7c6d889 | 448 | /* optimize_inline_calls avoids inlining of current_function_decl. */ |
1bd51781 | 449 | current_function_decl = decl; |
961e3b13 | 450 | if (flag_inline_trees) |
451 | optimize_inline_calls (decl); | |
452 | if (node->nested) | |
453 | { | |
454 | for (node = node->nested; node; node = node->next_nested) | |
455 | cgraph_optimize_function (node); | |
456 | } | |
f79b6507 | 457 | timevar_pop (TV_INTEGRATION); |
961e3b13 | 458 | } |
459 | ||
ae01b312 | 460 | /* Expand function specified by NODE. */ |
e6d2b2d8 | 461 | |
ae01b312 | 462 | static void |
d9d9733a | 463 | cgraph_expand_function (struct cgraph_node *node) |
ae01b312 | 464 | { |
465 | tree decl = node->decl; | |
d7c6d889 | 466 | struct cgraph_edge *e; |
ae01b312 | 467 | |
468 | announce_function (decl); | |
961e3b13 | 469 | |
470 | cgraph_optimize_function (node); | |
80a85d8a | 471 | |
e6d2b2d8 | 472 | /* Generate RTL for the body of DECL. Nested functions are expanded |
473 | via lang_expand_decl_stmt. */ | |
ae01b312 | 474 | (*lang_hooks.callgraph.expand_function) (decl); |
961e3b13 | 475 | |
2ff66ee0 | 476 | if (!flag_unit_at_a_time) |
477 | { | |
478 | if (!node->local.inlinable | |
479 | || (!node->local.disregard_inline_limits | |
480 | && !cgraph_default_inline_p (node))) | |
481 | DECL_SAVED_TREE (node->decl) = NULL; | |
482 | } | |
483 | else | |
484 | { | |
485 | for (e = node->callers; e; e = e->next_caller) | |
486 | if (e->inline_call) | |
487 | break; | |
488 | if (!e) | |
489 | DECL_SAVED_TREE (decl) = NULL; | |
490 | } | |
ae01b312 | 491 | current_function_decl = NULL; |
492 | } | |
493 | ||
d7c6d889 | 494 | /* Fill array order with all nodes with output flag set in the reverse |
495 | topological order. */ | |
496 | static int | |
497 | cgraph_postorder (struct cgraph_node **order) | |
ae01b312 | 498 | { |
499 | struct cgraph_node *node, *node2; | |
ae01b312 | 500 | int stack_size = 0; |
501 | int order_pos = 0; | |
502 | struct cgraph_edge *edge, last; | |
ae01b312 | 503 | |
d7c6d889 | 504 | struct cgraph_node **stack = |
746149b7 | 505 | xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); |
ae01b312 | 506 | |
e6d2b2d8 | 507 | /* We have to deal with cycles nicely, so use a depth first traversal |
508 | output algorithm. Ignore the fact that some functions won't need | |
509 | to be output and put them into order as well, so we get dependencies | |
510 | right through intline functions. */ | |
ae01b312 | 511 | for (node = cgraph_nodes; node; node = node->next) |
512 | node->aux = NULL; | |
513 | for (node = cgraph_nodes; node; node = node->next) | |
3d7bfc56 | 514 | if (!node->aux) |
ae01b312 | 515 | { |
516 | node2 = node; | |
517 | if (!node->callers) | |
518 | node->aux = &last; | |
519 | else | |
520 | node->aux = node->callers; | |
521 | while (node2) | |
522 | { | |
523 | while (node2->aux != &last) | |
524 | { | |
525 | edge = node2->aux; | |
526 | if (edge->next_caller) | |
527 | node2->aux = edge->next_caller; | |
528 | else | |
529 | node2->aux = &last; | |
530 | if (!edge->caller->aux) | |
531 | { | |
532 | if (!edge->caller->callers) | |
533 | edge->caller->aux = &last; | |
534 | else | |
535 | edge->caller->aux = edge->caller->callers; | |
536 | stack[stack_size++] = node2; | |
537 | node2 = edge->caller; | |
538 | break; | |
539 | } | |
540 | } | |
541 | if (node2->aux == &last) | |
542 | { | |
543 | order[order_pos++] = node2; | |
544 | if (stack_size) | |
545 | node2 = stack[--stack_size]; | |
546 | else | |
547 | node2 = NULL; | |
548 | } | |
549 | } | |
550 | } | |
d7c6d889 | 551 | free (stack); |
552 | return order_pos; | |
553 | } | |
554 | ||
555 | #define INLINED_TIMES(node) ((size_t)(node)->aux) | |
556 | #define SET_INLINED_TIMES(node,times) ((node)->aux = (void *)(times)) | |
557 | ||
558 | /* Return list of nodes we decided to inline NODE into, set their output | |
d9d9733a | 559 | flag and compute INLINED_TIMES. |
d7c6d889 | 560 | |
561 | We do simple backtracing to get INLINED_TIMES right. This should not be | |
562 | expensive as we limit the amount of inlining. Alternatively we may first | |
563 | discover set of nodes, topologically sort these and propagate | |
564 | INLINED_TIMES */ | |
565 | ||
566 | static int | |
567 | cgraph_inlined_into (struct cgraph_node *node, struct cgraph_node **array) | |
568 | { | |
569 | int nfound = 0; | |
570 | struct cgraph_edge **stack; | |
571 | struct cgraph_edge *e, *e1; | |
572 | int sp; | |
573 | int i; | |
574 | ||
575 | /* Fast path: since we traverse in mostly topological order, we will likely | |
576 | find no edges. */ | |
577 | for (e = node->callers; e; e = e->next_caller) | |
578 | if (e->inline_call) | |
579 | break; | |
580 | ||
581 | if (!e) | |
582 | return 0; | |
583 | ||
584 | /* Allocate stack for back-tracking up callgraph. */ | |
585 | stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge)); | |
586 | sp = 0; | |
587 | ||
588 | /* Push the first edge on to the stack. */ | |
589 | stack[sp++] = e; | |
590 | ||
591 | while (sp) | |
ae01b312 | 592 | { |
d7c6d889 | 593 | struct cgraph_node *caller; |
594 | ||
595 | /* Look at the edge on the top of the stack. */ | |
596 | e = stack[sp - 1]; | |
597 | caller = e->caller; | |
598 | ||
599 | /* Check if the caller destination has been visited yet. */ | |
600 | if (!caller->output) | |
ae01b312 | 601 | { |
d7c6d889 | 602 | array[nfound++] = e->caller; |
603 | /* Mark that we have visited the destination. */ | |
604 | caller->output = true; | |
605 | SET_INLINED_TIMES (caller, 0); | |
606 | } | |
607 | SET_INLINED_TIMES (caller, INLINED_TIMES (caller) + 1); | |
608 | ||
609 | for (e1 = caller->callers; e1; e1 = e1->next_caller) | |
610 | if (e1->inline_call) | |
611 | break; | |
612 | if (e1) | |
613 | stack[sp++] = e1; | |
614 | else | |
615 | { | |
616 | while (true) | |
617 | { | |
618 | for (e1 = e->next_caller; e1; e1 = e1->next_caller) | |
619 | if (e1->inline_call) | |
620 | break; | |
621 | ||
622 | if (e1) | |
623 | { | |
624 | stack[sp - 1] = e1; | |
625 | break; | |
626 | } | |
627 | else | |
628 | { | |
629 | sp--; | |
630 | if (!sp) | |
631 | break; | |
632 | e = stack[sp - 1]; | |
633 | } | |
634 | } | |
ae01b312 | 635 | } |
636 | } | |
d7c6d889 | 637 | |
ae01b312 | 638 | free (stack); |
d7c6d889 | 639 | |
640 | ||
641 | if (cgraph_dump_file) | |
642 | { | |
643 | fprintf (cgraph_dump_file, "Found inline predecesors of %s:", | |
644 | cgraph_node_name (node)); | |
645 | for (i = 0; i < nfound; i++) | |
646 | { | |
647 | fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i])); | |
648 | if (INLINED_TIMES (array[i]) != 1) | |
649 | fprintf (cgraph_dump_file, " (%i times)", | |
c50db3a3 | 650 | (int)INLINED_TIMES (array[i])); |
d7c6d889 | 651 | } |
652 | fprintf (cgraph_dump_file, "\n"); | |
653 | } | |
654 | ||
655 | return nfound; | |
ae01b312 | 656 | } |
657 | ||
d7c6d889 | 658 | /* Return list of nodes we decided to inline into NODE, set their output |
d9d9733a | 659 | flag and compute INLINED_TIMES. |
d7c6d889 | 660 | |
661 | This function is identical to cgraph_inlined_into with callers and callees | |
662 | nodes swapped. */ | |
663 | ||
664 | static int | |
665 | cgraph_inlined_callees (struct cgraph_node *node, struct cgraph_node **array) | |
666 | { | |
667 | int nfound = 0; | |
668 | struct cgraph_edge **stack; | |
669 | struct cgraph_edge *e, *e1; | |
670 | int sp; | |
671 | int i; | |
672 | ||
673 | /* Fast path: since we traverse in mostly topological order, we will likely | |
674 | find no edges. */ | |
675 | for (e = node->callees; e; e = e->next_callee) | |
676 | if (e->inline_call) | |
677 | break; | |
678 | ||
679 | if (!e) | |
680 | return 0; | |
681 | ||
682 | /* Allocate stack for back-tracking up callgraph. */ | |
683 | stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge)); | |
684 | sp = 0; | |
685 | ||
686 | /* Push the first edge on to the stack. */ | |
687 | stack[sp++] = e; | |
688 | ||
689 | while (sp) | |
690 | { | |
691 | struct cgraph_node *callee; | |
692 | ||
693 | /* Look at the edge on the top of the stack. */ | |
694 | e = stack[sp - 1]; | |
695 | callee = e->callee; | |
696 | ||
697 | /* Check if the callee destination has been visited yet. */ | |
698 | if (!callee->output) | |
699 | { | |
700 | array[nfound++] = e->callee; | |
701 | /* Mark that we have visited the destination. */ | |
702 | callee->output = true; | |
703 | SET_INLINED_TIMES (callee, 0); | |
704 | } | |
705 | SET_INLINED_TIMES (callee, INLINED_TIMES (callee) + 1); | |
706 | ||
707 | for (e1 = callee->callees; e1; e1 = e1->next_callee) | |
708 | if (e1->inline_call) | |
709 | break; | |
710 | if (e1) | |
711 | stack[sp++] = e1; | |
712 | else | |
713 | { | |
714 | while (true) | |
715 | { | |
716 | for (e1 = e->next_callee; e1; e1 = e1->next_callee) | |
717 | if (e1->inline_call) | |
718 | break; | |
719 | ||
720 | if (e1) | |
721 | { | |
722 | stack[sp - 1] = e1; | |
723 | break; | |
724 | } | |
725 | else | |
726 | { | |
727 | sp--; | |
728 | if (!sp) | |
729 | break; | |
730 | e = stack[sp - 1]; | |
731 | } | |
732 | } | |
733 | } | |
734 | } | |
735 | ||
736 | free (stack); | |
737 | ||
738 | if (cgraph_dump_file) | |
739 | { | |
740 | fprintf (cgraph_dump_file, "Found inline successors of %s:", | |
741 | cgraph_node_name (node)); | |
742 | for (i = 0; i < nfound; i++) | |
743 | { | |
744 | fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i])); | |
745 | if (INLINED_TIMES (array[i]) != 1) | |
746 | fprintf (cgraph_dump_file, " (%i times)", | |
c50db3a3 | 747 | (int)INLINED_TIMES (array[i])); |
d7c6d889 | 748 | } |
749 | fprintf (cgraph_dump_file, "\n"); | |
750 | } | |
751 | ||
752 | return nfound; | |
753 | } | |
754 | ||
755 | /* Estimate size of the function after inlining WHAT into TO. */ | |
756 | ||
757 | static int | |
d9d9733a | 758 | cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to, |
d7c6d889 | 759 | struct cgraph_node *what) |
760 | { | |
761 | return (what->global.insns - INSNS_PER_CALL) *times + to->global.insns; | |
762 | } | |
763 | ||
764 | /* Estimate the growth caused by inlining NODE into all callees. */ | |
765 | ||
766 | static int | |
767 | cgraph_estimate_growth (struct cgraph_node *node) | |
768 | { | |
769 | int growth = 0; | |
770 | int calls_saved = 0; | |
771 | int clones_added = 0; | |
772 | struct cgraph_edge *e; | |
773 | ||
774 | for (e = node->callers; e; e = e->next_caller) | |
775 | if (!e->inline_call) | |
776 | { | |
777 | growth += ((cgraph_estimate_size_after_inlining (1, e->caller, node) | |
778 | - | |
779 | e->caller->global.insns) *e->caller->global.cloned_times); | |
780 | calls_saved += e->caller->global.cloned_times; | |
781 | clones_added += e->caller->global.cloned_times; | |
782 | } | |
783 | ||
784 | /* ??? Wrong for self recursive functions or cases where we decide to not | |
785 | inline for different reasons, but it is not big deal as in that case | |
786 | we will keep the body around, but we will also avoid some inlining. */ | |
787 | if (!node->needed && !node->origin && !DECL_EXTERNAL (node->decl)) | |
788 | growth -= node->global.insns, clones_added--; | |
789 | ||
790 | if (!calls_saved) | |
791 | calls_saved = 1; | |
792 | ||
793 | return growth; | |
794 | } | |
795 | ||
796 | /* Update insn sizes after inlining WHAT into TO that is already inlined into | |
797 | all nodes in INLINED array. */ | |
80a85d8a | 798 | |
799 | static void | |
d9d9733a | 800 | cgraph_mark_inline (struct cgraph_node *to, struct cgraph_node *what, |
d7c6d889 | 801 | struct cgraph_node **inlined, int ninlined, |
802 | struct cgraph_node **inlined_callees, | |
803 | int ninlined_callees) | |
804 | { | |
805 | int i; | |
806 | int times = 0; | |
807 | int clones = 0; | |
808 | struct cgraph_edge *e; | |
809 | bool called = false; | |
810 | int new_insns; | |
811 | ||
812 | for (e = what->callers; e; e = e->next_caller) | |
813 | { | |
814 | if (e->caller == to) | |
815 | { | |
816 | if (e->inline_call) | |
817 | abort (); | |
818 | e->inline_call = true; | |
819 | times++; | |
820 | clones += e->caller->global.cloned_times; | |
821 | } | |
822 | else if (!e->inline_call) | |
823 | called = true; | |
824 | } | |
825 | if (!times) | |
826 | abort (); | |
827 | ncalls_inlined += times; | |
828 | ||
829 | new_insns = cgraph_estimate_size_after_inlining (times, to, what); | |
830 | if (to->global.will_be_output) | |
831 | overall_insns += new_insns - to->global.insns; | |
832 | to->global.insns = new_insns; | |
833 | ||
d7c6d889 | 834 | if (!called && !what->needed && !what->origin |
835 | && !DECL_EXTERNAL (what->decl)) | |
836 | { | |
837 | if (!what->global.will_be_output) | |
838 | abort (); | |
839 | clones--; | |
840 | nfunctions_inlined++; | |
841 | what->global.will_be_output = 0; | |
842 | overall_insns -= what->global.insns; | |
843 | } | |
844 | what->global.cloned_times += clones; | |
d7c6d889 | 845 | for (i = 0; i < ninlined; i++) |
846 | { | |
847 | new_insns = | |
848 | cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) * | |
849 | times, inlined[i], what); | |
850 | if (inlined[i]->global.will_be_output) | |
851 | overall_insns += new_insns - inlined[i]->global.insns; | |
852 | inlined[i]->global.insns = new_insns; | |
d7c6d889 | 853 | } |
854 | for (i = 0; i < ninlined_callees; i++) | |
855 | { | |
856 | inlined_callees[i]->global.cloned_times += | |
857 | INLINED_TIMES (inlined_callees[i]) * clones; | |
858 | } | |
859 | } | |
860 | ||
861 | /* Return false when inlining WHAT into TO is not good idea as it would cause | |
862 | too large growth of function bodies. */ | |
863 | ||
864 | static bool | |
d9d9733a | 865 | cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what, |
d7c6d889 | 866 | struct cgraph_node **inlined, int ninlined) |
80a85d8a | 867 | { |
d7c6d889 | 868 | int i; |
869 | int times = 0; | |
870 | struct cgraph_edge *e; | |
871 | int newsize; | |
872 | int limit; | |
873 | ||
874 | for (e = to->callees; e; e = e->next_callee) | |
875 | if (e->callee == what) | |
876 | times++; | |
877 | ||
878 | /* When inlining large function body called once into small function, | |
879 | take the inlined function as base for limiting the growth. */ | |
880 | if (to->local.self_insns > what->local.self_insns) | |
881 | limit = to->local.self_insns; | |
882 | else | |
883 | limit = what->local.self_insns; | |
884 | ||
885 | limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100; | |
886 | ||
887 | newsize = cgraph_estimate_size_after_inlining (times, to, what); | |
888 | if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS) | |
889 | && newsize > limit) | |
890 | return false; | |
891 | for (i = 0; i < ninlined; i++) | |
892 | { | |
893 | newsize = | |
894 | cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) * | |
895 | times, inlined[i], what); | |
896 | if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS) | |
897 | && newsize > | |
898 | inlined[i]->local.self_insns * | |
899 | (100 + PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH)) / 100) | |
900 | return false; | |
901 | } | |
902 | return true; | |
903 | } | |
904 | ||
905 | /* Return true when function N is small enought to be inlined. */ | |
906 | ||
907 | static bool | |
908 | cgraph_default_inline_p (struct cgraph_node *n) | |
909 | { | |
910 | if (!DECL_INLINE (n->decl) || !DECL_SAVED_TREE (n->decl)) | |
911 | return false; | |
746149b7 | 912 | if (DECL_DECLARED_INLINE_P (n->decl)) |
d7c6d889 | 913 | return n->global.insns < MAX_INLINE_INSNS_SINGLE; |
746149b7 | 914 | else |
915 | return n->global.insns < MAX_INLINE_INSNS_AUTO; | |
d7c6d889 | 916 | } |
917 | ||
918 | /* We use greedy algorithm for inlining of small functions: | |
919 | All inline candidates are put into prioritized heap based on estimated | |
920 | growth of the overall number of instructions and then update the estimates. | |
d9d9733a | 921 | |
d7c6d889 | 922 | INLINED and INLINED_CALEES are just pointers to arrays large enought |
923 | to be passed to cgraph_inlined_into and cgraph_inlined_callees. */ | |
924 | ||
925 | static void | |
926 | cgraph_decide_inlining_of_small_functions (struct cgraph_node **inlined, | |
d9d9733a | 927 | struct cgraph_node **inlined_callees) |
d7c6d889 | 928 | { |
929 | int i; | |
80a85d8a | 930 | struct cgraph_node *node; |
d7c6d889 | 931 | fibheap_t heap = fibheap_new (); |
932 | struct fibnode **heap_node = | |
746149b7 | 933 | xcalloc (cgraph_max_uid, sizeof (struct fibnode *)); |
d7c6d889 | 934 | int ninlined, ninlined_callees; |
935 | int max_insns = ((HOST_WIDEST_INT) initial_insns | |
936 | * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100); | |
80a85d8a | 937 | |
d7c6d889 | 938 | /* Put all inline candidates into the heap. */ |
80a85d8a | 939 | |
80a85d8a | 940 | for (node = cgraph_nodes; node; node = node->next) |
941 | { | |
d7c6d889 | 942 | struct cgraph_edge *e; |
943 | ||
944 | if (!node->local.inlinable || !node->callers | |
945 | || !cgraph_default_inline_p (node)) | |
946 | continue; | |
947 | ||
91c82c20 | 948 | /* Rule out always_inline functions we dealt with earlier. */ |
d7c6d889 | 949 | for (e = node->callers; e; e = e->next_caller) |
950 | if (e->inline_call) | |
951 | break; | |
952 | if (e) | |
953 | continue; | |
954 | heap_node[node->uid] = | |
955 | fibheap_insert (heap, cgraph_estimate_growth (node), node); | |
80a85d8a | 956 | } |
d7c6d889 | 957 | |
f79b6507 | 958 | if (cgraph_dump_file) |
d7c6d889 | 959 | fprintf (cgraph_dump_file, "\n\nDeciding on inlining: "); |
960 | while ((node = fibheap_extract_min (heap)) && overall_insns <= max_insns) | |
961 | { | |
962 | struct cgraph_edge *e; | |
963 | int old_insns = overall_insns; | |
964 | ||
965 | heap_node[node->uid] = NULL; | |
966 | if (cgraph_dump_file) | |
967 | fprintf (cgraph_dump_file, "Considering %s %i insns, growth %i.\n", | |
968 | cgraph_node_name (node), node->global.insns, | |
969 | cgraph_estimate_growth (node)); | |
970 | if (!cgraph_default_inline_p (node)) | |
971 | { | |
972 | if (cgraph_dump_file) | |
973 | fprintf (cgraph_dump_file, "Function too large.\n"); | |
974 | continue; | |
975 | } | |
976 | ninlined_callees = cgraph_inlined_callees (node, inlined_callees); | |
977 | for (e = node->callers; e; e = e->next_caller) | |
978 | if (!e->inline_call && e->caller != node) | |
979 | { | |
980 | ninlined = cgraph_inlined_into (e->caller, inlined); | |
981 | if (e->callee->output | |
982 | || !cgraph_check_inline_limits (e->caller, node, inlined, | |
983 | ninlined)) | |
984 | { | |
985 | for (i = 0; i < ninlined; i++) | |
986 | inlined[i]->output = 0, node->aux = 0; | |
987 | if (cgraph_dump_file) | |
988 | fprintf (cgraph_dump_file, "Not inlining into %s\n", | |
989 | cgraph_node_name (e->caller)); | |
990 | continue; | |
991 | } | |
992 | cgraph_mark_inline (e->caller, node, inlined, ninlined, | |
993 | inlined_callees, ninlined_callees); | |
994 | if (heap_node[e->caller->uid]) | |
995 | fibheap_replace_key (heap, heap_node[e->caller->uid], | |
996 | cgraph_estimate_growth (e->caller)); | |
997 | ||
998 | /* Size of the functions we updated into has changed, so update | |
999 | the keys. */ | |
1000 | for (i = 0; i < ninlined; i++) | |
1001 | { | |
1002 | inlined[i]->output = 0, node->aux = 0; | |
1003 | if (heap_node[inlined[i]->uid]) | |
1004 | fibheap_replace_key (heap, heap_node[inlined[i]->uid], | |
1005 | cgraph_estimate_growth (inlined[i])); | |
1006 | } | |
1007 | } | |
1008 | ||
1009 | /* Similarly all functions called by function we just inlined | |
1010 | are now called more times; update keys. */ | |
1011 | ||
1012 | for (e = node->callees; e; e = e->next_callee) | |
1013 | if (!e->inline_call && heap_node[e->callee->uid]) | |
1014 | fibheap_replace_key (heap, heap_node[e->callee->uid], | |
1015 | cgraph_estimate_growth (e->callee)); | |
1016 | ||
1017 | for (i = 0; i < ninlined_callees; i++) | |
1018 | { | |
1019 | struct cgraph_edge *e; | |
1020 | ||
1021 | for (e = inlined_callees[i]->callees; e; e = e->next_callee) | |
1022 | if (!e->inline_call && heap_node[e->callee->uid]) | |
1023 | fibheap_replace_key (heap, heap_node[e->callee->uid], | |
1024 | cgraph_estimate_growth (e->callee)); | |
1025 | ||
1026 | inlined_callees[i]->output = 0, node->aux = 0; | |
1027 | } | |
1028 | if (cgraph_dump_file) | |
1029 | fprintf (cgraph_dump_file, | |
1030 | "Created %i clones, Num insns:%i (%+i), %.2f%%.\n\n", | |
1031 | node->global.cloned_times - 1, | |
1032 | overall_insns, overall_insns - old_insns, | |
1033 | overall_insns * 100.0 / initial_insns); | |
1034 | } | |
1035 | if (cgraph_dump_file && !fibheap_empty (heap)) | |
1036 | fprintf (cgraph_dump_file, "inline-unit-growth limit reached.\n"); | |
1037 | fibheap_delete (heap); | |
1038 | free (heap_node); | |
80a85d8a | 1039 | } |
1040 | ||
d7c6d889 | 1041 | /* Decide on the inlining. We do so in the topological order to avoid |
1042 | expenses on updating datastructures. */ | |
961e3b13 | 1043 | |
1044 | static void | |
d7c6d889 | 1045 | cgraph_decide_inlining (void) |
961e3b13 | 1046 | { |
d7c6d889 | 1047 | struct cgraph_node *node; |
1048 | int nnodes; | |
1049 | struct cgraph_node **order = | |
746149b7 | 1050 | xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); |
d7c6d889 | 1051 | struct cgraph_node **inlined = |
746149b7 | 1052 | xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); |
d7c6d889 | 1053 | struct cgraph_node **inlined_callees = |
746149b7 | 1054 | xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); |
d7c6d889 | 1055 | int ninlined; |
1056 | int ninlined_callees; | |
1057 | int i, y; | |
961e3b13 | 1058 | |
d7c6d889 | 1059 | for (node = cgraph_nodes; node; node = node->next) |
0785e435 | 1060 | initial_insns += node->local.self_insns; |
d7c6d889 | 1061 | overall_insns = initial_insns; |
1062 | ||
1063 | nnodes = cgraph_postorder (order); | |
961e3b13 | 1064 | |
961e3b13 | 1065 | for (node = cgraph_nodes; node; node = node->next) |
d7c6d889 | 1066 | node->aux = 0; |
1067 | ||
1068 | if (cgraph_dump_file) | |
1069 | fprintf (cgraph_dump_file, "\n\nDeciding on always_inline functions:\n"); | |
1070 | ||
1071 | /* In the first pass mark all always_inline edges. Do this with a priority | |
1072 | so no our decisions makes this impossible. */ | |
1073 | for (i = nnodes - 1; i >= 0; i--) | |
1074 | { | |
1075 | struct cgraph_edge *e; | |
1076 | ||
1077 | node = order[i]; | |
1078 | ||
1079 | for (e = node->callees; e; e = e->next_callee) | |
746149b7 | 1080 | if (e->callee->local.disregard_inline_limits) |
d7c6d889 | 1081 | break; |
1082 | if (!e) | |
1083 | continue; | |
1084 | if (cgraph_dump_file) | |
1085 | fprintf (cgraph_dump_file, | |
1086 | "Considering %s %i insns (always inline)\n", | |
1087 | cgraph_node_name (node), node->global.insns); | |
1088 | ninlined = cgraph_inlined_into (order[i], inlined); | |
1089 | for (; e; e = e->next_callee) | |
1090 | { | |
746149b7 | 1091 | if (e->inline_call || !e->callee->local.disregard_inline_limits) |
d7c6d889 | 1092 | continue; |
1093 | if (e->callee->output || e->callee == node) | |
1094 | continue; | |
1095 | ninlined_callees = | |
1096 | cgraph_inlined_callees (e->callee, inlined_callees); | |
1097 | cgraph_mark_inline (node, e->callee, inlined, ninlined, | |
1098 | inlined_callees, ninlined_callees); | |
1099 | for (y = 0; y < ninlined_callees; y++) | |
1100 | inlined_callees[y]->output = 0, node->aux = 0; | |
1101 | if (cgraph_dump_file) | |
1102 | fprintf (cgraph_dump_file, "Inlined %i times. Now %i insns\n\n", | |
1103 | node->global.cloned_times, overall_insns); | |
1104 | } | |
1105 | for (y = 0; y < ninlined; y++) | |
1106 | inlined[y]->output = 0, node->aux = 0; | |
1107 | } | |
1108 | ||
1109 | cgraph_decide_inlining_of_small_functions (inlined, inlined_callees); | |
1110 | ||
1111 | if (cgraph_dump_file) | |
1112 | fprintf (cgraph_dump_file, "\n\nFunctions to inline once:\n"); | |
1113 | ||
1114 | /* And finally decide what functions are called once. */ | |
1115 | ||
1116 | for (i = nnodes - 1; i >= 0; i--) | |
961e3b13 | 1117 | { |
d7c6d889 | 1118 | node = order[i]; |
1119 | ||
961e3b13 | 1120 | if (node->callers && !node->callers->next_caller && !node->needed |
d7c6d889 | 1121 | && node->local.inlinable && !node->callers->inline_call |
1122 | && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl)) | |
961e3b13 | 1123 | { |
1124 | bool ok = true; | |
d7c6d889 | 1125 | struct cgraph_node *node1; |
961e3b13 | 1126 | |
1127 | /* Verify that we won't duplicate the caller. */ | |
1128 | for (node1 = node->callers->caller; | |
d7c6d889 | 1129 | node1->callers && node1->callers->inline_call |
1130 | && ok; node1 = node1->callers->caller) | |
961e3b13 | 1131 | if (node1->callers->next_caller || node1->needed) |
1132 | ok = false; | |
1133 | if (ok) | |
1134 | { | |
f79b6507 | 1135 | if (cgraph_dump_file) |
d7c6d889 | 1136 | fprintf (cgraph_dump_file, |
1137 | "Considering %s %i insns (called once)\n", | |
1138 | cgraph_node_name (node), node->global.insns); | |
1139 | ninlined = cgraph_inlined_into (node->callers->caller, inlined); | |
1140 | if (cgraph_check_inline_limits | |
1141 | (node->callers->caller, node, inlined, ninlined)) | |
1142 | { | |
1143 | ninlined_callees = | |
1144 | cgraph_inlined_callees (node, inlined_callees); | |
1145 | cgraph_mark_inline (node->callers->caller, node, inlined, | |
1146 | ninlined, inlined_callees, | |
1147 | ninlined_callees); | |
1148 | for (y = 0; y < ninlined_callees; y++) | |
1149 | inlined_callees[y]->output = 0, node->aux = 0; | |
1150 | if (cgraph_dump_file) | |
1151 | fprintf (cgraph_dump_file, "Inlined. Now %i insns\n\n", overall_insns); | |
1152 | } | |
1153 | for (y = 0; y < ninlined; y++) | |
1154 | inlined[y]->output = 0, node->aux = 0; | |
961e3b13 | 1155 | } |
1156 | } | |
1157 | } | |
d7c6d889 | 1158 | |
f79b6507 | 1159 | if (cgraph_dump_file) |
d7c6d889 | 1160 | fprintf (cgraph_dump_file, |
1161 | "\nInlined %i calls, elliminated %i functions, %i insns turned to %i insns.\n", | |
1162 | ncalls_inlined, nfunctions_inlined, initial_insns, | |
1163 | overall_insns); | |
1164 | free (order); | |
1165 | free (inlined); | |
1166 | free (inlined_callees); | |
961e3b13 | 1167 | } |
1168 | ||
d7c6d889 | 1169 | /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */ |
1170 | ||
1171 | bool | |
1172 | cgraph_inline_p (tree caller_decl, tree callee_decl) | |
1173 | { | |
1174 | struct cgraph_node *caller = cgraph_node (caller_decl); | |
1175 | struct cgraph_node *callee = cgraph_node (callee_decl); | |
1176 | struct cgraph_edge *e; | |
1177 | ||
1178 | for (e = caller->callees; e; e = e->next_callee) | |
1179 | if (e->callee == callee) | |
1180 | return e->inline_call; | |
1181 | /* We do not record builtins in the callgraph. Perhaps it would make more | |
91c82c20 | 1182 | sense to do so and then prune out those not overwritten by explicit |
d7c6d889 | 1183 | function body. */ |
1184 | return false; | |
1185 | } | |
d9d9733a | 1186 | /* Expand all functions that must be output. |
1187 | ||
d7c6d889 | 1188 | Attempt to topologically sort the nodes so function is output when |
1189 | all called functions are already assembled to allow data to be | |
91c82c20 | 1190 | propagated across the callgraph. Use a stack to get smaller distance |
d7c6d889 | 1191 | between a function and it's callees (later we may choose to use a more |
1192 | sophisticated algorithm for function reordering; we will likely want | |
1193 | to use subsections to make the output functions appear in top-down | |
1194 | order). */ | |
1195 | ||
1196 | static void | |
d9d9733a | 1197 | cgraph_expand_functions (void) |
d7c6d889 | 1198 | { |
1199 | struct cgraph_node *node; | |
1200 | struct cgraph_node **order = | |
746149b7 | 1201 | xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); |
d7c6d889 | 1202 | int order_pos = 0; |
1203 | int i; | |
1204 | ||
1205 | cgraph_mark_functions_to_output (); | |
1206 | ||
1207 | order_pos = cgraph_postorder (order); | |
1208 | ||
1209 | for (i = order_pos - 1; i >= 0; i--) | |
1210 | { | |
1211 | node = order[i]; | |
1212 | if (node->output) | |
1213 | { | |
1214 | if (!node->reachable) | |
1215 | abort (); | |
1216 | node->output = 0; | |
1217 | cgraph_expand_function (node); | |
1218 | } | |
1219 | } | |
1220 | free (order); | |
1221 | } | |
1222 | ||
1223 | /* Mark all local functions. | |
1224 | ||
91c82c20 | 1225 | A local function is one whose calls can occur only in the |
1226 | current compilation unit, so we change its calling convention. | |
d7c6d889 | 1227 | We simply mark all static functions whose address is not taken |
1228 | as local. */ | |
1229 | ||
1230 | static void | |
d9d9733a | 1231 | cgraph_mark_local_functions (void) |
d7c6d889 | 1232 | { |
1233 | struct cgraph_node *node; | |
1234 | ||
1235 | if (cgraph_dump_file) | |
1236 | fprintf (cgraph_dump_file, "Marking local functions:"); | |
1237 | ||
1238 | /* Figure out functions we want to assemble. */ | |
1239 | for (node = cgraph_nodes; node; node = node->next) | |
1240 | { | |
1241 | node->local.local = (!node->needed | |
1242 | && DECL_SAVED_TREE (node->decl) | |
1243 | && !TREE_PUBLIC (node->decl)); | |
1244 | if (cgraph_dump_file && node->local.local) | |
1245 | fprintf (cgraph_dump_file, " %s", cgraph_node_name (node)); | |
1246 | } | |
1247 | if (cgraph_dump_file) | |
1248 | fprintf (cgraph_dump_file, "\n"); | |
1249 | } | |
80a85d8a | 1250 | |
ae01b312 | 1251 | /* Perform simple optimizations based on callgraph. */ |
1252 | ||
1253 | void | |
d9d9733a | 1254 | cgraph_optimize (void) |
ae01b312 | 1255 | { |
2ff66ee0 | 1256 | if (!flag_unit_at_a_time) |
1257 | return; | |
f79b6507 | 1258 | timevar_push (TV_CGRAPHOPT); |
d7c6d889 | 1259 | if (!quiet_flag) |
1260 | fprintf (stderr, "Performing intraprocedural optimizations\n"); | |
f79b6507 | 1261 | if (cgraph_dump_file) |
1262 | { | |
1263 | fprintf (cgraph_dump_file, "Initial callgraph:"); | |
1264 | dump_cgraph (cgraph_dump_file); | |
1265 | } | |
80a85d8a | 1266 | cgraph_mark_local_functions (); |
1267 | ||
d7c6d889 | 1268 | cgraph_decide_inlining (); |
961e3b13 | 1269 | |
80a85d8a | 1270 | cgraph_global_info_ready = true; |
f79b6507 | 1271 | if (cgraph_dump_file) |
1272 | { | |
1273 | fprintf (cgraph_dump_file, "Optimized callgraph:"); | |
1274 | dump_cgraph (cgraph_dump_file); | |
1275 | } | |
1276 | timevar_pop (TV_CGRAPHOPT); | |
ae01b312 | 1277 | if (!quiet_flag) |
d7c6d889 | 1278 | fprintf (stderr, "Assembling functions:"); |
ae01b312 | 1279 | |
d7c6d889 | 1280 | /* Output everything. */ |
ae01b312 | 1281 | cgraph_expand_functions (); |
f79b6507 | 1282 | if (cgraph_dump_file) |
1283 | { | |
1284 | fprintf (cgraph_dump_file, "Final callgraph:"); | |
1285 | dump_cgraph (cgraph_dump_file); | |
1286 | } | |
ae01b312 | 1287 | } |