1 /* Callgraph clones
2 Copyright (C) 2003-2016 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 3, 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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 /* This module provide facilities for clonning functions. I.e. creating
22 new functions based on existing functions with simple modifications,
23 such as replacement of parameters.
24
25 To allow whole program optimization without actual presence of function
26 bodies, an additional infrastructure is provided for so-called virtual
27 clones
28
29 A virtual clone in the callgraph is a function that has no
30 associated body, just a description of how to create its body based
31 on a different function (which itself may be a virtual clone).
32
33 The description of function modifications includes adjustments to
34 the function's signature (which allows, for example, removing or
35 adding function arguments), substitutions to perform on the
36 function body, and, for inlined functions, a pointer to the
37 function that it will be inlined into.
38
39 It is also possible to redirect any edge of the callgraph from a
40 function to its virtual clone. This implies updating of the call
41 site to adjust for the new function signature.
42
43 Most of the transformations performed by inter-procedural
44 optimizations can be represented via virtual clones. For
45 instance, a constant propagation pass can produce a virtual clone
46 of the function which replaces one of its arguments by a
47 constant. The inliner can represent its decisions by producing a
48 clone of a function whose body will be later integrated into
49 a given function.
50
51 Using virtual clones, the program can be easily updated
52 during the Execute stage, solving most of pass interactions
53 problems that would otherwise occur during Transform.
54
55 Virtual clones are later materialized in the LTRANS stage and
56 turned into real functions. Passes executed after the virtual
57 clone were introduced also perform their Transform stage
58 on new functions, so for a pass there is no significant
59 difference between operating on a real function or a virtual
60 clone introduced before its Execute stage.
61
62 Optimization passes then work on virtual clones introduced before
63 their Execute stage as if they were real functions. The
64 only difference is that clones are not visible during the
65 Generate Summary stage. */
66
67 #include "config.h"
68 #include "system.h"
69 #include "coretypes.h"
70 #include "backend.h"
71 #include "target.h"
72 #include "rtl.h"
73 #include "tree.h"
74 #include "gimple.h"
75 #include "stringpool.h"
76 #include "cgraph.h"
77 #include "lto-streamer.h"
78 #include "tree-eh.h"
79 #include "tree-cfg.h"
80 #include "tree-inline.h"
81 #include "tree-dump.h"
82 #include "gimple-pretty-print.h"
83
84 /* Create clone of edge in the node N represented by CALL_EXPR
85 the callgraph. */
86
87 cgraph_edge *
clone(cgraph_node * n,gcall * call_stmt,unsigned stmt_uid,gcov_type count_scale,int freq_scale,bool update_original)88 cgraph_edge::clone (cgraph_node *n, gcall *call_stmt, unsigned stmt_uid,
89 gcov_type count_scale, int freq_scale, bool update_original)
90 {
91 cgraph_edge *new_edge;
92 gcov_type gcov_count = apply_probability (count, count_scale);
93 gcov_type freq;
94
95 /* We do not want to ignore loop nest after frequency drops to 0. */
96 if (!freq_scale)
97 freq_scale = 1;
98 freq = frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
99 if (freq > CGRAPH_FREQ_MAX)
100 freq = CGRAPH_FREQ_MAX;
101
102 if (indirect_unknown_callee)
103 {
104 tree decl;
105
106 if (call_stmt && (decl = gimple_call_fndecl (call_stmt))
107 /* When the call is speculative, we need to resolve it
108 via cgraph_resolve_speculation and not here. */
109 && !speculative)
110 {
111 cgraph_node *callee = cgraph_node::get (decl);
112 gcc_checking_assert (callee);
113 new_edge = n->create_edge (callee, call_stmt, gcov_count, freq);
114 }
115 else
116 {
117 new_edge = n->create_indirect_edge (call_stmt,
118 indirect_info->ecf_flags,
119 count, freq, false);
120 *new_edge->indirect_info = *indirect_info;
121 }
122 }
123 else
124 {
125 new_edge = n->create_edge (callee, call_stmt, gcov_count, freq);
126 if (indirect_info)
127 {
128 new_edge->indirect_info
129 = ggc_cleared_alloc<cgraph_indirect_call_info> ();
130 *new_edge->indirect_info = *indirect_info;
131 }
132 }
133
134 new_edge->inline_failed = inline_failed;
135 new_edge->indirect_inlining_edge = indirect_inlining_edge;
136 new_edge->lto_stmt_uid = stmt_uid;
137 /* Clone flags that depend on call_stmt availability manually. */
138 new_edge->can_throw_external = can_throw_external;
139 new_edge->call_stmt_cannot_inline_p = call_stmt_cannot_inline_p;
140 new_edge->speculative = speculative;
141 new_edge->in_polymorphic_cdtor = in_polymorphic_cdtor;
142 if (update_original)
143 {
144 count -= new_edge->count;
145 if (count < 0)
146 count = 0;
147 }
148 symtab->call_edge_duplication_hooks (this, new_edge);
149 return new_edge;
150 }
151
152 /* Build variant of function type ORIG_TYPE skipping ARGS_TO_SKIP and the
153 return value if SKIP_RETURN is true. */
154
155 tree
cgraph_build_function_type_skip_args(tree orig_type,bitmap args_to_skip,bool skip_return)156 cgraph_build_function_type_skip_args (tree orig_type, bitmap args_to_skip,
157 bool skip_return)
158 {
159 tree new_type = NULL;
160 tree args, new_args = NULL;
161 tree new_reversed;
162 int i = 0;
163
164 for (args = TYPE_ARG_TYPES (orig_type); args && args != void_list_node;
165 args = TREE_CHAIN (args), i++)
166 if (!args_to_skip || !bitmap_bit_p (args_to_skip, i))
167 new_args = tree_cons (NULL_TREE, TREE_VALUE (args), new_args);
168
169 new_reversed = nreverse (new_args);
170 if (args)
171 {
172 if (new_reversed)
173 TREE_CHAIN (new_args) = void_list_node;
174 else
175 new_reversed = void_list_node;
176 }
177
178 /* Use copy_node to preserve as much as possible from original type
179 (debug info, attribute lists etc.)
180 Exception is METHOD_TYPEs must have THIS argument.
181 When we are asked to remove it, we need to build new FUNCTION_TYPE
182 instead. */
183 if (TREE_CODE (orig_type) != METHOD_TYPE
184 || !args_to_skip
185 || !bitmap_bit_p (args_to_skip, 0))
186 {
187 new_type = build_distinct_type_copy (orig_type);
188 TYPE_ARG_TYPES (new_type) = new_reversed;
189 }
190 else
191 {
192 new_type
193 = build_distinct_type_copy (build_function_type (TREE_TYPE (orig_type),
194 new_reversed));
195 TYPE_CONTEXT (new_type) = TYPE_CONTEXT (orig_type);
196 }
197
198 if (skip_return)
199 TREE_TYPE (new_type) = void_type_node;
200
201 return new_type;
202 }
203
204 /* Build variant of function decl ORIG_DECL skipping ARGS_TO_SKIP and the
205 return value if SKIP_RETURN is true.
206
207 Arguments from DECL_ARGUMENTS list can't be removed now, since they are
208 linked by TREE_CHAIN directly. The caller is responsible for eliminating
209 them when they are being duplicated (i.e. copy_arguments_for_versioning). */
210
211 static tree
build_function_decl_skip_args(tree orig_decl,bitmap args_to_skip,bool skip_return)212 build_function_decl_skip_args (tree orig_decl, bitmap args_to_skip,
213 bool skip_return)
214 {
215 tree new_decl = copy_node (orig_decl);
216 tree new_type;
217
218 new_type = TREE_TYPE (orig_decl);
219 if (prototype_p (new_type)
220 || (skip_return && !VOID_TYPE_P (TREE_TYPE (new_type))))
221 new_type
222 = cgraph_build_function_type_skip_args (new_type, args_to_skip,
223 skip_return);
224 TREE_TYPE (new_decl) = new_type;
225
226 /* For declarations setting DECL_VINDEX (i.e. methods)
227 we expect first argument to be THIS pointer. */
228 if (args_to_skip && bitmap_bit_p (args_to_skip, 0))
229 DECL_VINDEX (new_decl) = NULL_TREE;
230
231 /* When signature changes, we need to clear builtin info. */
232 if (DECL_BUILT_IN (new_decl)
233 && args_to_skip
234 && !bitmap_empty_p (args_to_skip))
235 {
236 DECL_BUILT_IN_CLASS (new_decl) = NOT_BUILT_IN;
237 DECL_FUNCTION_CODE (new_decl) = (enum built_in_function) 0;
238 }
239 /* The FE might have information and assumptions about the other
240 arguments. */
241 DECL_LANG_SPECIFIC (new_decl) = NULL;
242 return new_decl;
243 }
244
245 /* Set flags of NEW_NODE and its decl. NEW_NODE is a newly created private
246 clone or its thunk. */
247
248 static void
set_new_clone_decl_and_node_flags(cgraph_node * new_node)249 set_new_clone_decl_and_node_flags (cgraph_node *new_node)
250 {
251 DECL_EXTERNAL (new_node->decl) = 0;
252 TREE_PUBLIC (new_node->decl) = 0;
253 DECL_COMDAT (new_node->decl) = 0;
254 DECL_WEAK (new_node->decl) = 0;
255 DECL_VIRTUAL_P (new_node->decl) = 0;
256 DECL_STATIC_CONSTRUCTOR (new_node->decl) = 0;
257 DECL_STATIC_DESTRUCTOR (new_node->decl) = 0;
258
259 new_node->externally_visible = 0;
260 new_node->local.local = 1;
261 new_node->lowered = true;
262 }
263
264 /* Duplicate thunk THUNK if necessary but make it to refer to NODE.
265 ARGS_TO_SKIP, if non-NULL, determines which parameters should be omitted.
266 Function can return NODE if no thunk is necessary, which can happen when
267 thunk is this_adjusting but we are removing this parameter. */
268
269 static cgraph_node *
duplicate_thunk_for_node(cgraph_node * thunk,cgraph_node * node)270 duplicate_thunk_for_node (cgraph_node *thunk, cgraph_node *node)
271 {
272 cgraph_node *new_thunk, *thunk_of;
273 thunk_of = thunk->callees->callee->ultimate_alias_target ();
274
275 if (thunk_of->thunk.thunk_p)
276 node = duplicate_thunk_for_node (thunk_of, node);
277
278 if (!DECL_ARGUMENTS (thunk->decl))
279 thunk->get_untransformed_body ();
280
281 cgraph_edge *cs;
282 for (cs = node->callers; cs; cs = cs->next_caller)
283 if (cs->caller->thunk.thunk_p
284 && cs->caller->thunk.this_adjusting == thunk->thunk.this_adjusting
285 && cs->caller->thunk.fixed_offset == thunk->thunk.fixed_offset
286 && cs->caller->thunk.virtual_offset_p == thunk->thunk.virtual_offset_p
287 && cs->caller->thunk.virtual_value == thunk->thunk.virtual_value)
288 return cs->caller;
289
290 tree new_decl;
291 if (!node->clone.args_to_skip)
292 new_decl = copy_node (thunk->decl);
293 else
294 {
295 /* We do not need to duplicate this_adjusting thunks if we have removed
296 this. */
297 if (thunk->thunk.this_adjusting
298 && bitmap_bit_p (node->clone.args_to_skip, 0))
299 return node;
300
301 new_decl = build_function_decl_skip_args (thunk->decl,
302 node->clone.args_to_skip,
303 false);
304 }
305
306 tree *link = &DECL_ARGUMENTS (new_decl);
307 int i = 0;
308 for (tree pd = DECL_ARGUMENTS (thunk->decl); pd; pd = DECL_CHAIN (pd), i++)
309 {
310 if (!node->clone.args_to_skip
311 || !bitmap_bit_p (node->clone.args_to_skip, i))
312 {
313 tree nd = copy_node (pd);
314 DECL_CONTEXT (nd) = new_decl;
315 *link = nd;
316 link = &DECL_CHAIN (nd);
317 }
318 }
319 *link = NULL_TREE;
320
321 gcc_checking_assert (!DECL_STRUCT_FUNCTION (new_decl));
322 gcc_checking_assert (!DECL_INITIAL (new_decl));
323 gcc_checking_assert (!DECL_RESULT (new_decl));
324 gcc_checking_assert (!DECL_RTL_SET_P (new_decl));
325
326 DECL_NAME (new_decl) = clone_function_name (thunk->decl, "artificial_thunk");
327 SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
328
329 new_thunk = cgraph_node::create (new_decl);
330 set_new_clone_decl_and_node_flags (new_thunk);
331 new_thunk->definition = true;
332 new_thunk->local.can_change_signature = node->local.can_change_signature;
333 new_thunk->thunk = thunk->thunk;
334 new_thunk->unique_name = in_lto_p;
335 new_thunk->former_clone_of = thunk->decl;
336 new_thunk->clone.args_to_skip = node->clone.args_to_skip;
337 new_thunk->clone.combined_args_to_skip = node->clone.combined_args_to_skip;
338
339 cgraph_edge *e = new_thunk->create_edge (node, NULL, 0,
340 CGRAPH_FREQ_BASE);
341 e->call_stmt_cannot_inline_p = true;
342 symtab->call_edge_duplication_hooks (thunk->callees, e);
343 symtab->call_cgraph_duplication_hooks (thunk, new_thunk);
344 return new_thunk;
345 }
346
347 /* If E does not lead to a thunk, simply redirect it to N. Otherwise create
348 one or more equivalent thunks for N and redirect E to the first in the
349 chain. Note that it is then necessary to call
350 n->expand_all_artificial_thunks once all callers are redirected. */
351
352 void
redirect_callee_duplicating_thunks(cgraph_node * n)353 cgraph_edge::redirect_callee_duplicating_thunks (cgraph_node *n)
354 {
355 cgraph_node *orig_to = callee->ultimate_alias_target ();
356 if (orig_to->thunk.thunk_p)
357 n = duplicate_thunk_for_node (orig_to, n);
358
359 redirect_callee (n);
360 }
361
362 /* Call expand_thunk on all callers that are thunks and if analyze those nodes
363 that were expanded. */
364
365 void
expand_all_artificial_thunks()366 cgraph_node::expand_all_artificial_thunks ()
367 {
368 cgraph_edge *e;
369 for (e = callers; e;)
370 if (e->caller->thunk.thunk_p)
371 {
372 cgraph_node *thunk = e->caller;
373
374 e = e->next_caller;
375 if (thunk->expand_thunk (false, false))
376 {
377 thunk->thunk.thunk_p = false;
378 thunk->analyze ();
379 }
380 thunk->expand_all_artificial_thunks ();
381 }
382 else
383 e = e->next_caller;
384 }
385
386 /* Create node representing clone of N executed COUNT times. Decrease
387 the execution counts from original node too.
388 The new clone will have decl set to DECL that may or may not be the same
389 as decl of N.
390
391 When UPDATE_ORIGINAL is true, the counts are subtracted from the original
392 function's profile to reflect the fact that part of execution is handled
393 by node.
394 When CALL_DUPLICATOIN_HOOK is true, the ipa passes are acknowledged about
395 the new clone. Otherwise the caller is responsible for doing so later.
396
397 If the new node is being inlined into another one, NEW_INLINED_TO should be
398 the outline function the new one is (even indirectly) inlined to. All hooks
399 will see this in node's global.inlined_to, when invoked. Can be NULL if the
400 node is not inlined. */
401
402 cgraph_node *
create_clone(tree new_decl,gcov_type gcov_count,int freq,bool update_original,vec<cgraph_edge * > redirect_callers,bool call_duplication_hook,cgraph_node * new_inlined_to,bitmap args_to_skip)403 cgraph_node::create_clone (tree new_decl, gcov_type gcov_count, int freq,
404 bool update_original,
405 vec<cgraph_edge *> redirect_callers,
406 bool call_duplication_hook,
407 cgraph_node *new_inlined_to,
408 bitmap args_to_skip)
409 {
410 cgraph_node *new_node = symtab->create_empty ();
411 cgraph_edge *e;
412 gcov_type count_scale;
413 unsigned i;
414
415 new_node->decl = new_decl;
416 new_node->register_symbol ();
417 new_node->origin = origin;
418 new_node->lto_file_data = lto_file_data;
419 if (new_node->origin)
420 {
421 new_node->next_nested = new_node->origin->nested;
422 new_node->origin->nested = new_node;
423 }
424 new_node->analyzed = analyzed;
425 new_node->definition = definition;
426 new_node->local = local;
427 new_node->externally_visible = false;
428 new_node->no_reorder = no_reorder;
429 new_node->local.local = true;
430 new_node->global = global;
431 new_node->global.inlined_to = new_inlined_to;
432 new_node->rtl = rtl;
433 new_node->count = count;
434 new_node->frequency = frequency;
435 new_node->tp_first_run = tp_first_run;
436 new_node->tm_clone = tm_clone;
437 new_node->icf_merged = icf_merged;
438 new_node->merged_comdat = merged_comdat;
439
440 new_node->clone.tree_map = NULL;
441 new_node->clone.args_to_skip = args_to_skip;
442 new_node->split_part = split_part;
443 if (!args_to_skip)
444 new_node->clone.combined_args_to_skip = clone.combined_args_to_skip;
445 else if (clone.combined_args_to_skip)
446 {
447 new_node->clone.combined_args_to_skip = BITMAP_GGC_ALLOC ();
448 bitmap_ior (new_node->clone.combined_args_to_skip,
449 clone.combined_args_to_skip, args_to_skip);
450 }
451 else
452 new_node->clone.combined_args_to_skip = args_to_skip;
453
454 if (count)
455 {
456 if (new_node->count > count)
457 count_scale = REG_BR_PROB_BASE;
458 else
459 count_scale = GCOV_COMPUTE_SCALE (new_node->count, count);
460 }
461 else
462 count_scale = 0;
463 if (update_original)
464 {
465 count -= gcov_count;
466 if (count < 0)
467 count = 0;
468 }
469
470 FOR_EACH_VEC_ELT (redirect_callers, i, e)
471 {
472 /* Redirect calls to the old version node to point to its new
473 version. The only exception is when the edge was proved to
474 be unreachable during the clonning procedure. */
475 if (!e->callee
476 || DECL_BUILT_IN_CLASS (e->callee->decl) != BUILT_IN_NORMAL
477 || DECL_FUNCTION_CODE (e->callee->decl) != BUILT_IN_UNREACHABLE)
478 e->redirect_callee_duplicating_thunks (new_node);
479 }
480 new_node->expand_all_artificial_thunks ();
481
482 for (e = callees;e; e=e->next_callee)
483 e->clone (new_node, e->call_stmt, e->lto_stmt_uid, count_scale,
484 freq, update_original);
485
486 for (e = indirect_calls; e; e = e->next_callee)
487 e->clone (new_node, e->call_stmt, e->lto_stmt_uid,
488 count_scale, freq, update_original);
489 new_node->clone_references (this);
490
491 new_node->next_sibling_clone = clones;
492 if (clones)
493 clones->prev_sibling_clone = new_node;
494 clones = new_node;
495 new_node->clone_of = this;
496
497 if (call_duplication_hook)
498 symtab->call_cgraph_duplication_hooks (this, new_node);
499 return new_node;
500 }
501
502 static GTY(()) unsigned int clone_fn_id_num;
503
504 /* Return a new assembler name for a clone with SUFFIX of a decl named
505 NAME. */
506
507 tree
clone_function_name_1(const char * name,const char * suffix)508 clone_function_name_1 (const char *name, const char *suffix)
509 {
510 size_t len = strlen (name);
511 char *tmp_name, *prefix;
512
513 prefix = XALLOCAVEC (char, len + strlen (suffix) + 2);
514 memcpy (prefix, name, len);
515 strcpy (prefix + len + 1, suffix);
516 prefix[len] = symbol_table::symbol_suffix_separator ();
517 ASM_FORMAT_PRIVATE_NAME (tmp_name, prefix, clone_fn_id_num++);
518 return get_identifier (tmp_name);
519 }
520
521 /* Return a new assembler name for a clone of DECL with SUFFIX. */
522
523 tree
clone_function_name(tree decl,const char * suffix)524 clone_function_name (tree decl, const char *suffix)
525 {
526 tree name = DECL_ASSEMBLER_NAME (decl);
527 return clone_function_name_1 (IDENTIFIER_POINTER (name), suffix);
528 }
529
530
531 /* Create callgraph node clone with new declaration. The actual body will
532 be copied later at compilation stage.
533
534 TODO: after merging in ipa-sra use function call notes instead of args_to_skip
535 bitmap interface.
536 */
537 cgraph_node *
create_virtual_clone(vec<cgraph_edge * > redirect_callers,vec<ipa_replace_map *,va_gc> * tree_map,bitmap args_to_skip,const char * suffix)538 cgraph_node::create_virtual_clone (vec<cgraph_edge *> redirect_callers,
539 vec<ipa_replace_map *, va_gc> *tree_map,
540 bitmap args_to_skip, const char * suffix)
541 {
542 tree old_decl = decl;
543 cgraph_node *new_node = NULL;
544 tree new_decl;
545 size_t len, i;
546 ipa_replace_map *map;
547 char *name;
548
549 gcc_checking_assert (local.versionable);
550 gcc_assert (local.can_change_signature || !args_to_skip);
551
552 /* Make a new FUNCTION_DECL tree node */
553 if (!args_to_skip)
554 new_decl = copy_node (old_decl);
555 else
556 new_decl = build_function_decl_skip_args (old_decl, args_to_skip, false);
557
558 /* These pointers represent function body and will be populated only when clone
559 is materialized. */
560 gcc_assert (new_decl != old_decl);
561 DECL_STRUCT_FUNCTION (new_decl) = NULL;
562 DECL_ARGUMENTS (new_decl) = NULL;
563 DECL_INITIAL (new_decl) = NULL;
564 DECL_RESULT (new_decl) = NULL;
565 /* We can not do DECL_RESULT (new_decl) = NULL; here because of LTO partitioning
566 sometimes storing only clone decl instead of original. */
567
568 /* Generate a new name for the new version. */
569 len = IDENTIFIER_LENGTH (DECL_NAME (old_decl));
570 name = XALLOCAVEC (char, len + strlen (suffix) + 2);
571 memcpy (name, IDENTIFIER_POINTER (DECL_NAME (old_decl)), len);
572 strcpy (name + len + 1, suffix);
573 name[len] = '.';
574 DECL_NAME (new_decl) = get_identifier (name);
575 SET_DECL_ASSEMBLER_NAME (new_decl, clone_function_name (old_decl, suffix));
576 SET_DECL_RTL (new_decl, NULL);
577
578 new_node = create_clone (new_decl, count, CGRAPH_FREQ_BASE, false,
579 redirect_callers, false, NULL, args_to_skip);
580
581 /* Update the properties.
582 Make clone visible only within this translation unit. Make sure
583 that is not weak also.
584 ??? We cannot use COMDAT linkage because there is no
585 ABI support for this. */
586 set_new_clone_decl_and_node_flags (new_node);
587 new_node->clone.tree_map = tree_map;
588 if (!implicit_section)
589 new_node->set_section (get_section ());
590
591 /* Clones of global symbols or symbols with unique names are unique. */
592 if ((TREE_PUBLIC (old_decl)
593 && !DECL_EXTERNAL (old_decl)
594 && !DECL_WEAK (old_decl)
595 && !DECL_COMDAT (old_decl))
596 || in_lto_p)
597 new_node->unique_name = true;
598 FOR_EACH_VEC_SAFE_ELT (tree_map, i, map)
599 new_node->maybe_create_reference (map->new_tree, IPA_REF_ADDR, NULL);
600
601 if (ipa_transforms_to_apply.exists ())
602 new_node->ipa_transforms_to_apply
603 = ipa_transforms_to_apply.copy ();
604
605 symtab->call_cgraph_duplication_hooks (this, new_node);
606
607 return new_node;
608 }
609
610 /* callgraph node being removed from symbol table; see if its entry can be
611 replaced by other inline clone. */
612 cgraph_node *
find_replacement(void)613 cgraph_node::find_replacement (void)
614 {
615 cgraph_node *next_inline_clone, *replacement;
616
617 for (next_inline_clone = clones;
618 next_inline_clone
619 && next_inline_clone->decl != decl;
620 next_inline_clone = next_inline_clone->next_sibling_clone)
621 ;
622
623 /* If there is inline clone of the node being removed, we need
624 to put it into the position of removed node and reorganize all
625 other clones to be based on it. */
626 if (next_inline_clone)
627 {
628 cgraph_node *n;
629 cgraph_node *new_clones;
630
631 replacement = next_inline_clone;
632
633 /* Unlink inline clone from the list of clones of removed node. */
634 if (next_inline_clone->next_sibling_clone)
635 next_inline_clone->next_sibling_clone->prev_sibling_clone
636 = next_inline_clone->prev_sibling_clone;
637 if (next_inline_clone->prev_sibling_clone)
638 {
639 gcc_assert (clones != next_inline_clone);
640 next_inline_clone->prev_sibling_clone->next_sibling_clone
641 = next_inline_clone->next_sibling_clone;
642 }
643 else
644 {
645 gcc_assert (clones == next_inline_clone);
646 clones = next_inline_clone->next_sibling_clone;
647 }
648
649 new_clones = clones;
650 clones = NULL;
651
652 /* Copy clone info. */
653 next_inline_clone->clone = clone;
654
655 /* Now place it into clone tree at same level at NODE. */
656 next_inline_clone->clone_of = clone_of;
657 next_inline_clone->prev_sibling_clone = NULL;
658 next_inline_clone->next_sibling_clone = NULL;
659 if (clone_of)
660 {
661 if (clone_of->clones)
662 clone_of->clones->prev_sibling_clone = next_inline_clone;
663 next_inline_clone->next_sibling_clone = clone_of->clones;
664 clone_of->clones = next_inline_clone;
665 }
666
667 /* Merge the clone list. */
668 if (new_clones)
669 {
670 if (!next_inline_clone->clones)
671 next_inline_clone->clones = new_clones;
672 else
673 {
674 n = next_inline_clone->clones;
675 while (n->next_sibling_clone)
676 n = n->next_sibling_clone;
677 n->next_sibling_clone = new_clones;
678 new_clones->prev_sibling_clone = n;
679 }
680 }
681
682 /* Update clone_of pointers. */
683 n = new_clones;
684 while (n)
685 {
686 n->clone_of = next_inline_clone;
687 n = n->next_sibling_clone;
688 }
689 return replacement;
690 }
691 else
692 return NULL;
693 }
694
695 /* Like cgraph_set_call_stmt but walk the clone tree and update all
696 clones sharing the same function body.
697 When WHOLE_SPECULATIVE_EDGES is true, all three components of
698 speculative edge gets updated. Otherwise we update only direct
699 call. */
700
701 void
set_call_stmt_including_clones(gimple * old_stmt,gcall * new_stmt,bool update_speculative)702 cgraph_node::set_call_stmt_including_clones (gimple *old_stmt,
703 gcall *new_stmt,
704 bool update_speculative)
705 {
706 cgraph_node *node;
707 cgraph_edge *edge = get_edge (old_stmt);
708
709 if (edge)
710 edge->set_call_stmt (new_stmt, update_speculative);
711
712 node = clones;
713 if (node)
714 while (node != this)
715 {
716 cgraph_edge *edge = node->get_edge (old_stmt);
717 if (edge)
718 {
719 edge->set_call_stmt (new_stmt, update_speculative);
720 /* If UPDATE_SPECULATIVE is false, it means that we are turning
721 speculative call into a real code sequence. Update the
722 callgraph edges. */
723 if (edge->speculative && !update_speculative)
724 {
725 cgraph_edge *direct, *indirect;
726 ipa_ref *ref;
727
728 gcc_assert (!edge->indirect_unknown_callee);
729 edge->speculative_call_info (direct, indirect, ref);
730 direct->speculative = false;
731 indirect->speculative = false;
732 ref->speculative = false;
733 }
734 }
735 if (node->clones)
736 node = node->clones;
737 else if (node->next_sibling_clone)
738 node = node->next_sibling_clone;
739 else
740 {
741 while (node != this && !node->next_sibling_clone)
742 node = node->clone_of;
743 if (node != this)
744 node = node->next_sibling_clone;
745 }
746 }
747 }
748
749 /* Like cgraph_create_edge walk the clone tree and update all clones sharing
750 same function body. If clones already have edge for OLD_STMT; only
751 update the edge same way as cgraph_set_call_stmt_including_clones does.
752
753 TODO: COUNT and LOOP_DEPTH should be properly distributed based on relative
754 frequencies of the clones. */
755
756 void
create_edge_including_clones(cgraph_node * callee,gimple * old_stmt,gcall * stmt,gcov_type count,int freq,cgraph_inline_failed_t reason)757 cgraph_node::create_edge_including_clones (cgraph_node *callee,
758 gimple *old_stmt, gcall *stmt,
759 gcov_type count,
760 int freq,
761 cgraph_inline_failed_t reason)
762 {
763 cgraph_node *node;
764 cgraph_edge *edge;
765
766 if (!get_edge (stmt))
767 {
768 edge = create_edge (callee, stmt, count, freq);
769 edge->inline_failed = reason;
770 }
771
772 node = clones;
773 if (node)
774 while (node != this)
775 {
776 cgraph_edge *edge = node->get_edge (old_stmt);
777
778 /* It is possible that clones already contain the edge while
779 master didn't. Either we promoted indirect call into direct
780 call in the clone or we are processing clones of unreachable
781 master where edges has been removed. */
782 if (edge)
783 edge->set_call_stmt (stmt);
784 else if (! node->get_edge (stmt))
785 {
786 edge = node->create_edge (callee, stmt, count, freq);
787 edge->inline_failed = reason;
788 }
789
790 if (node->clones)
791 node = node->clones;
792 else if (node->next_sibling_clone)
793 node = node->next_sibling_clone;
794 else
795 {
796 while (node != this && !node->next_sibling_clone)
797 node = node->clone_of;
798 if (node != this)
799 node = node->next_sibling_clone;
800 }
801 }
802 }
803
804 /* Remove the node from cgraph and all inline clones inlined into it.
805 Skip however removal of FORBIDDEN_NODE and return true if it needs to be
806 removed. This allows to call the function from outer loop walking clone
807 tree. */
808
809 bool
remove_symbol_and_inline_clones(cgraph_node * forbidden_node)810 cgraph_node::remove_symbol_and_inline_clones (cgraph_node *forbidden_node)
811 {
812 cgraph_edge *e, *next;
813 bool found = false;
814
815 if (this == forbidden_node)
816 {
817 callers->remove ();
818 return true;
819 }
820 for (e = callees; e; e = next)
821 {
822 next = e->next_callee;
823 if (!e->inline_failed)
824 found |= e->callee->remove_symbol_and_inline_clones (forbidden_node);
825 }
826 remove ();
827 return found;
828 }
829
830 /* The edges representing the callers of the NEW_VERSION node were
831 fixed by cgraph_function_versioning (), now the call_expr in their
832 respective tree code should be updated to call the NEW_VERSION. */
833
834 static void
update_call_expr(cgraph_node * new_version)835 update_call_expr (cgraph_node *new_version)
836 {
837 cgraph_edge *e;
838
839 gcc_assert (new_version);
840
841 /* Update the call expr on the edges to call the new version. */
842 for (e = new_version->callers; e; e = e->next_caller)
843 {
844 function *inner_function = DECL_STRUCT_FUNCTION (e->caller->decl);
845 gimple_call_set_fndecl (e->call_stmt, new_version->decl);
846 maybe_clean_eh_stmt_fn (inner_function, e->call_stmt);
847 }
848 }
849
850
851 /* Create a new cgraph node which is the new version of
852 callgraph node. REDIRECT_CALLERS holds the callers
853 edges which should be redirected to point to
854 NEW_VERSION. ALL the callees edges of the node
855 are cloned to the new version node. Return the new
856 version node.
857
858 If non-NULL BLOCK_TO_COPY determine what basic blocks
859 was copied to prevent duplications of calls that are dead
860 in the clone. */
861
862 cgraph_node *
create_version_clone(tree new_decl,vec<cgraph_edge * > redirect_callers,bitmap bbs_to_copy)863 cgraph_node::create_version_clone (tree new_decl,
864 vec<cgraph_edge *> redirect_callers,
865 bitmap bbs_to_copy)
866 {
867 cgraph_node *new_version;
868 cgraph_edge *e;
869 unsigned i;
870
871 new_version = cgraph_node::create (new_decl);
872
873 new_version->analyzed = analyzed;
874 new_version->definition = definition;
875 new_version->local = local;
876 new_version->externally_visible = false;
877 new_version->no_reorder = no_reorder;
878 new_version->local.local = new_version->definition;
879 new_version->global = global;
880 new_version->rtl = rtl;
881 new_version->count = count;
882
883 for (e = callees; e; e=e->next_callee)
884 if (!bbs_to_copy
885 || bitmap_bit_p (bbs_to_copy, gimple_bb (e->call_stmt)->index))
886 e->clone (new_version, e->call_stmt,
887 e->lto_stmt_uid, REG_BR_PROB_BASE,
888 CGRAPH_FREQ_BASE,
889 true);
890 for (e = indirect_calls; e; e=e->next_callee)
891 if (!bbs_to_copy
892 || bitmap_bit_p (bbs_to_copy, gimple_bb (e->call_stmt)->index))
893 e->clone (new_version, e->call_stmt,
894 e->lto_stmt_uid, REG_BR_PROB_BASE,
895 CGRAPH_FREQ_BASE,
896 true);
897 FOR_EACH_VEC_ELT (redirect_callers, i, e)
898 {
899 /* Redirect calls to the old version node to point to its new
900 version. */
901 e->redirect_callee (new_version);
902 }
903
904 symtab->call_cgraph_duplication_hooks (this, new_version);
905
906 return new_version;
907 }
908
909 /* Perform function versioning.
910 Function versioning includes copying of the tree and
911 a callgraph update (creating a new cgraph node and updating
912 its callees and callers).
913
914 REDIRECT_CALLERS varray includes the edges to be redirected
915 to the new version.
916
917 TREE_MAP is a mapping of tree nodes we want to replace with
918 new ones (according to results of prior analysis).
919
920 If non-NULL ARGS_TO_SKIP determine function parameters to remove
921 from new version.
922 If SKIP_RETURN is true, the new version will return void.
923 If non-NULL BLOCK_TO_COPY determine what basic blocks to copy.
924 If non_NULL NEW_ENTRY determine new entry BB of the clone.
925
926 Return the new version's cgraph node. */
927
928 cgraph_node *
create_version_clone_with_body(vec<cgraph_edge * > redirect_callers,vec<ipa_replace_map *,va_gc> * tree_map,bitmap args_to_skip,bool skip_return,bitmap bbs_to_copy,basic_block new_entry_block,const char * clone_name)929 cgraph_node::create_version_clone_with_body
930 (vec<cgraph_edge *> redirect_callers,
931 vec<ipa_replace_map *, va_gc> *tree_map, bitmap args_to_skip,
932 bool skip_return, bitmap bbs_to_copy, basic_block new_entry_block,
933 const char *clone_name)
934 {
935 tree old_decl = decl;
936 cgraph_node *new_version_node = NULL;
937 tree new_decl;
938
939 if (!tree_versionable_function_p (old_decl))
940 return NULL;
941
942 gcc_assert (local.can_change_signature || !args_to_skip);
943
944 /* Make a new FUNCTION_DECL tree node for the new version. */
945 if (!args_to_skip && !skip_return)
946 new_decl = copy_node (old_decl);
947 else
948 new_decl
949 = build_function_decl_skip_args (old_decl, args_to_skip, skip_return);
950
951 /* Generate a new name for the new version. */
952 DECL_NAME (new_decl) = clone_function_name (old_decl, clone_name);
953 SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
954 SET_DECL_RTL (new_decl, NULL);
955
956 /* When the old decl was a con-/destructor make sure the clone isn't. */
957 DECL_STATIC_CONSTRUCTOR (new_decl) = 0;
958 DECL_STATIC_DESTRUCTOR (new_decl) = 0;
959
960 /* Create the new version's call-graph node.
961 and update the edges of the new node. */
962 new_version_node = create_version_clone (new_decl, redirect_callers,
963 bbs_to_copy);
964
965 if (ipa_transforms_to_apply.exists ())
966 new_version_node->ipa_transforms_to_apply
967 = ipa_transforms_to_apply.copy ();
968 /* Copy the OLD_VERSION_NODE function tree to the new version. */
969 tree_function_versioning (old_decl, new_decl, tree_map, false, args_to_skip,
970 skip_return, bbs_to_copy, new_entry_block);
971
972 /* Update the new version's properties.
973 Make The new version visible only within this translation unit. Make sure
974 that is not weak also.
975 ??? We cannot use COMDAT linkage because there is no
976 ABI support for this. */
977 new_version_node->make_decl_local ();
978 DECL_VIRTUAL_P (new_version_node->decl) = 0;
979 new_version_node->externally_visible = 0;
980 new_version_node->local.local = 1;
981 new_version_node->lowered = true;
982 if (!implicit_section)
983 new_version_node->set_section (get_section ());
984 /* Clones of global symbols or symbols with unique names are unique. */
985 if ((TREE_PUBLIC (old_decl)
986 && !DECL_EXTERNAL (old_decl)
987 && !DECL_WEAK (old_decl)
988 && !DECL_COMDAT (old_decl))
989 || in_lto_p)
990 new_version_node->unique_name = true;
991
992 /* Update the call_expr on the edges to call the new version node. */
993 update_call_expr (new_version_node);
994
995 symtab->call_cgraph_insertion_hooks (this);
996 return new_version_node;
997 }
998
999 /* Given virtual clone, turn it into actual clone. */
1000
1001 static void
cgraph_materialize_clone(cgraph_node * node)1002 cgraph_materialize_clone (cgraph_node *node)
1003 {
1004 bitmap_obstack_initialize (NULL);
1005 node->former_clone_of = node->clone_of->decl;
1006 if (node->clone_of->former_clone_of)
1007 node->former_clone_of = node->clone_of->former_clone_of;
1008 /* Copy the OLD_VERSION_NODE function tree to the new version. */
1009 tree_function_versioning (node->clone_of->decl, node->decl,
1010 node->clone.tree_map, true,
1011 node->clone.args_to_skip, false,
1012 NULL, NULL);
1013 if (symtab->dump_file)
1014 {
1015 dump_function_to_file (node->clone_of->decl, symtab->dump_file,
1016 dump_flags);
1017 dump_function_to_file (node->decl, symtab->dump_file, dump_flags);
1018 }
1019
1020 /* Function is no longer clone. */
1021 if (node->next_sibling_clone)
1022 node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
1023 if (node->prev_sibling_clone)
1024 node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
1025 else
1026 node->clone_of->clones = node->next_sibling_clone;
1027 node->next_sibling_clone = NULL;
1028 node->prev_sibling_clone = NULL;
1029 if (!node->clone_of->analyzed && !node->clone_of->clones)
1030 {
1031 node->clone_of->release_body ();
1032 node->clone_of->remove_callees ();
1033 node->clone_of->remove_all_references ();
1034 }
1035 node->clone_of = NULL;
1036 bitmap_obstack_release (NULL);
1037 }
1038
1039 /* Once all functions from compilation unit are in memory, produce all clones
1040 and update all calls. We might also do this on demand if we don't want to
1041 bring all functions to memory prior compilation, but current WHOPR
1042 implementation does that and it is a bit easier to keep everything right in
1043 this order. */
1044
1045 void
materialize_all_clones(void)1046 symbol_table::materialize_all_clones (void)
1047 {
1048 cgraph_node *node;
1049 bool stabilized = false;
1050
1051
1052 if (symtab->dump_file)
1053 fprintf (symtab->dump_file, "Materializing clones\n");
1054
1055 cgraph_node::checking_verify_cgraph_nodes ();
1056
1057 /* We can also do topological order, but number of iterations should be
1058 bounded by number of IPA passes since single IPA pass is probably not
1059 going to create clones of clones it created itself. */
1060 while (!stabilized)
1061 {
1062 stabilized = true;
1063 FOR_EACH_FUNCTION (node)
1064 {
1065 if (node->clone_of && node->decl != node->clone_of->decl
1066 && !gimple_has_body_p (node->decl))
1067 {
1068 if (!node->clone_of->clone_of)
1069 node->clone_of->get_untransformed_body ();
1070 if (gimple_has_body_p (node->clone_of->decl))
1071 {
1072 if (symtab->dump_file)
1073 {
1074 fprintf (symtab->dump_file, "cloning %s to %s\n",
1075 xstrdup_for_dump (node->clone_of->name ()),
1076 xstrdup_for_dump (node->name ()));
1077 if (node->clone.tree_map)
1078 {
1079 unsigned int i;
1080 fprintf (symtab->dump_file, " replace map: ");
1081 for (i = 0;
1082 i < vec_safe_length (node->clone.tree_map);
1083 i++)
1084 {
1085 ipa_replace_map *replace_info;
1086 replace_info = (*node->clone.tree_map)[i];
1087 print_generic_expr (symtab->dump_file, replace_info->old_tree, 0);
1088 fprintf (symtab->dump_file, " -> ");
1089 print_generic_expr (symtab->dump_file, replace_info->new_tree, 0);
1090 fprintf (symtab->dump_file, "%s%s;",
1091 replace_info->replace_p ? "(replace)":"",
1092 replace_info->ref_p ? "(ref)":"");
1093 }
1094 fprintf (symtab->dump_file, "\n");
1095 }
1096 if (node->clone.args_to_skip)
1097 {
1098 fprintf (symtab->dump_file, " args_to_skip: ");
1099 dump_bitmap (symtab->dump_file,
1100 node->clone.args_to_skip);
1101 }
1102 if (node->clone.args_to_skip)
1103 {
1104 fprintf (symtab->dump_file, " combined_args_to_skip:");
1105 dump_bitmap (symtab->dump_file, node->clone.combined_args_to_skip);
1106 }
1107 }
1108 cgraph_materialize_clone (node);
1109 stabilized = false;
1110 }
1111 }
1112 }
1113 }
1114 FOR_EACH_FUNCTION (node)
1115 if (!node->analyzed && node->callees)
1116 {
1117 node->remove_callees ();
1118 node->remove_all_references ();
1119 }
1120 else
1121 node->clear_stmts_in_references ();
1122 if (symtab->dump_file)
1123 fprintf (symtab->dump_file, "Materialization Call site updates done.\n");
1124
1125 cgraph_node::checking_verify_cgraph_nodes ();
1126
1127 symtab->remove_unreachable_nodes (symtab->dump_file);
1128 }
1129
1130 #include "gt-cgraphclones.h"
1131