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