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