2015-05-05 Yvan Roux <yvan.roux@linaro.org>
[official-gcc.git] / gcc / ipa-inline-transform.c
blob5a628f39dd68b6c314e6ea19a25de0286497d54c
1 /* Callgraph transformations to handle inlining
2 Copyright (C) 2003-2015 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
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 3, or (at your option) any later
10 version.
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.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* The inline decisions are stored in callgraph in "inline plan" and
22 applied later.
24 To mark given call inline, use inline_call function.
25 The function marks the edge inlinable and, if necessary, produces
26 virtual clone in the callgraph representing the new copy of callee's
27 function body.
29 The inline plan is applied on given function body by inline_transform. */
31 #include "config.h"
32 #include "system.h"
33 #include "coretypes.h"
34 #include "tm.h"
35 #include "hash-set.h"
36 #include "machmode.h"
37 #include "vec.h"
38 #include "double-int.h"
39 #include "input.h"
40 #include "alias.h"
41 #include "symtab.h"
42 #include "wide-int.h"
43 #include "inchash.h"
44 #include "tree.h"
45 #include "langhooks.h"
46 #include "intl.h"
47 #include "coverage.h"
48 #include "ggc.h"
49 #include "tree-cfg.h"
50 #include "hash-map.h"
51 #include "is-a.h"
52 #include "plugin-api.h"
53 #include "hard-reg-set.h"
54 #include "input.h"
55 #include "function.h"
56 #include "ipa-ref.h"
57 #include "cgraph.h"
58 #include "alloc-pool.h"
59 #include "symbol-summary.h"
60 #include "ipa-prop.h"
61 #include "ipa-inline.h"
62 #include "tree-inline.h"
63 #include "tree-pass.h"
65 int ncalls_inlined;
66 int nfunctions_inlined;
68 /* Scale frequency of NODE edges by FREQ_SCALE. */
70 static void
71 update_noncloned_frequencies (struct cgraph_node *node,
72 int freq_scale)
74 struct cgraph_edge *e;
76 /* We do not want to ignore high loop nest after freq drops to 0. */
77 if (!freq_scale)
78 freq_scale = 1;
79 for (e = node->callees; e; e = e->next_callee)
81 e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
82 if (e->frequency > CGRAPH_FREQ_MAX)
83 e->frequency = CGRAPH_FREQ_MAX;
84 if (!e->inline_failed)
85 update_noncloned_frequencies (e->callee, freq_scale);
87 for (e = node->indirect_calls; e; e = e->next_callee)
89 e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
90 if (e->frequency > CGRAPH_FREQ_MAX)
91 e->frequency = CGRAPH_FREQ_MAX;
95 /* We removed or are going to remove the last call to NODE.
96 Return true if we can and want proactively remove the NODE now.
97 This is important to do, since we want inliner to know when offline
98 copy of function was removed. */
100 static bool
101 can_remove_node_now_p_1 (struct cgraph_node *node, struct cgraph_edge *e)
103 ipa_ref *ref;
105 FOR_EACH_ALIAS (node, ref)
107 cgraph_node *alias = dyn_cast <cgraph_node *> (ref->referring);
108 if ((alias->callers && alias->callers != e)
109 || !can_remove_node_now_p_1 (alias, e))
110 return false;
112 /* FIXME: When address is taken of DECL_EXTERNAL function we still
113 can remove its offline copy, but we would need to keep unanalyzed node in
114 the callgraph so references can point to it.
116 Also for comdat group we can ignore references inside a group as we
117 want to prove the group as a whole to be dead. */
118 return (!node->address_taken
119 && node->can_remove_if_no_direct_calls_and_refs_p ()
120 /* Inlining might enable more devirtualizing, so we want to remove
121 those only after all devirtualizable virtual calls are processed.
122 Lacking may edges in callgraph we just preserve them post
123 inlining. */
124 && (!DECL_VIRTUAL_P (node->decl)
125 || !opt_for_fn (node->decl, flag_devirtualize))
126 /* During early inlining some unanalyzed cgraph nodes might be in the
127 callgraph and they might reffer the function in question. */
128 && !cgraph_new_nodes.exists ());
131 /* We are going to eliminate last direct call to NODE (or alias of it) via edge E.
132 Verify that the NODE can be removed from unit and if it is contained in comdat
133 group that the whole comdat group is removable. */
135 static bool
136 can_remove_node_now_p (struct cgraph_node *node, struct cgraph_edge *e)
138 struct cgraph_node *next;
139 if (!can_remove_node_now_p_1 (node, e))
140 return false;
142 /* When we see same comdat group, we need to be sure that all
143 items can be removed. */
144 if (!node->same_comdat_group || !node->externally_visible)
145 return true;
146 for (next = dyn_cast<cgraph_node *> (node->same_comdat_group);
147 next != node; next = dyn_cast<cgraph_node *> (next->same_comdat_group))
149 if (next->alias)
150 continue;
151 if ((next->callers && next->callers != e)
152 || !can_remove_node_now_p_1 (next, e))
153 return false;
155 return true;
158 /* Return true if NODE is a master clone with non-inline clones. */
160 static bool
161 master_clone_with_noninline_clones_p (struct cgraph_node *node)
163 if (node->clone_of)
164 return false;
166 for (struct cgraph_node *n = node->clones; n; n = n->next_sibling_clone)
167 if (n->decl != node->decl)
168 return true;
170 return false;
173 /* E is expected to be an edge being inlined. Clone destination node of
174 the edge and redirect it to the new clone.
175 DUPLICATE is used for bookkeeping on whether we are actually creating new
176 clones or re-using node originally representing out-of-line function call.
177 By default the offline copy is removed, when it appears dead after inlining.
178 UPDATE_ORIGINAL prevents this transformation.
179 If OVERALL_SIZE is non-NULL, the size is updated to reflect the
180 transformation.
181 FREQ_SCALE specify the scaling of frequencies of call sites. */
183 void
184 clone_inlined_nodes (struct cgraph_edge *e, bool duplicate,
185 bool update_original, int *overall_size, int freq_scale)
187 struct cgraph_node *inlining_into;
188 struct cgraph_edge *next;
190 if (e->caller->global.inlined_to)
191 inlining_into = e->caller->global.inlined_to;
192 else
193 inlining_into = e->caller;
195 if (duplicate)
197 /* We may eliminate the need for out-of-line copy to be output.
198 In that case just go ahead and re-use it. This is not just an
199 memory optimization. Making offline copy of fuction disappear
200 from the program will improve future decisions on inlining. */
201 if (!e->callee->callers->next_caller
202 /* Recursive inlining never wants the master clone to
203 be overwritten. */
204 && update_original
205 && can_remove_node_now_p (e->callee, e)
206 /* We cannot overwrite a master clone with non-inline clones
207 until after these clones are materialized. */
208 && !master_clone_with_noninline_clones_p (e->callee))
210 /* TODO: When callee is in a comdat group, we could remove all of it,
211 including all inline clones inlined into it. That would however
212 need small function inlining to register edge removal hook to
213 maintain the priority queue.
215 For now we keep the ohter functions in the group in program until
216 cgraph_remove_unreachable_functions gets rid of them. */
217 gcc_assert (!e->callee->global.inlined_to);
218 e->callee->remove_from_same_comdat_group ();
219 if (e->callee->definition
220 && inline_account_function_p (e->callee))
222 gcc_assert (!e->callee->alias);
223 if (overall_size)
224 *overall_size -= inline_summaries->get (e->callee)->size;
225 nfunctions_inlined++;
227 duplicate = false;
228 e->callee->externally_visible = false;
229 update_noncloned_frequencies (e->callee, e->frequency);
231 else
233 struct cgraph_node *n;
235 if (freq_scale == -1)
236 freq_scale = e->frequency;
237 n = e->callee->create_clone (e->callee->decl,
238 MIN (e->count, e->callee->count),
239 freq_scale,
240 update_original, vNULL, true,
241 inlining_into,
242 NULL);
243 n->used_as_abstract_origin = e->callee->used_as_abstract_origin;
244 e->redirect_callee (n);
247 else
248 e->callee->remove_from_same_comdat_group ();
250 e->callee->global.inlined_to = inlining_into;
252 /* Recursively clone all bodies. */
253 for (e = e->callee->callees; e; e = next)
255 next = e->next_callee;
256 if (!e->inline_failed)
257 clone_inlined_nodes (e, duplicate, update_original, overall_size, freq_scale);
261 /* Check all speculations in N and resolve them if they seems useless. */
263 static bool
264 check_speculations (cgraph_node *n)
266 bool speculation_removed = false;
267 cgraph_edge *next;
269 for (cgraph_edge *e = n->callees; e; e = next)
271 next = e->next_callee;
272 if (e->speculative && !speculation_useful_p (e, true))
274 e->resolve_speculation (NULL);
275 speculation_removed = true;
277 else if (!e->inline_failed)
278 speculation_removed |= check_speculations (e->callee);
280 return speculation_removed;
283 /* Mark all call graph edges coming out of NODE and all nodes that have been
284 inlined to it as in_polymorphic_cdtor. */
286 static void
287 mark_all_inlined_calls_cdtor (cgraph_node *node)
289 for (cgraph_edge *cs = node->callees; cs; cs = cs->next_callee)
291 cs->in_polymorphic_cdtor = true;
292 if (!cs->inline_failed)
293 mark_all_inlined_calls_cdtor (cs->callee);
295 for (cgraph_edge *cs = node->indirect_calls; cs; cs = cs->next_callee)
296 cs->in_polymorphic_cdtor = true;
300 /* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL
301 specify whether profile of original function should be updated. If any new
302 indirect edges are discovered in the process, add them to NEW_EDGES, unless
303 it is NULL. If UPDATE_OVERALL_SUMMARY is false, do not bother to recompute overall
304 size of caller after inlining. Caller is required to eventually do it via
305 inline_update_overall_summary.
306 If callee_removed is non-NULL, set it to true if we removed callee node.
308 Return true iff any new callgraph edges were discovered as a
309 result of inlining. */
311 bool
312 inline_call (struct cgraph_edge *e, bool update_original,
313 vec<cgraph_edge *> *new_edges,
314 int *overall_size, bool update_overall_summary,
315 bool *callee_removed)
317 int old_size = 0, new_size = 0;
318 struct cgraph_node *to = NULL;
319 struct cgraph_edge *curr = e;
320 struct cgraph_node *callee = e->callee->ultimate_alias_target ();
321 bool new_edges_found = false;
323 /* This is used only for assert bellow. */
324 #if 0
325 int estimated_growth = estimate_edge_growth (e);
326 bool predicated = inline_edge_summary (e)->predicate != NULL;
327 #endif
329 /* Don't inline inlined edges. */
330 gcc_assert (e->inline_failed);
331 /* Don't even think of inlining inline clone. */
332 gcc_assert (!callee->global.inlined_to);
334 e->inline_failed = CIF_OK;
335 DECL_POSSIBLY_INLINED (callee->decl) = true;
337 to = e->caller;
338 if (to->global.inlined_to)
339 to = to->global.inlined_to;
341 if (DECL_FUNCTION_PERSONALITY (callee->decl))
342 DECL_FUNCTION_PERSONALITY (to->decl)
343 = DECL_FUNCTION_PERSONALITY (callee->decl);
345 /* If aliases are involved, redirect edge to the actual destination and
346 possibly remove the aliases. */
347 if (e->callee != callee)
349 struct cgraph_node *alias = e->callee, *next_alias;
350 e->redirect_callee (callee);
351 while (alias && alias != callee)
353 if (!alias->callers
354 && can_remove_node_now_p (alias,
355 !e->next_caller && !e->prev_caller ? e : NULL))
357 next_alias = alias->get_alias_target ();
358 alias->remove ();
359 if (callee_removed)
360 *callee_removed = true;
361 alias = next_alias;
363 else
364 break;
368 clone_inlined_nodes (e, true, update_original, overall_size, e->frequency);
370 gcc_assert (curr->callee->global.inlined_to == to);
372 old_size = inline_summaries->get (to)->size;
373 inline_merge_summary (e);
374 if (e->in_polymorphic_cdtor)
375 mark_all_inlined_calls_cdtor (e->callee);
376 if (opt_for_fn (e->caller->decl, optimize))
377 new_edges_found = ipa_propagate_indirect_call_infos (curr, new_edges);
378 check_speculations (e->callee);
379 if (update_overall_summary)
380 inline_update_overall_summary (to);
381 new_size = inline_summaries->get (to)->size;
383 if (callee->calls_comdat_local)
384 to->calls_comdat_local = true;
385 else if (to->calls_comdat_local && callee->comdat_local_p ())
387 struct cgraph_edge *se = to->callees;
388 for (; se; se = se->next_callee)
389 if (se->inline_failed && se->callee->comdat_local_p ())
390 break;
391 if (se == NULL)
392 to->calls_comdat_local = false;
395 /* FIXME: This assert suffers from roundoff errors, disable it for GCC 5
396 and revisit it after conversion to sreals in GCC 6.
397 See PR 65654. */
398 #if 0
399 /* Verify that estimated growth match real growth. Allow off-by-one
400 error due to INLINE_SIZE_SCALE roudoff errors. */
401 gcc_assert (!update_overall_summary || !overall_size || new_edges_found
402 || abs (estimated_growth - (new_size - old_size)) <= 1
403 || speculation_removed
404 /* FIXME: a hack. Edges with false predicate are accounted
405 wrong, we should remove them from callgraph. */
406 || predicated);
407 #endif
409 /* Account the change of overall unit size; external functions will be
410 removed and are thus not accounted. */
411 if (overall_size && inline_account_function_p (to))
412 *overall_size += new_size - old_size;
413 ncalls_inlined++;
415 /* This must happen after inline_merge_summary that rely on jump
416 functions of callee to not be updated. */
417 return new_edges_found;
421 /* Copy function body of NODE and redirect all inline clones to it.
422 This is done before inline plan is applied to NODE when there are
423 still some inline clones if it.
425 This is necessary because inline decisions are not really transitive
426 and the other inline clones may have different bodies. */
428 static struct cgraph_node *
429 save_inline_function_body (struct cgraph_node *node)
431 struct cgraph_node *first_clone, *n;
433 if (dump_file)
434 fprintf (dump_file, "\nSaving body of %s for later reuse\n",
435 node->name ());
437 gcc_assert (node == cgraph_node::get (node->decl));
439 /* first_clone will be turned into real function. */
440 first_clone = node->clones;
441 first_clone->decl = copy_node (node->decl);
442 first_clone->decl->decl_with_vis.symtab_node = first_clone;
443 gcc_assert (first_clone == cgraph_node::get (first_clone->decl));
445 /* Now reshape the clone tree, so all other clones descends from
446 first_clone. */
447 if (first_clone->next_sibling_clone)
449 for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
450 n->clone_of = first_clone;
451 n->clone_of = first_clone;
452 n->next_sibling_clone = first_clone->clones;
453 if (first_clone->clones)
454 first_clone->clones->prev_sibling_clone = n;
455 first_clone->clones = first_clone->next_sibling_clone;
456 first_clone->next_sibling_clone->prev_sibling_clone = NULL;
457 first_clone->next_sibling_clone = NULL;
458 gcc_assert (!first_clone->prev_sibling_clone);
460 first_clone->clone_of = NULL;
462 /* Now node in question has no clones. */
463 node->clones = NULL;
465 /* Inline clones share decl with the function they are cloned
466 from. Walk the whole clone tree and redirect them all to the
467 new decl. */
468 if (first_clone->clones)
469 for (n = first_clone->clones; n != first_clone;)
471 gcc_assert (n->decl == node->decl);
472 n->decl = first_clone->decl;
473 if (n->clones)
474 n = n->clones;
475 else if (n->next_sibling_clone)
476 n = n->next_sibling_clone;
477 else
479 while (n != first_clone && !n->next_sibling_clone)
480 n = n->clone_of;
481 if (n != first_clone)
482 n = n->next_sibling_clone;
486 /* Copy the OLD_VERSION_NODE function tree to the new version. */
487 tree_function_versioning (node->decl, first_clone->decl,
488 NULL, true, NULL, false,
489 NULL, NULL);
491 /* The function will be short lived and removed after we inline all the clones,
492 but make it internal so we won't confuse ourself. */
493 DECL_EXTERNAL (first_clone->decl) = 0;
494 TREE_PUBLIC (first_clone->decl) = 0;
495 DECL_COMDAT (first_clone->decl) = 0;
496 first_clone->ipa_transforms_to_apply.release ();
498 /* When doing recursive inlining, the clone may become unnecessary.
499 This is possible i.e. in the case when the recursive function is proved to be
500 non-throwing and the recursion happens only in the EH landing pad.
501 We can not remove the clone until we are done with saving the body.
502 Remove it now. */
503 if (!first_clone->callers)
505 first_clone->remove_symbol_and_inline_clones ();
506 first_clone = NULL;
508 #ifdef ENABLE_CHECKING
509 else
510 first_clone->verify ();
511 #endif
512 return first_clone;
515 /* Return true when function body of DECL still needs to be kept around
516 for later re-use. */
517 static bool
518 preserve_function_body_p (struct cgraph_node *node)
520 gcc_assert (symtab->global_info_ready);
521 gcc_assert (!node->alias && !node->thunk.thunk_p);
523 /* Look if there is any clone around. */
524 if (node->clones)
525 return true;
526 return false;
529 /* Apply inline plan to function. */
531 unsigned int
532 inline_transform (struct cgraph_node *node)
534 unsigned int todo = 0;
535 struct cgraph_edge *e, *next;
536 bool has_inline = false;
538 /* FIXME: Currently the pass manager is adding inline transform more than
539 once to some clones. This needs revisiting after WPA cleanups. */
540 if (cfun->after_inlining)
541 return 0;
543 /* We might need the body of this function so that we can expand
544 it inline somewhere else. */
545 if (preserve_function_body_p (node))
546 save_inline_function_body (node);
548 for (e = node->callees; e; e = next)
550 if (!e->inline_failed)
551 has_inline = true;
552 next = e->next_callee;
553 e->redirect_call_stmt_to_callee ();
555 node->remove_all_references ();
557 timevar_push (TV_INTEGRATION);
558 if (node->callees && (opt_for_fn (node->decl, optimize) || has_inline))
559 todo = optimize_inline_calls (current_function_decl);
560 timevar_pop (TV_INTEGRATION);
562 cfun->always_inline_functions_inlined = true;
563 cfun->after_inlining = true;
564 todo |= execute_fixup_cfg ();
566 if (!(todo & TODO_update_ssa_any))
567 /* Redirecting edges might lead to a need for vops to be recomputed. */
568 todo |= TODO_update_ssa_only_virtuals;
570 return todo;