]>
Commit | Line | Data |
---|---|---|
ca31b95f JH |
1 | /* Inlining decision heuristics. |
2 | Copyright (C) 2003, 2004 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 | |
366ccddb KC |
19 | Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA |
20 | 02110-1301, USA. */ | |
ca31b95f JH |
21 | |
22 | /* Inlining decision heuristics | |
23 | ||
24 | We separate inlining decisions from the inliner itself and store it | |
25 | inside callgraph as so called inline plan. Refer to cgraph.c | |
26 | documentation about particular representation of inline plans in the | |
27 | callgraph. | |
28 | ||
29 | There are three major parts of this file: | |
30 | ||
31 | cgraph_mark_inline implementation | |
32 | ||
a80769d7 | 33 | This function allows to mark given call inline and performs necessary |
ca31b95f JH |
34 | modifications of cgraph (production of the clones and updating overall |
35 | statistics) | |
36 | ||
37 | inlining heuristics limits | |
38 | ||
39 | These functions allow to check that particular inlining is allowed | |
40 | by the limits specified by user (allowed function growth, overall unit | |
41 | growth and so on). | |
42 | ||
43 | inlining heuristics | |
44 | ||
45 | This is implementation of IPA pass aiming to get as much of benefit | |
46 | from inlining obeying the limits checked above. | |
47 | ||
48 | The implementation of particular heuristics is separated from | |
49 | the rest of code to make it easier to replace it with more complicated | |
50 | implementation in the future. The rest of inlining code acts as a | |
51 | library aimed to modify the callgraph and verify that the parameters | |
52 | on code size growth fits. | |
53 | ||
54 | To mark given call inline, use cgraph_mark_inline function, the | |
55 | verification is performed by cgraph_default_inline_p and | |
56 | cgraph_check_inline_limits. | |
57 | ||
58 | The heuristics implements simple knapsack style algorithm ordering | |
59 | all functions by their "profitability" (estimated by code size growth) | |
60 | and inlining them in priority order. | |
61 | ||
62 | cgraph_decide_inlining implements heuristics taking whole callgraph | |
63 | into account, while cgraph_decide_inlining_incrementally considers | |
64 | only one function at a time and is used in non-unit-at-a-time mode. */ | |
65 | ||
66 | #include "config.h" | |
67 | #include "system.h" | |
68 | #include "coretypes.h" | |
69 | #include "tm.h" | |
70 | #include "tree.h" | |
71 | #include "tree-inline.h" | |
72 | #include "langhooks.h" | |
73 | #include "flags.h" | |
74 | #include "cgraph.h" | |
75 | #include "diagnostic.h" | |
76 | #include "timevar.h" | |
77 | #include "params.h" | |
78 | #include "fibheap.h" | |
79 | #include "intl.h" | |
80 | #include "tree-pass.h" | |
0691d1d4 | 81 | #include "hashtab.h" |
670cd5c5 | 82 | #include "coverage.h" |
d63db217 | 83 | #include "ggc.h" |
ca31b95f JH |
84 | |
85 | /* Statistics we collect about inlining algorithm. */ | |
86 | static int ncalls_inlined; | |
87 | static int nfunctions_inlined; | |
88 | static int initial_insns; | |
89 | static int overall_insns; | |
670cd5c5 JH |
90 | static int max_insns; |
91 | static gcov_type max_count; | |
ca31b95f JH |
92 | |
93 | /* Estimate size of the function after inlining WHAT into TO. */ | |
94 | ||
95 | static int | |
96 | cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to, | |
97 | struct cgraph_node *what) | |
98 | { | |
670cd5c5 JH |
99 | int size; |
100 | tree fndecl = what->decl, arg; | |
ca31b95f | 101 | int call_insns = PARAM_VALUE (PARAM_INLINE_CALL_COST); |
670cd5c5 | 102 | |
ca31b95f JH |
103 | for (arg = DECL_ARGUMENTS (fndecl); arg; arg = TREE_CHAIN (arg)) |
104 | call_insns += estimate_move_cost (TREE_TYPE (arg)); | |
670cd5c5 JH |
105 | size = (what->global.insns - call_insns) * times + to->global.insns; |
106 | gcc_assert (size >= 0); | |
107 | return size; | |
ca31b95f JH |
108 | } |
109 | ||
110 | /* E is expected to be an edge being inlined. Clone destination node of | |
111 | the edge and redirect it to the new clone. | |
112 | DUPLICATE is used for bookkeeping on whether we are actually creating new | |
113 | clones or re-using node originally representing out-of-line function call. | |
114 | */ | |
115 | void | |
06191a23 | 116 | cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate, bool update_original) |
ca31b95f JH |
117 | { |
118 | struct cgraph_node *n; | |
119 | ||
120 | /* We may eliminate the need for out-of-line copy to be output. In that | |
121 | case just go ahead and re-use it. */ | |
122 | if (!e->callee->callers->next_caller | |
123 | && (!e->callee->needed || DECL_EXTERNAL (e->callee->decl)) | |
124 | && duplicate | |
9f2583c7 | 125 | && flag_unit_at_a_time) |
ca31b95f JH |
126 | { |
127 | gcc_assert (!e->callee->global.inlined_to); | |
128 | if (!DECL_EXTERNAL (e->callee->decl)) | |
129 | overall_insns -= e->callee->global.insns, nfunctions_inlined++; | |
130 | duplicate = 0; | |
131 | } | |
132 | else if (duplicate) | |
133 | { | |
06191a23 | 134 | n = cgraph_clone_node (e->callee, e->count, e->loop_nest, update_original); |
ca31b95f JH |
135 | cgraph_redirect_edge_callee (e, n); |
136 | } | |
137 | ||
138 | if (e->caller->global.inlined_to) | |
139 | e->callee->global.inlined_to = e->caller->global.inlined_to; | |
140 | else | |
141 | e->callee->global.inlined_to = e->caller; | |
142 | ||
143 | /* Recursively clone all bodies. */ | |
144 | for (e = e->callee->callees; e; e = e->next_callee) | |
145 | if (!e->inline_failed) | |
06191a23 | 146 | cgraph_clone_inlined_nodes (e, duplicate, update_original); |
ca31b95f JH |
147 | } |
148 | ||
06191a23 JH |
149 | /* Mark edge E as inlined and update callgraph accordingly. |
150 | UPDATE_ORIGINAL specify whether profile of original function should be | |
151 | updated. */ | |
ca31b95f JH |
152 | |
153 | void | |
06191a23 | 154 | cgraph_mark_inline_edge (struct cgraph_edge *e, bool update_original) |
ca31b95f JH |
155 | { |
156 | int old_insns = 0, new_insns = 0; | |
157 | struct cgraph_node *to = NULL, *what; | |
158 | ||
159 | gcc_assert (e->inline_failed); | |
160 | e->inline_failed = NULL; | |
161 | ||
162 | if (!e->callee->global.inlined && flag_unit_at_a_time) | |
163 | DECL_POSSIBLY_INLINED (e->callee->decl) = true; | |
164 | e->callee->global.inlined = true; | |
165 | ||
06191a23 | 166 | cgraph_clone_inlined_nodes (e, true, update_original); |
ca31b95f JH |
167 | |
168 | what = e->callee; | |
169 | ||
170 | /* Now update size of caller and all functions caller is inlined into. */ | |
171 | for (;e && !e->inline_failed; e = e->caller->callers) | |
172 | { | |
173 | old_insns = e->caller->global.insns; | |
174 | new_insns = cgraph_estimate_size_after_inlining (1, e->caller, | |
175 | what); | |
176 | gcc_assert (new_insns >= 0); | |
177 | to = e->caller; | |
178 | to->global.insns = new_insns; | |
179 | } | |
180 | gcc_assert (what->global.inlined_to == to); | |
181 | if (new_insns > old_insns) | |
182 | overall_insns += new_insns - old_insns; | |
183 | ncalls_inlined++; | |
184 | } | |
185 | ||
186 | /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER. | |
187 | Return following unredirected edge in the list of callers | |
188 | of EDGE->CALLEE */ | |
189 | ||
190 | static struct cgraph_edge * | |
191 | cgraph_mark_inline (struct cgraph_edge *edge) | |
192 | { | |
193 | struct cgraph_node *to = edge->caller; | |
194 | struct cgraph_node *what = edge->callee; | |
195 | struct cgraph_edge *e, *next; | |
196 | int times = 0; | |
197 | ||
198 | /* Look for all calls, mark them inline and clone recursively | |
199 | all inlined functions. */ | |
200 | for (e = what->callers; e; e = next) | |
201 | { | |
202 | next = e->next_caller; | |
203 | if (e->caller == to && e->inline_failed) | |
204 | { | |
06191a23 | 205 | cgraph_mark_inline_edge (e, true); |
ca31b95f JH |
206 | if (e == edge) |
207 | edge = next; | |
208 | times++; | |
209 | } | |
210 | } | |
211 | gcc_assert (times); | |
212 | return edge; | |
213 | } | |
214 | ||
215 | /* Estimate the growth caused by inlining NODE into all callees. */ | |
216 | ||
217 | static int | |
218 | cgraph_estimate_growth (struct cgraph_node *node) | |
219 | { | |
220 | int growth = 0; | |
221 | struct cgraph_edge *e; | |
670cd5c5 JH |
222 | if (node->global.estimated_growth != INT_MIN) |
223 | return node->global.estimated_growth; | |
ca31b95f JH |
224 | |
225 | for (e = node->callers; e; e = e->next_caller) | |
226 | if (e->inline_failed) | |
227 | growth += (cgraph_estimate_size_after_inlining (1, e->caller, node) | |
228 | - e->caller->global.insns); | |
229 | ||
230 | /* ??? Wrong for self recursive functions or cases where we decide to not | |
231 | inline for different reasons, but it is not big deal as in that case | |
232 | we will keep the body around, but we will also avoid some inlining. */ | |
233 | if (!node->needed && !DECL_EXTERNAL (node->decl)) | |
234 | growth -= node->global.insns; | |
235 | ||
670cd5c5 | 236 | node->global.estimated_growth = growth; |
ca31b95f JH |
237 | return growth; |
238 | } | |
239 | ||
240 | /* Return false when inlining WHAT into TO is not good idea | |
241 | as it would cause too large growth of function bodies. */ | |
242 | ||
243 | static bool | |
244 | cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what, | |
245 | const char **reason) | |
246 | { | |
247 | int times = 0; | |
248 | struct cgraph_edge *e; | |
249 | int newsize; | |
250 | int limit; | |
251 | ||
252 | if (to->global.inlined_to) | |
253 | to = to->global.inlined_to; | |
254 | ||
255 | for (e = to->callees; e; e = e->next_callee) | |
256 | if (e->callee == what) | |
257 | times++; | |
258 | ||
259 | /* When inlining large function body called once into small function, | |
260 | take the inlined function as base for limiting the growth. */ | |
261 | if (to->local.self_insns > what->local.self_insns) | |
262 | limit = to->local.self_insns; | |
263 | else | |
264 | limit = what->local.self_insns; | |
265 | ||
266 | limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100; | |
267 | ||
268 | newsize = cgraph_estimate_size_after_inlining (times, to, what); | |
269 | if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS) | |
270 | && newsize > limit) | |
271 | { | |
272 | if (reason) | |
273 | *reason = N_("--param large-function-growth limit reached"); | |
274 | return false; | |
275 | } | |
276 | return true; | |
277 | } | |
278 | ||
279 | /* Return true when function N is small enough to be inlined. */ | |
280 | ||
281 | bool | |
9de21a23 | 282 | cgraph_default_inline_p (struct cgraph_node *n, const char **reason) |
ca31b95f | 283 | { |
9de21a23 JC |
284 | if (!DECL_INLINE (n->decl)) |
285 | { | |
286 | if (reason) | |
287 | *reason = N_("function not inlinable"); | |
288 | return false; | |
289 | } | |
290 | ||
291 | if (!DECL_SAVED_TREE (n->decl)) | |
292 | { | |
293 | if (reason) | |
294 | *reason = N_("function body not available"); | |
295 | return false; | |
296 | } | |
297 | ||
ca31b95f | 298 | if (DECL_DECLARED_INLINE_P (n->decl)) |
9de21a23 JC |
299 | { |
300 | if (n->global.insns >= MAX_INLINE_INSNS_SINGLE) | |
301 | { | |
302 | if (reason) | |
303 | *reason = N_("--param max-inline-insns-single limit reached"); | |
304 | return false; | |
305 | } | |
306 | } | |
ca31b95f | 307 | else |
9de21a23 JC |
308 | { |
309 | if (n->global.insns >= MAX_INLINE_INSNS_AUTO) | |
310 | { | |
311 | if (reason) | |
312 | *reason = N_("--param max-inline-insns-auto limit reached"); | |
313 | return false; | |
314 | } | |
315 | } | |
316 | ||
317 | return true; | |
ca31b95f JH |
318 | } |
319 | ||
320 | /* Return true when inlining WHAT would create recursive inlining. | |
321 | We call recursive inlining all cases where same function appears more than | |
322 | once in the single recursion nest path in the inline graph. */ | |
323 | ||
324 | static bool | |
325 | cgraph_recursive_inlining_p (struct cgraph_node *to, | |
326 | struct cgraph_node *what, | |
327 | const char **reason) | |
328 | { | |
329 | bool recursive; | |
330 | if (to->global.inlined_to) | |
331 | recursive = what->decl == to->global.inlined_to->decl; | |
332 | else | |
333 | recursive = what->decl == to->decl; | |
334 | /* Marking recursive function inline has sane semantic and thus we should | |
335 | not warn on it. */ | |
336 | if (recursive && reason) | |
337 | *reason = (what->local.disregard_inline_limits | |
338 | ? N_("recursive inlining") : ""); | |
339 | return recursive; | |
340 | } | |
341 | ||
670cd5c5 JH |
342 | /* Return true if the call can be hot. */ |
343 | static bool | |
344 | cgraph_maybe_hot_edge_p (struct cgraph_edge *edge) | |
345 | { | |
346 | if (profile_info && flag_branch_probabilities | |
347 | && (edge->count | |
348 | <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION))) | |
349 | return false; | |
350 | return true; | |
351 | } | |
352 | ||
353 | /* A cost model driving the inlining heuristics in a way so the edges with | |
354 | smallest badness are inlined first. After each inlining is performed | |
0fa2e4df | 355 | the costs of all caller edges of nodes affected are recomputed so the |
670cd5c5 JH |
356 | metrics may accurately depend on values such as number of inlinable callers |
357 | of the function or function body size. | |
358 | ||
670cd5c5 JH |
359 | With profiling we use number of executions of each edge to drive the cost. |
360 | We also should distinguish hot and cold calls where the cold calls are | |
361 | inlined into only when code size is overall improved. | |
670cd5c5 JH |
362 | */ |
363 | ||
364 | static int | |
365 | cgraph_edge_badness (struct cgraph_edge *edge) | |
366 | { | |
367 | if (max_count) | |
368 | { | |
369 | int growth = | |
370 | cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee); | |
371 | growth -= edge->caller->global.insns; | |
372 | ||
0fa2e4df | 373 | /* Always prefer inlining saving code size. */ |
670cd5c5 JH |
374 | if (growth <= 0) |
375 | return INT_MIN - growth; | |
376 | return ((int)((double)edge->count * INT_MIN / max_count)) / growth; | |
377 | } | |
378 | else | |
379 | { | |
380 | int nest = MIN (edge->loop_nest, 8); | |
381 | int badness = cgraph_estimate_growth (edge->callee) * 256; | |
9de21a23 JC |
382 | |
383 | /* Decrease badness if call is nested. */ | |
384 | if (badness > 0) | |
385 | badness >>= nest; | |
386 | else | |
387 | badness <<= nest; | |
670cd5c5 JH |
388 | |
389 | /* Make recursive inlining happen always after other inlining is done. */ | |
390 | if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL)) | |
391 | return badness + 1; | |
392 | else | |
393 | return badness; | |
394 | } | |
395 | } | |
396 | ||
397 | /* Recompute heap nodes for each of caller edge. */ | |
398 | ||
399 | static void | |
400 | update_caller_keys (fibheap_t heap, struct cgraph_node *node, | |
401 | bitmap updated_nodes) | |
402 | { | |
403 | struct cgraph_edge *edge; | |
404 | ||
405 | if (!node->local.inlinable || node->local.disregard_inline_limits | |
406 | || node->global.inlined_to) | |
407 | return; | |
408 | if (bitmap_bit_p (updated_nodes, node->uid)) | |
409 | return; | |
410 | bitmap_set_bit (updated_nodes, node->uid); | |
facc20ee | 411 | node->global.estimated_growth = INT_MIN; |
670cd5c5 JH |
412 | |
413 | for (edge = node->callers; edge; edge = edge->next_caller) | |
414 | if (edge->inline_failed) | |
415 | { | |
416 | int badness = cgraph_edge_badness (edge); | |
417 | if (edge->aux) | |
418 | { | |
419 | fibnode_t n = edge->aux; | |
420 | gcc_assert (n->data == edge); | |
421 | if (n->key == badness) | |
422 | continue; | |
423 | ||
424 | /* fibheap_replace_key only increase the keys. */ | |
425 | if (fibheap_replace_key (heap, n, badness)) | |
426 | continue; | |
427 | fibheap_delete_node (heap, edge->aux); | |
428 | } | |
429 | edge->aux = fibheap_insert (heap, badness, edge); | |
430 | } | |
431 | } | |
432 | ||
433 | /* Recompute heap nodes for each of caller edges of each of callees. */ | |
434 | ||
ca31b95f | 435 | static void |
670cd5c5 JH |
436 | update_callee_keys (fibheap_t heap, struct cgraph_node *node, |
437 | bitmap updated_nodes) | |
ca31b95f JH |
438 | { |
439 | struct cgraph_edge *e; | |
670cd5c5 | 440 | node->global.estimated_growth = INT_MIN; |
ca31b95f JH |
441 | |
442 | for (e = node->callees; e; e = e->next_callee) | |
670cd5c5 JH |
443 | if (e->inline_failed) |
444 | update_caller_keys (heap, e->callee, updated_nodes); | |
ca31b95f | 445 | else if (!e->inline_failed) |
670cd5c5 | 446 | update_callee_keys (heap, e->callee, updated_nodes); |
ca31b95f JH |
447 | } |
448 | ||
670cd5c5 | 449 | /* Enqueue all recursive calls from NODE into priority queue depending on |
0fa2e4df | 450 | how likely we want to recursively inline the call. */ |
670cd5c5 | 451 | |
ca31b95f JH |
452 | static void |
453 | lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where, | |
670cd5c5 | 454 | fibheap_t heap) |
ca31b95f | 455 | { |
670cd5c5 | 456 | static int priority; |
ca31b95f JH |
457 | struct cgraph_edge *e; |
458 | for (e = where->callees; e; e = e->next_callee) | |
459 | if (e->callee == node) | |
460 | { | |
c5a4444c JH |
461 | /* When profile feedback is available, prioritize by expected number |
462 | of calls. Without profile feedback we maintain simple queue | |
463 | to order candidates via recursive depths. */ | |
464 | fibheap_insert (heap, | |
465 | !max_count ? priority++ | |
466 | : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))), | |
467 | e); | |
ca31b95f JH |
468 | } |
469 | for (e = where->callees; e; e = e->next_callee) | |
470 | if (!e->inline_failed) | |
670cd5c5 | 471 | lookup_recursive_calls (node, e->callee, heap); |
ca31b95f JH |
472 | } |
473 | ||
0691d1d4 RG |
474 | /* Find callgraph nodes closing a circle in the graph. The |
475 | resulting hashtab can be used to avoid walking the circles. | |
476 | Uses the cgraph nodes ->aux field which needs to be zero | |
477 | before and will be zero after operation. */ | |
478 | ||
479 | static void | |
480 | cgraph_find_cycles (struct cgraph_node *node, htab_t cycles) | |
481 | { | |
482 | struct cgraph_edge *e; | |
483 | ||
484 | if (node->aux) | |
485 | { | |
486 | void **slot; | |
487 | slot = htab_find_slot (cycles, node, INSERT); | |
488 | if (!*slot) | |
489 | { | |
490 | if (dump_file) | |
491 | fprintf (dump_file, "Cycle contains %s\n", cgraph_node_name (node)); | |
492 | *slot = node; | |
493 | } | |
494 | return; | |
495 | } | |
496 | ||
497 | node->aux = node; | |
498 | for (e = node->callees; e; e = e->next_callee) | |
499 | cgraph_find_cycles (e->callee, cycles); | |
500 | node->aux = 0; | |
501 | } | |
502 | ||
503 | /* Leafify the cgraph node. We have to be careful in recursing | |
504 | as to not run endlessly in circles of the callgraph. | |
505 | We do so by using a hashtab of cycle entering nodes as generated | |
506 | by cgraph_find_cycles. */ | |
507 | ||
508 | static void | |
509 | cgraph_flatten_node (struct cgraph_node *node, htab_t cycles) | |
510 | { | |
511 | struct cgraph_edge *e; | |
512 | ||
513 | for (e = node->callees; e; e = e->next_callee) | |
514 | { | |
515 | /* Inline call, if possible, and recurse. Be sure we are not | |
516 | entering callgraph circles here. */ | |
517 | if (e->inline_failed | |
518 | && e->callee->local.inlinable | |
519 | && !cgraph_recursive_inlining_p (node, e->callee, | |
520 | &e->inline_failed) | |
521 | && !htab_find (cycles, e->callee)) | |
522 | { | |
523 | if (dump_file) | |
524 | fprintf (dump_file, " inlining %s", cgraph_node_name (e->callee)); | |
06191a23 | 525 | cgraph_mark_inline_edge (e, true); |
0691d1d4 RG |
526 | cgraph_flatten_node (e->callee, cycles); |
527 | } | |
528 | else if (dump_file) | |
529 | fprintf (dump_file, " !inlining %s", cgraph_node_name (e->callee)); | |
530 | } | |
531 | } | |
532 | ||
ca31b95f JH |
533 | /* Decide on recursive inlining: in the case function has recursive calls, |
534 | inline until body size reaches given argument. */ | |
670cd5c5 JH |
535 | |
536 | static bool | |
ca31b95f JH |
537 | cgraph_decide_recursive_inlining (struct cgraph_node *node) |
538 | { | |
539 | int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO); | |
540 | int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO); | |
c5a4444c | 541 | int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY); |
670cd5c5 | 542 | fibheap_t heap; |
ca31b95f JH |
543 | struct cgraph_edge *e; |
544 | struct cgraph_node *master_clone; | |
545 | int depth = 0; | |
546 | int n = 0; | |
547 | ||
548 | if (DECL_DECLARED_INLINE_P (node->decl)) | |
549 | { | |
550 | limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE); | |
551 | max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH); | |
552 | } | |
553 | ||
554 | /* Make sure that function is small enough to be considered for inlining. */ | |
555 | if (!max_depth | |
556 | || cgraph_estimate_size_after_inlining (1, node, node) >= limit) | |
670cd5c5 JH |
557 | return false; |
558 | heap = fibheap_new (); | |
559 | lookup_recursive_calls (node, node, heap); | |
560 | if (fibheap_empty (heap)) | |
561 | { | |
562 | fibheap_delete (heap); | |
563 | return false; | |
564 | } | |
ca31b95f JH |
565 | |
566 | if (dump_file) | |
567 | fprintf (dump_file, | |
670cd5c5 | 568 | " Performing recursive inlining on %s\n", |
ca31b95f JH |
569 | cgraph_node_name (node)); |
570 | ||
571 | /* We need original clone to copy around. */ | |
c5a4444c | 572 | master_clone = cgraph_clone_node (node, node->count, 1, false); |
ca31b95f JH |
573 | master_clone->needed = true; |
574 | for (e = master_clone->callees; e; e = e->next_callee) | |
575 | if (!e->inline_failed) | |
06191a23 | 576 | cgraph_clone_inlined_nodes (e, true, false); |
ca31b95f JH |
577 | |
578 | /* Do the inlining and update list of recursive call during process. */ | |
670cd5c5 | 579 | while (!fibheap_empty (heap) |
c5a4444c JH |
580 | && (cgraph_estimate_size_after_inlining (1, node, master_clone) |
581 | <= limit)) | |
ca31b95f | 582 | { |
670cd5c5 | 583 | struct cgraph_edge *curr = fibheap_extract_min (heap); |
c5a4444c | 584 | struct cgraph_node *cnode; |
670cd5c5 | 585 | |
c5a4444c JH |
586 | depth = 1; |
587 | for (cnode = curr->caller; | |
588 | cnode->global.inlined_to; cnode = cnode->callers->caller) | |
670cd5c5 JH |
589 | if (node->decl == curr->callee->decl) |
590 | depth++; | |
591 | if (depth > max_depth) | |
c5a4444c JH |
592 | { |
593 | if (dump_file) | |
594 | fprintf (dump_file, | |
595 | " maxmal depth reached\n"); | |
596 | continue; | |
597 | } | |
598 | ||
599 | if (max_count) | |
600 | { | |
601 | if (!cgraph_maybe_hot_edge_p (curr)) | |
602 | { | |
603 | if (dump_file) | |
604 | fprintf (dump_file, " Not inlining cold call\n"); | |
605 | continue; | |
606 | } | |
607 | if (curr->count * 100 / node->count < probability) | |
608 | { | |
609 | if (dump_file) | |
610 | fprintf (dump_file, | |
611 | " Probability of edge is too small\n"); | |
612 | continue; | |
613 | } | |
614 | } | |
ca31b95f | 615 | |
670cd5c5 | 616 | if (dump_file) |
c5a4444c JH |
617 | { |
618 | fprintf (dump_file, | |
619 | " Inlining call of depth %i", depth); | |
620 | if (node->count) | |
621 | { | |
622 | fprintf (dump_file, " called approx. %.2f times per call", | |
623 | (double)curr->count / node->count); | |
624 | } | |
625 | fprintf (dump_file, "\n"); | |
626 | } | |
ca31b95f | 627 | cgraph_redirect_edge_callee (curr, master_clone); |
06191a23 | 628 | cgraph_mark_inline_edge (curr, false); |
670cd5c5 | 629 | lookup_recursive_calls (node, curr->callee, heap); |
ca31b95f JH |
630 | n++; |
631 | } | |
c5a4444c JH |
632 | if (!fibheap_empty (heap) && dump_file) |
633 | fprintf (dump_file, " Recursive inlining growth limit met.\n"); | |
ca31b95f | 634 | |
670cd5c5 | 635 | fibheap_delete (heap); |
ca31b95f JH |
636 | if (dump_file) |
637 | fprintf (dump_file, | |
638 | "\n Inlined %i times, body grown from %i to %i insns\n", n, | |
639 | master_clone->global.insns, node->global.insns); | |
640 | ||
641 | /* Remove master clone we used for inlining. We rely that clones inlined | |
642 | into master clone gets queued just before master clone so we don't | |
643 | need recursion. */ | |
644 | for (node = cgraph_nodes; node != master_clone; | |
645 | node = node->next) | |
646 | if (node->global.inlined_to == master_clone) | |
647 | cgraph_remove_node (node); | |
648 | cgraph_remove_node (master_clone); | |
c5a4444c JH |
649 | /* FIXME: Recursive inlining actually reduces number of calls of the |
650 | function. At this place we should probably walk the function and | |
651 | inline clones and compensate the counts accordingly. This probably | |
652 | doesn't matter much in practice. */ | |
7e1b44bb | 653 | return n > 0; |
ca31b95f JH |
654 | } |
655 | ||
656 | /* Set inline_failed for all callers of given function to REASON. */ | |
657 | ||
658 | static void | |
659 | cgraph_set_inline_failed (struct cgraph_node *node, const char *reason) | |
660 | { | |
661 | struct cgraph_edge *e; | |
662 | ||
663 | if (dump_file) | |
664 | fprintf (dump_file, "Inlining failed: %s\n", reason); | |
665 | for (e = node->callers; e; e = e->next_caller) | |
666 | if (e->inline_failed) | |
667 | e->inline_failed = reason; | |
668 | } | |
669 | ||
670 | /* We use greedy algorithm for inlining of small functions: | |
671 | All inline candidates are put into prioritized heap based on estimated | |
672 | growth of the overall number of instructions and then update the estimates. | |
673 | ||
674 | INLINED and INLINED_CALEES are just pointers to arrays large enough | |
675 | to be passed to cgraph_inlined_into and cgraph_inlined_callees. */ | |
676 | ||
677 | static void | |
678 | cgraph_decide_inlining_of_small_functions (void) | |
679 | { | |
680 | struct cgraph_node *node; | |
670cd5c5 | 681 | struct cgraph_edge *edge; |
9de21a23 | 682 | const char *failed_reason; |
ca31b95f | 683 | fibheap_t heap = fibheap_new (); |
670cd5c5 JH |
684 | bitmap updated_nodes = BITMAP_ALLOC (NULL); |
685 | ||
686 | if (dump_file) | |
687 | fprintf (dump_file, "\nDeciding on smaller functions:\n"); | |
ca31b95f JH |
688 | |
689 | /* Put all inline candidates into the heap. */ | |
690 | ||
691 | for (node = cgraph_nodes; node; node = node->next) | |
692 | { | |
693 | if (!node->local.inlinable || !node->callers | |
694 | || node->local.disregard_inline_limits) | |
695 | continue; | |
670cd5c5 JH |
696 | if (dump_file) |
697 | fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node)); | |
ca31b95f | 698 | |
670cd5c5 | 699 | node->global.estimated_growth = INT_MIN; |
9de21a23 | 700 | if (!cgraph_default_inline_p (node, &failed_reason)) |
ca31b95f | 701 | { |
9de21a23 | 702 | cgraph_set_inline_failed (node, failed_reason); |
ca31b95f JH |
703 | continue; |
704 | } | |
ca31b95f | 705 | |
670cd5c5 JH |
706 | for (edge = node->callers; edge; edge = edge->next_caller) |
707 | if (edge->inline_failed) | |
708 | { | |
709 | gcc_assert (!edge->aux); | |
710 | edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge); | |
711 | } | |
712 | } | |
713 | while (overall_insns <= max_insns && (edge = fibheap_extract_min (heap))) | |
ca31b95f | 714 | { |
ca31b95f | 715 | int old_insns = overall_insns; |
670cd5c5 JH |
716 | struct cgraph_node *where; |
717 | int growth = | |
718 | cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee); | |
719 | ||
720 | growth -= edge->caller->global.insns; | |
ca31b95f | 721 | |
ca31b95f | 722 | if (dump_file) |
ca31b95f | 723 | { |
670cd5c5 JH |
724 | fprintf (dump_file, |
725 | "\nConsidering %s with %i insns to be inlined into %s\n" | |
726 | " Estimated growth after inlined into all callees is %+i insns.\n" | |
727 | " Estimated badness is %i.\n", | |
728 | cgraph_node_name (edge->callee), | |
729 | edge->callee->global.insns, | |
730 | cgraph_node_name (edge->caller), | |
731 | cgraph_estimate_growth (edge->callee), | |
732 | cgraph_edge_badness (edge)); | |
733 | if (edge->count) | |
734 | fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count); | |
ca31b95f | 735 | } |
670cd5c5 JH |
736 | gcc_assert (edge->aux); |
737 | edge->aux = NULL; | |
738 | if (!edge->inline_failed) | |
739 | continue; | |
ca31b95f | 740 | |
670cd5c5 | 741 | /* When not having profile info ready we don't weight by any way the |
0fa2e4df | 742 | position of call in procedure itself. This means if call of |
670cd5c5 JH |
743 | function A from function B seems profitable to inline, the recursive |
744 | call of function A in inline copy of A in B will look profitable too | |
745 | and we end up inlining until reaching maximal function growth. This | |
746 | is not good idea so prohibit the recursive inlining. | |
ca31b95f | 747 | |
670cd5c5 JH |
748 | ??? When the frequencies are taken into account we might not need this |
749 | restriction. */ | |
750 | if (!max_count) | |
751 | { | |
752 | where = edge->caller; | |
753 | while (where->global.inlined_to) | |
754 | { | |
755 | if (where->decl == edge->callee->decl) | |
756 | break; | |
757 | where = where->callers->caller; | |
758 | } | |
759 | if (where->global.inlined_to) | |
760 | { | |
761 | edge->inline_failed | |
762 | = (edge->callee->local.disregard_inline_limits ? N_("recursive inlining") : ""); | |
ca31b95f | 763 | if (dump_file) |
cc9795d4 | 764 | fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n"); |
670cd5c5 | 765 | continue; |
ca31b95f JH |
766 | } |
767 | } | |
768 | ||
670cd5c5 JH |
769 | if (!cgraph_maybe_hot_edge_p (edge) && growth > 0) |
770 | { | |
771 | if (!cgraph_recursive_inlining_p (edge->caller, edge->callee, | |
772 | &edge->inline_failed)) | |
773 | { | |
774 | edge->inline_failed = | |
775 | N_("call is unlikely"); | |
776 | if (dump_file) | |
777 | fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed); | |
778 | } | |
779 | continue; | |
780 | } | |
9de21a23 | 781 | if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed)) |
670cd5c5 JH |
782 | { |
783 | if (!cgraph_recursive_inlining_p (edge->caller, edge->callee, | |
784 | &edge->inline_failed)) | |
785 | { | |
670cd5c5 JH |
786 | if (dump_file) |
787 | fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed); | |
788 | } | |
789 | continue; | |
790 | } | |
791 | if (cgraph_recursive_inlining_p (edge->caller, edge->callee, | |
792 | &edge->inline_failed)) | |
793 | { | |
794 | where = edge->caller; | |
795 | if (where->global.inlined_to) | |
796 | where = where->global.inlined_to; | |
797 | if (!cgraph_decide_recursive_inlining (where)) | |
798 | continue; | |
799 | update_callee_keys (heap, where, updated_nodes); | |
800 | } | |
801 | else | |
802 | { | |
facc20ee | 803 | struct cgraph_node *callee; |
670cd5c5 JH |
804 | if (!cgraph_check_inline_limits (edge->caller, edge->callee, |
805 | &edge->inline_failed)) | |
806 | { | |
807 | if (dump_file) | |
808 | fprintf (dump_file, " Not inlining into %s:%s.\n", | |
809 | cgraph_node_name (edge->caller), edge->inline_failed); | |
810 | continue; | |
811 | } | |
facc20ee | 812 | callee = edge->callee; |
06191a23 | 813 | cgraph_mark_inline_edge (edge, true); |
facc20ee | 814 | update_callee_keys (heap, callee, updated_nodes); |
670cd5c5 JH |
815 | } |
816 | where = edge->caller; | |
817 | if (where->global.inlined_to) | |
818 | where = where->global.inlined_to; | |
819 | ||
820 | /* Our profitability metric can depend on local properties | |
821 | such as number of inlinable calls and size of the function body. | |
822 | After inlining these properties might change for the function we | |
823 | inlined into (since it's body size changed) and for the functions | |
824 | called by function we inlined (since number of it inlinable callers | |
825 | might change). */ | |
826 | update_caller_keys (heap, where, updated_nodes); | |
827 | bitmap_clear (updated_nodes); | |
ca31b95f | 828 | |
670cd5c5 JH |
829 | if (dump_file) |
830 | fprintf (dump_file, | |
831 | " Inlined into %s which now has %i insns.\n", | |
832 | cgraph_node_name (edge->caller), | |
833 | edge->caller->global.insns); | |
ca31b95f JH |
834 | if (dump_file) |
835 | fprintf (dump_file, | |
836 | " Inlined for a net change of %+i insns.\n", | |
837 | overall_insns - old_insns); | |
838 | } | |
670cd5c5 JH |
839 | while ((edge = fibheap_extract_min (heap)) != NULL) |
840 | { | |
841 | gcc_assert (edge->aux); | |
842 | edge->aux = NULL; | |
843 | if (!edge->callee->local.disregard_inline_limits && edge->inline_failed | |
844 | && !cgraph_recursive_inlining_p (edge->caller, edge->callee, | |
845 | &edge->inline_failed)) | |
846 | edge->inline_failed = N_("--param inline-unit-growth limit reached"); | |
847 | } | |
ca31b95f | 848 | fibheap_delete (heap); |
670cd5c5 | 849 | BITMAP_FREE (updated_nodes); |
ca31b95f JH |
850 | } |
851 | ||
852 | /* Decide on the inlining. We do so in the topological order to avoid | |
853 | expenses on updating data structures. */ | |
854 | ||
855 | static void | |
856 | cgraph_decide_inlining (void) | |
857 | { | |
858 | struct cgraph_node *node; | |
859 | int nnodes; | |
860 | struct cgraph_node **order = | |
861 | xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); | |
862 | int old_insns = 0; | |
863 | int i; | |
864 | ||
670cd5c5 JH |
865 | timevar_push (TV_INLINE_HEURISTICS); |
866 | max_count = 0; | |
ca31b95f | 867 | for (node = cgraph_nodes; node; node = node->next) |
670cd5c5 JH |
868 | { |
869 | struct cgraph_edge *e; | |
870 | initial_insns += node->local.self_insns; | |
871 | for (e = node->callees; e; e = e->next_callee) | |
872 | if (max_count < e->count) | |
873 | max_count = e->count; | |
874 | } | |
ca31b95f | 875 | overall_insns = initial_insns; |
670cd5c5 JH |
876 | gcc_assert (!max_count || (profile_info && flag_branch_probabilities)); |
877 | ||
878 | max_insns = ((HOST_WIDEST_INT) overall_insns | |
879 | * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100); | |
ca31b95f JH |
880 | |
881 | nnodes = cgraph_postorder (order); | |
882 | ||
883 | if (dump_file) | |
884 | fprintf (dump_file, | |
885 | "\nDeciding on inlining. Starting with %i insns.\n", | |
886 | initial_insns); | |
887 | ||
888 | for (node = cgraph_nodes; node; node = node->next) | |
889 | node->aux = 0; | |
890 | ||
891 | if (dump_file) | |
892 | fprintf (dump_file, "\nInlining always_inline functions:\n"); | |
893 | ||
894 | /* In the first pass mark all always_inline edges. Do this with a priority | |
895 | so none of our later choices will make this impossible. */ | |
896 | for (i = nnodes - 1; i >= 0; i--) | |
897 | { | |
898 | struct cgraph_edge *e, *next; | |
899 | ||
900 | node = order[i]; | |
901 | ||
0691d1d4 RG |
902 | /* Handle nodes to be flattened, but don't update overall unit size. */ |
903 | if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL) | |
904 | { | |
905 | int old_overall_insns = overall_insns; | |
906 | htab_t cycles; | |
907 | if (dump_file) | |
908 | fprintf (dump_file, | |
909 | "Leafifying %s\n", cgraph_node_name (node)); | |
910 | cycles = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL); | |
911 | cgraph_find_cycles (node, cycles); | |
912 | cgraph_flatten_node (node, cycles); | |
913 | htab_delete (cycles); | |
914 | overall_insns = old_overall_insns; | |
915 | /* We don't need to consider always_inline functions inside the flattened | |
916 | function anymore. */ | |
917 | continue; | |
918 | } | |
919 | ||
ca31b95f JH |
920 | if (!node->local.disregard_inline_limits) |
921 | continue; | |
922 | if (dump_file) | |
923 | fprintf (dump_file, | |
924 | "\nConsidering %s %i insns (always inline)\n", | |
925 | cgraph_node_name (node), node->global.insns); | |
926 | old_insns = overall_insns; | |
927 | for (e = node->callers; e; e = next) | |
928 | { | |
929 | next = e->next_caller; | |
930 | if (!e->inline_failed) | |
931 | continue; | |
932 | if (cgraph_recursive_inlining_p (e->caller, e->callee, | |
933 | &e->inline_failed)) | |
934 | continue; | |
06191a23 | 935 | cgraph_mark_inline_edge (e, true); |
ca31b95f JH |
936 | if (dump_file) |
937 | fprintf (dump_file, | |
938 | " Inlined into %s which now has %i insns.\n", | |
939 | cgraph_node_name (e->caller), | |
940 | e->caller->global.insns); | |
941 | } | |
942 | if (dump_file) | |
943 | fprintf (dump_file, | |
944 | " Inlined for a net change of %+i insns.\n", | |
945 | overall_insns - old_insns); | |
946 | } | |
947 | ||
948 | if (!flag_really_no_inline) | |
355866de | 949 | cgraph_decide_inlining_of_small_functions (); |
ca31b95f | 950 | |
355866de RG |
951 | if (!flag_really_no_inline |
952 | && flag_inline_functions_called_once) | |
953 | { | |
ca31b95f JH |
954 | if (dump_file) |
955 | fprintf (dump_file, "\nDeciding on functions called once:\n"); | |
956 | ||
957 | /* And finally decide what functions are called once. */ | |
958 | ||
959 | for (i = nnodes - 1; i >= 0; i--) | |
960 | { | |
961 | node = order[i]; | |
962 | ||
963 | if (node->callers && !node->callers->next_caller && !node->needed | |
964 | && node->local.inlinable && node->callers->inline_failed | |
965 | && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl)) | |
966 | { | |
967 | bool ok = true; | |
968 | struct cgraph_node *node1; | |
969 | ||
970 | /* Verify that we won't duplicate the caller. */ | |
971 | for (node1 = node->callers->caller; | |
972 | node1->callers && !node1->callers->inline_failed | |
973 | && ok; node1 = node1->callers->caller) | |
974 | if (node1->callers->next_caller || node1->needed) | |
975 | ok = false; | |
976 | if (ok) | |
977 | { | |
978 | if (dump_file) | |
979 | fprintf (dump_file, | |
980 | "\nConsidering %s %i insns.\n" | |
981 | " Called once from %s %i insns.\n", | |
982 | cgraph_node_name (node), node->global.insns, | |
983 | cgraph_node_name (node->callers->caller), | |
984 | node->callers->caller->global.insns); | |
985 | ||
986 | old_insns = overall_insns; | |
987 | ||
988 | if (cgraph_check_inline_limits (node->callers->caller, node, | |
989 | NULL)) | |
990 | { | |
991 | cgraph_mark_inline (node->callers); | |
992 | if (dump_file) | |
993 | fprintf (dump_file, | |
994 | " Inlined into %s which now has %i insns" | |
995 | " for a net change of %+i insns.\n", | |
996 | cgraph_node_name (node->callers->caller), | |
997 | node->callers->caller->global.insns, | |
998 | overall_insns - old_insns); | |
999 | } | |
1000 | else | |
1001 | { | |
1002 | if (dump_file) | |
1003 | fprintf (dump_file, | |
1004 | " Inline limit reached, not inlined.\n"); | |
1005 | } | |
1006 | } | |
1007 | } | |
1008 | } | |
1009 | } | |
1010 | ||
ca31b95f JH |
1011 | if (dump_file) |
1012 | fprintf (dump_file, | |
1013 | "\nInlined %i calls, eliminated %i functions, " | |
1014 | "%i insns turned to %i insns.\n\n", | |
1015 | ncalls_inlined, nfunctions_inlined, initial_insns, | |
1016 | overall_insns); | |
1017 | free (order); | |
670cd5c5 | 1018 | timevar_pop (TV_INLINE_HEURISTICS); |
ca31b95f JH |
1019 | } |
1020 | ||
1021 | /* Decide on the inlining. We do so in the topological order to avoid | |
1022 | expenses on updating data structures. */ | |
1023 | ||
d63db217 JH |
1024 | bool |
1025 | cgraph_decide_inlining_incrementally (struct cgraph_node *node, bool early) | |
ca31b95f JH |
1026 | { |
1027 | struct cgraph_edge *e; | |
d63db217 | 1028 | bool inlined = false; |
9de21a23 | 1029 | const char *failed_reason; |
ca31b95f JH |
1030 | |
1031 | /* First of all look for always inline functions. */ | |
1032 | for (e = node->callees; e; e = e->next_callee) | |
1033 | if (e->callee->local.disregard_inline_limits | |
1034 | && e->inline_failed | |
1035 | && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed) | |
1036 | /* ??? It is possible that renaming variable removed the function body | |
1037 | in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */ | |
1038 | && DECL_SAVED_TREE (e->callee->decl)) | |
d63db217 JH |
1039 | { |
1040 | if (dump_file && early) | |
1041 | fprintf (dump_file, " Early inlining %s into %s\n", | |
1042 | cgraph_node_name (e->callee), cgraph_node_name (node)); | |
1043 | cgraph_mark_inline (e); | |
1044 | inlined = true; | |
1045 | } | |
ca31b95f JH |
1046 | |
1047 | /* Now do the automatic inlining. */ | |
1048 | if (!flag_really_no_inline) | |
1049 | for (e = node->callees; e; e = e->next_callee) | |
1050 | if (e->callee->local.inlinable | |
1051 | && e->inline_failed | |
1052 | && !e->callee->local.disregard_inline_limits | |
1053 | && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed) | |
d63db217 JH |
1054 | && (!early |
1055 | || (cgraph_estimate_size_after_inlining (1, e->caller, node) | |
1056 | <= e->caller->global.insns)) | |
ca31b95f JH |
1057 | && cgraph_check_inline_limits (node, e->callee, &e->inline_failed) |
1058 | && DECL_SAVED_TREE (e->callee->decl)) | |
1059 | { | |
9de21a23 | 1060 | if (cgraph_default_inline_p (e->callee, &failed_reason)) |
d63db217 JH |
1061 | { |
1062 | if (dump_file && early) | |
1063 | fprintf (dump_file, " Early inlining %s into %s\n", | |
1064 | cgraph_node_name (e->callee), cgraph_node_name (node)); | |
1065 | cgraph_mark_inline (e); | |
1066 | inlined = true; | |
1067 | } | |
1068 | else if (!early) | |
9de21a23 | 1069 | e->inline_failed = failed_reason; |
ca31b95f | 1070 | } |
d63db217 JH |
1071 | if (early && inlined) |
1072 | { | |
1073 | push_cfun (DECL_STRUCT_FUNCTION (node->decl)); | |
1074 | tree_register_cfg_hooks (); | |
1075 | current_function_decl = node->decl; | |
1076 | optimize_inline_calls (current_function_decl); | |
1077 | node->local.self_insns = node->global.insns; | |
1078 | current_function_decl = NULL; | |
1079 | pop_cfun (); | |
d63db217 JH |
1080 | } |
1081 | return inlined; | |
ca31b95f JH |
1082 | } |
1083 | ||
1084 | /* When inlining shall be performed. */ | |
1085 | static bool | |
1086 | cgraph_gate_inlining (void) | |
1087 | { | |
1088 | return flag_inline_trees; | |
1089 | } | |
1090 | ||
1091 | struct tree_opt_pass pass_ipa_inline = | |
1092 | { | |
1093 | "inline", /* name */ | |
1094 | cgraph_gate_inlining, /* gate */ | |
1095 | cgraph_decide_inlining, /* execute */ | |
1096 | NULL, /* sub */ | |
1097 | NULL, /* next */ | |
1098 | 0, /* static_pass_number */ | |
1099 | TV_INTEGRATION, /* tv_id */ | |
1100 | 0, /* properties_required */ | |
d63db217 JH |
1101 | PROP_cfg, /* properties_provided */ |
1102 | 0, /* properties_destroyed */ | |
1103 | 0, /* todo_flags_start */ | |
1104 | TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */ | |
1105 | 0 /* letter */ | |
1106 | }; | |
1107 | ||
1108 | /* Do inlining of small functions. Doing so early helps profiling and other | |
1109 | passes to be somewhat more effective and avoids some code duplication in | |
1110 | later real inlining pass for testcases with very many function calls. */ | |
1111 | static void | |
1112 | cgraph_early_inlining (void) | |
1113 | { | |
1114 | struct cgraph_node *node; | |
1115 | int nnodes; | |
1116 | struct cgraph_node **order = | |
1117 | xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); | |
1118 | int i; | |
1119 | ||
1120 | if (sorrycount || errorcount) | |
1121 | return; | |
1122 | #ifdef ENABLE_CHECKING | |
1123 | for (node = cgraph_nodes; node; node = node->next) | |
1124 | gcc_assert (!node->aux); | |
1125 | #endif | |
1126 | ||
1127 | nnodes = cgraph_postorder (order); | |
1128 | for (i = nnodes - 1; i >= 0; i--) | |
1129 | { | |
1130 | node = order[i]; | |
1131 | if (node->analyzed && node->local.inlinable | |
1132 | && (node->needed || node->reachable) | |
1133 | && node->callers) | |
1134 | cgraph_decide_inlining_incrementally (node, true); | |
1135 | } | |
1136 | cgraph_remove_unreachable_nodes (true, dump_file); | |
1137 | #ifdef ENABLE_CHECKING | |
1138 | for (node = cgraph_nodes; node; node = node->next) | |
1139 | gcc_assert (!node->global.inlined_to); | |
1140 | #endif | |
1141 | free (order); | |
1142 | } | |
1143 | ||
1144 | /* When inlining shall be performed. */ | |
1145 | static bool | |
1146 | cgraph_gate_early_inlining (void) | |
1147 | { | |
1148 | return flag_inline_trees && flag_early_inlining; | |
1149 | } | |
1150 | ||
1151 | struct tree_opt_pass pass_early_ipa_inline = | |
1152 | { | |
1153 | "einline", /* name */ | |
1154 | cgraph_gate_early_inlining, /* gate */ | |
1155 | cgraph_early_inlining, /* execute */ | |
1156 | NULL, /* sub */ | |
1157 | NULL, /* next */ | |
1158 | 0, /* static_pass_number */ | |
1159 | TV_INTEGRATION, /* tv_id */ | |
1160 | 0, /* properties_required */ | |
1161 | PROP_cfg, /* properties_provided */ | |
ca31b95f JH |
1162 | 0, /* properties_destroyed */ |
1163 | 0, /* todo_flags_start */ | |
1164 | TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */ | |
1165 | 0 /* letter */ | |
1166 | }; |