2016-05-04 Thomas Preud'homme <thomas.preudhomme@arm.com>
[official-gcc.git] / gcc / ipa-inline-transform.c
blob759617bb72f5b41a564b99c045db69799de86f4a
1 /* Callgraph transformations to handle inlining
2 Copyright (C) 2003-2016 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 "function.h"
36 #include "tree.h"
37 #include "alloc-pool.h"
38 #include "tree-pass.h"
39 #include "cgraph.h"
40 #include "tree-cfg.h"
41 #include "symbol-summary.h"
42 #include "ipa-prop.h"
43 #include "ipa-inline.h"
44 #include "tree-inline.h"
46 int ncalls_inlined;
47 int nfunctions_inlined;
49 /* Scale frequency of NODE edges by FREQ_SCALE. */
51 static void
52 update_noncloned_frequencies (struct cgraph_node *node,
53 int freq_scale)
55 struct cgraph_edge *e;
57 /* We do not want to ignore high loop nest after freq drops to 0. */
58 if (!freq_scale)
59 freq_scale = 1;
60 for (e = node->callees; e; e = e->next_callee)
62 e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
63 if (e->frequency > CGRAPH_FREQ_MAX)
64 e->frequency = CGRAPH_FREQ_MAX;
65 if (!e->inline_failed)
66 update_noncloned_frequencies (e->callee, freq_scale);
68 for (e = node->indirect_calls; e; e = e->next_callee)
70 e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
71 if (e->frequency > CGRAPH_FREQ_MAX)
72 e->frequency = CGRAPH_FREQ_MAX;
76 /* We removed or are going to remove the last call to NODE.
77 Return true if we can and want proactively remove the NODE now.
78 This is important to do, since we want inliner to know when offline
79 copy of function was removed. */
81 static bool
82 can_remove_node_now_p_1 (struct cgraph_node *node, struct cgraph_edge *e)
84 ipa_ref *ref;
86 FOR_EACH_ALIAS (node, ref)
88 cgraph_node *alias = dyn_cast <cgraph_node *> (ref->referring);
89 if ((alias->callers && alias->callers != e)
90 || !can_remove_node_now_p_1 (alias, e))
91 return false;
93 /* FIXME: When address is taken of DECL_EXTERNAL function we still
94 can remove its offline copy, but we would need to keep unanalyzed node in
95 the callgraph so references can point to it.
97 Also for comdat group we can ignore references inside a group as we
98 want to prove the group as a whole to be dead. */
99 return (!node->address_taken
100 && node->can_remove_if_no_direct_calls_and_refs_p ()
101 /* Inlining might enable more devirtualizing, so we want to remove
102 those only after all devirtualizable virtual calls are processed.
103 Lacking may edges in callgraph we just preserve them post
104 inlining. */
105 && (!DECL_VIRTUAL_P (node->decl)
106 || !opt_for_fn (node->decl, flag_devirtualize))
107 /* During early inlining some unanalyzed cgraph nodes might be in the
108 callgraph and they might reffer the function in question. */
109 && !cgraph_new_nodes.exists ());
112 /* We are going to eliminate last direct call to NODE (or alias of it) via edge E.
113 Verify that the NODE can be removed from unit and if it is contained in comdat
114 group that the whole comdat group is removable. */
116 static bool
117 can_remove_node_now_p (struct cgraph_node *node, struct cgraph_edge *e)
119 struct cgraph_node *next;
120 if (!can_remove_node_now_p_1 (node, e))
121 return false;
123 /* When we see same comdat group, we need to be sure that all
124 items can be removed. */
125 if (!node->same_comdat_group || !node->externally_visible)
126 return true;
127 for (next = dyn_cast<cgraph_node *> (node->same_comdat_group);
128 next != node; next = dyn_cast<cgraph_node *> (next->same_comdat_group))
130 if (next->alias)
131 continue;
132 if ((next->callers && next->callers != e)
133 || !can_remove_node_now_p_1 (next, e))
134 return false;
136 return true;
139 /* Return true if NODE is a master clone with non-inline clones. */
141 static bool
142 master_clone_with_noninline_clones_p (struct cgraph_node *node)
144 if (node->clone_of)
145 return false;
147 for (struct cgraph_node *n = node->clones; n; n = n->next_sibling_clone)
148 if (n->decl != node->decl)
149 return true;
151 return false;
154 /* E is expected to be an edge being inlined. Clone destination node of
155 the edge and redirect it to the new clone.
156 DUPLICATE is used for bookkeeping on whether we are actually creating new
157 clones or re-using node originally representing out-of-line function call.
158 By default the offline copy is removed, when it appears dead after inlining.
159 UPDATE_ORIGINAL prevents this transformation.
160 If OVERALL_SIZE is non-NULL, the size is updated to reflect the
161 transformation.
162 FREQ_SCALE specify the scaling of frequencies of call sites. */
164 void
165 clone_inlined_nodes (struct cgraph_edge *e, bool duplicate,
166 bool update_original, int *overall_size, int freq_scale)
168 struct cgraph_node *inlining_into;
169 struct cgraph_edge *next;
171 if (e->caller->global.inlined_to)
172 inlining_into = e->caller->global.inlined_to;
173 else
174 inlining_into = e->caller;
176 if (duplicate)
178 /* We may eliminate the need for out-of-line copy to be output.
179 In that case just go ahead and re-use it. This is not just an
180 memory optimization. Making offline copy of fuction disappear
181 from the program will improve future decisions on inlining. */
182 if (!e->callee->callers->next_caller
183 /* Recursive inlining never wants the master clone to
184 be overwritten. */
185 && update_original
186 && can_remove_node_now_p (e->callee, e)
187 /* We cannot overwrite a master clone with non-inline clones
188 until after these clones are materialized. */
189 && !master_clone_with_noninline_clones_p (e->callee))
191 /* TODO: When callee is in a comdat group, we could remove all of it,
192 including all inline clones inlined into it. That would however
193 need small function inlining to register edge removal hook to
194 maintain the priority queue.
196 For now we keep the ohter functions in the group in program until
197 cgraph_remove_unreachable_functions gets rid of them. */
198 gcc_assert (!e->callee->global.inlined_to);
199 e->callee->remove_from_same_comdat_group ();
200 if (e->callee->definition
201 && inline_account_function_p (e->callee))
203 gcc_assert (!e->callee->alias);
204 if (overall_size)
205 *overall_size -= inline_summaries->get (e->callee)->size;
206 nfunctions_inlined++;
208 duplicate = false;
209 e->callee->externally_visible = false;
210 update_noncloned_frequencies (e->callee, e->frequency);
212 else
214 struct cgraph_node *n;
216 if (freq_scale == -1)
217 freq_scale = e->frequency;
218 n = e->callee->create_clone (e->callee->decl,
219 MIN (e->count, e->callee->count),
220 freq_scale,
221 update_original, vNULL, true,
222 inlining_into,
223 NULL);
224 n->used_as_abstract_origin = e->callee->used_as_abstract_origin;
225 e->redirect_callee (n);
228 else
229 e->callee->remove_from_same_comdat_group ();
231 e->callee->global.inlined_to = inlining_into;
233 /* Recursively clone all bodies. */
234 for (e = e->callee->callees; e; e = next)
236 next = e->next_callee;
237 if (!e->inline_failed)
238 clone_inlined_nodes (e, duplicate, update_original, overall_size, freq_scale);
242 /* Check all speculations in N and resolve them if they seems useless. */
244 static bool
245 check_speculations (cgraph_node *n)
247 bool speculation_removed = false;
248 cgraph_edge *next;
250 for (cgraph_edge *e = n->callees; e; e = next)
252 next = e->next_callee;
253 if (e->speculative && !speculation_useful_p (e, true))
255 e->resolve_speculation (NULL);
256 speculation_removed = true;
258 else if (!e->inline_failed)
259 speculation_removed |= check_speculations (e->callee);
261 return speculation_removed;
264 /* Mark all call graph edges coming out of NODE and all nodes that have been
265 inlined to it as in_polymorphic_cdtor. */
267 static void
268 mark_all_inlined_calls_cdtor (cgraph_node *node)
270 for (cgraph_edge *cs = node->callees; cs; cs = cs->next_callee)
272 cs->in_polymorphic_cdtor = true;
273 if (!cs->inline_failed)
274 mark_all_inlined_calls_cdtor (cs->callee);
276 for (cgraph_edge *cs = node->indirect_calls; cs; cs = cs->next_callee)
277 cs->in_polymorphic_cdtor = true;
281 /* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL
282 specify whether profile of original function should be updated. If any new
283 indirect edges are discovered in the process, add them to NEW_EDGES, unless
284 it is NULL. If UPDATE_OVERALL_SUMMARY is false, do not bother to recompute overall
285 size of caller after inlining. Caller is required to eventually do it via
286 inline_update_overall_summary.
287 If callee_removed is non-NULL, set it to true if we removed callee node.
289 Return true iff any new callgraph edges were discovered as a
290 result of inlining. */
292 bool
293 inline_call (struct cgraph_edge *e, bool update_original,
294 vec<cgraph_edge *> *new_edges,
295 int *overall_size, bool update_overall_summary,
296 bool *callee_removed)
298 int old_size = 0, new_size = 0;
299 struct cgraph_node *to = NULL;
300 struct cgraph_edge *curr = e;
301 struct cgraph_node *callee = e->callee->ultimate_alias_target ();
302 bool new_edges_found = false;
304 int estimated_growth = 0;
305 if (! update_overall_summary)
306 estimated_growth = estimate_edge_growth (e);
307 /* This is used only for assert bellow. */
308 #if 0
309 bool predicated = inline_edge_summary (e)->predicate != NULL;
310 #endif
312 /* Don't inline inlined edges. */
313 gcc_assert (e->inline_failed);
314 /* Don't even think of inlining inline clone. */
315 gcc_assert (!callee->global.inlined_to);
317 e->inline_failed = CIF_OK;
318 DECL_POSSIBLY_INLINED (callee->decl) = true;
320 to = e->caller;
321 if (to->global.inlined_to)
322 to = to->global.inlined_to;
324 if (DECL_FUNCTION_PERSONALITY (callee->decl))
325 DECL_FUNCTION_PERSONALITY (to->decl)
326 = DECL_FUNCTION_PERSONALITY (callee->decl);
327 if (!opt_for_fn (callee->decl, flag_strict_aliasing)
328 && opt_for_fn (to->decl, flag_strict_aliasing))
330 struct gcc_options opts = global_options;
332 cl_optimization_restore (&opts, opts_for_fn (to->decl));
333 opts.x_flag_strict_aliasing = false;
334 if (dump_file)
335 fprintf (dump_file, "Dropping flag_strict_aliasing on %s:%i\n",
336 to->name (), to->order);
337 build_optimization_node (&opts);
338 DECL_FUNCTION_SPECIFIC_OPTIMIZATION (to->decl)
339 = build_optimization_node (&opts);
341 inline_summary *caller_info = inline_summaries->get (to);
342 inline_summary *callee_info = inline_summaries->get (callee);
343 if (!caller_info->fp_expressions && callee_info->fp_expressions)
345 caller_info->fp_expressions = true;
346 if (opt_for_fn (callee->decl, flag_rounding_math)
347 != opt_for_fn (to->decl, flag_rounding_math)
348 || opt_for_fn (callee->decl, flag_trapping_math)
349 != opt_for_fn (to->decl, flag_trapping_math)
350 || opt_for_fn (callee->decl, flag_unsafe_math_optimizations)
351 != opt_for_fn (to->decl, flag_unsafe_math_optimizations)
352 || opt_for_fn (callee->decl, flag_finite_math_only)
353 != opt_for_fn (to->decl, flag_finite_math_only)
354 || opt_for_fn (callee->decl, flag_signaling_nans)
355 != opt_for_fn (to->decl, flag_signaling_nans)
356 || opt_for_fn (callee->decl, flag_cx_limited_range)
357 != opt_for_fn (to->decl, flag_cx_limited_range)
358 || opt_for_fn (callee->decl, flag_signed_zeros)
359 != opt_for_fn (to->decl, flag_signed_zeros)
360 || opt_for_fn (callee->decl, flag_associative_math)
361 != opt_for_fn (to->decl, flag_associative_math)
362 || opt_for_fn (callee->decl, flag_reciprocal_math)
363 != opt_for_fn (to->decl, flag_reciprocal_math)
364 || opt_for_fn (callee->decl, flag_errno_math)
365 != opt_for_fn (to->decl, flag_errno_math))
367 struct gcc_options opts = global_options;
369 cl_optimization_restore (&opts, opts_for_fn (to->decl));
370 opts.x_flag_rounding_math
371 = opt_for_fn (callee->decl, flag_rounding_math);
372 opts.x_flag_trapping_math
373 = opt_for_fn (callee->decl, flag_trapping_math);
374 opts.x_flag_unsafe_math_optimizations
375 = opt_for_fn (callee->decl, flag_unsafe_math_optimizations);
376 opts.x_flag_finite_math_only
377 = opt_for_fn (callee->decl, flag_finite_math_only);
378 opts.x_flag_signaling_nans
379 = opt_for_fn (callee->decl, flag_signaling_nans);
380 opts.x_flag_cx_limited_range
381 = opt_for_fn (callee->decl, flag_cx_limited_range);
382 opts.x_flag_signed_zeros
383 = opt_for_fn (callee->decl, flag_signed_zeros);
384 opts.x_flag_associative_math
385 = opt_for_fn (callee->decl, flag_associative_math);
386 opts.x_flag_reciprocal_math
387 = opt_for_fn (callee->decl, flag_reciprocal_math);
388 opts.x_flag_errno_math
389 = opt_for_fn (callee->decl, flag_errno_math);
390 if (dump_file)
391 fprintf (dump_file, "Copying FP flags from %s:%i to %s:%i\n",
392 callee->name (), callee->order, to->name (), to->order);
393 build_optimization_node (&opts);
394 DECL_FUNCTION_SPECIFIC_OPTIMIZATION (to->decl)
395 = build_optimization_node (&opts);
399 /* If aliases are involved, redirect edge to the actual destination and
400 possibly remove the aliases. */
401 if (e->callee != callee)
403 struct cgraph_node *alias = e->callee, *next_alias;
404 e->redirect_callee (callee);
405 while (alias && alias != callee)
407 if (!alias->callers
408 && can_remove_node_now_p (alias,
409 !e->next_caller && !e->prev_caller ? e : NULL))
411 next_alias = alias->get_alias_target ();
412 alias->remove ();
413 if (callee_removed)
414 *callee_removed = true;
415 alias = next_alias;
417 else
418 break;
422 clone_inlined_nodes (e, true, update_original, overall_size, e->frequency);
424 gcc_assert (curr->callee->global.inlined_to == to);
426 old_size = inline_summaries->get (to)->size;
427 inline_merge_summary (e);
428 if (e->in_polymorphic_cdtor)
429 mark_all_inlined_calls_cdtor (e->callee);
430 if (opt_for_fn (e->caller->decl, optimize))
431 new_edges_found = ipa_propagate_indirect_call_infos (curr, new_edges);
432 check_speculations (e->callee);
433 if (update_overall_summary)
434 inline_update_overall_summary (to);
435 else
436 /* Update self size by the estimate so overall function growth limits
437 work for further inlining into this function. Before inlining
438 the function we inlined to again we expect the caller to update
439 the overall summary. */
440 inline_summaries->get (to)->size += estimated_growth;
441 new_size = inline_summaries->get (to)->size;
443 if (callee->calls_comdat_local)
444 to->calls_comdat_local = true;
445 else if (to->calls_comdat_local && callee->comdat_local_p ())
447 struct cgraph_edge *se = to->callees;
448 for (; se; se = se->next_callee)
449 if (se->inline_failed && se->callee->comdat_local_p ())
450 break;
451 if (se == NULL)
452 to->calls_comdat_local = false;
455 /* FIXME: This assert suffers from roundoff errors, disable it for GCC 5
456 and revisit it after conversion to sreals in GCC 6.
457 See PR 65654. */
458 #if 0
459 /* Verify that estimated growth match real growth. Allow off-by-one
460 error due to INLINE_SIZE_SCALE roudoff errors. */
461 gcc_assert (!update_overall_summary || !overall_size || new_edges_found
462 || abs (estimated_growth - (new_size - old_size)) <= 1
463 || speculation_removed
464 /* FIXME: a hack. Edges with false predicate are accounted
465 wrong, we should remove them from callgraph. */
466 || predicated);
467 #endif
469 /* Account the change of overall unit size; external functions will be
470 removed and are thus not accounted. */
471 if (overall_size && inline_account_function_p (to))
472 *overall_size += new_size - old_size;
473 ncalls_inlined++;
475 /* This must happen after inline_merge_summary that rely on jump
476 functions of callee to not be updated. */
477 return new_edges_found;
481 /* Copy function body of NODE and redirect all inline clones to it.
482 This is done before inline plan is applied to NODE when there are
483 still some inline clones if it.
485 This is necessary because inline decisions are not really transitive
486 and the other inline clones may have different bodies. */
488 static struct cgraph_node *
489 save_inline_function_body (struct cgraph_node *node)
491 struct cgraph_node *first_clone, *n;
493 if (dump_file)
494 fprintf (dump_file, "\nSaving body of %s for later reuse\n",
495 node->name ());
497 gcc_assert (node == cgraph_node::get (node->decl));
499 /* first_clone will be turned into real function. */
500 first_clone = node->clones;
501 first_clone->decl = copy_node (node->decl);
502 first_clone->decl->decl_with_vis.symtab_node = first_clone;
503 gcc_assert (first_clone == cgraph_node::get (first_clone->decl));
505 /* Now reshape the clone tree, so all other clones descends from
506 first_clone. */
507 if (first_clone->next_sibling_clone)
509 for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
510 n->clone_of = first_clone;
511 n->clone_of = first_clone;
512 n->next_sibling_clone = first_clone->clones;
513 if (first_clone->clones)
514 first_clone->clones->prev_sibling_clone = n;
515 first_clone->clones = first_clone->next_sibling_clone;
516 first_clone->next_sibling_clone->prev_sibling_clone = NULL;
517 first_clone->next_sibling_clone = NULL;
518 gcc_assert (!first_clone->prev_sibling_clone);
520 first_clone->clone_of = NULL;
522 /* Now node in question has no clones. */
523 node->clones = NULL;
525 /* Inline clones share decl with the function they are cloned
526 from. Walk the whole clone tree and redirect them all to the
527 new decl. */
528 if (first_clone->clones)
529 for (n = first_clone->clones; n != first_clone;)
531 gcc_assert (n->decl == node->decl);
532 n->decl = first_clone->decl;
533 if (n->clones)
534 n = n->clones;
535 else if (n->next_sibling_clone)
536 n = n->next_sibling_clone;
537 else
539 while (n != first_clone && !n->next_sibling_clone)
540 n = n->clone_of;
541 if (n != first_clone)
542 n = n->next_sibling_clone;
546 /* Copy the OLD_VERSION_NODE function tree to the new version. */
547 tree_function_versioning (node->decl, first_clone->decl,
548 NULL, true, NULL, false,
549 NULL, NULL);
551 /* The function will be short lived and removed after we inline all the clones,
552 but make it internal so we won't confuse ourself. */
553 DECL_EXTERNAL (first_clone->decl) = 0;
554 TREE_PUBLIC (first_clone->decl) = 0;
555 DECL_COMDAT (first_clone->decl) = 0;
556 first_clone->ipa_transforms_to_apply.release ();
558 /* When doing recursive inlining, the clone may become unnecessary.
559 This is possible i.e. in the case when the recursive function is proved to be
560 non-throwing and the recursion happens only in the EH landing pad.
561 We can not remove the clone until we are done with saving the body.
562 Remove it now. */
563 if (!first_clone->callers)
565 first_clone->remove_symbol_and_inline_clones ();
566 first_clone = NULL;
568 else if (flag_checking)
569 first_clone->verify ();
571 return first_clone;
574 /* Return true when function body of DECL still needs to be kept around
575 for later re-use. */
576 static bool
577 preserve_function_body_p (struct cgraph_node *node)
579 gcc_assert (symtab->global_info_ready);
580 gcc_assert (!node->alias && !node->thunk.thunk_p);
582 /* Look if there is any clone around. */
583 if (node->clones)
584 return true;
585 return false;
588 /* Apply inline plan to function. */
590 unsigned int
591 inline_transform (struct cgraph_node *node)
593 unsigned int todo = 0;
594 struct cgraph_edge *e, *next;
595 bool has_inline = false;
597 /* FIXME: Currently the pass manager is adding inline transform more than
598 once to some clones. This needs revisiting after WPA cleanups. */
599 if (cfun->after_inlining)
600 return 0;
602 /* We might need the body of this function so that we can expand
603 it inline somewhere else. */
604 if (preserve_function_body_p (node))
605 save_inline_function_body (node);
607 for (e = node->callees; e; e = next)
609 if (!e->inline_failed)
610 has_inline = true;
611 next = e->next_callee;
612 e->redirect_call_stmt_to_callee ();
614 node->remove_all_references ();
616 timevar_push (TV_INTEGRATION);
617 if (node->callees && (opt_for_fn (node->decl, optimize) || has_inline))
618 todo = optimize_inline_calls (current_function_decl);
619 timevar_pop (TV_INTEGRATION);
621 cfun->always_inline_functions_inlined = true;
622 cfun->after_inlining = true;
623 todo |= execute_fixup_cfg ();
625 if (!(todo & TODO_update_ssa_any))
626 /* Redirecting edges might lead to a need for vops to be recomputed. */
627 todo |= TODO_update_ssa_only_virtuals;
629 return todo;