contrib/gcc-5.0/gcc/cgraphclones.c

   1 /* Callgraph clones
   2    Copyright (C) 2003-2015 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 "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
 126 cgraph_edge *
 127 cgraph_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
 194 static tree
 195 build_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
 250 static tree
 251 build_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
 286 static void
 287 set_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
 307 static cgraph_node *
 308 duplicate_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->thunk = thunk->thunk;
 371   new_thunk->unique_name = in_lto_p;
 372   new_thunk->former_clone_of = thunk->decl;
 373   new_thunk->clone.args_to_skip = node->clone.args_to_skip;
 374   new_thunk->clone.combined_args_to_skip = node->clone.combined_args_to_skip;
 375
 376   cgraph_edge *e = new_thunk->create_edge (node, NULL, 0,
 377                                                   CGRAPH_FREQ_BASE);
 378   e->call_stmt_cannot_inline_p = true;
 379   symtab->call_edge_duplication_hooks (thunk->callees, e);
 380   symtab->call_cgraph_duplication_hooks (thunk, new_thunk);
 381   return new_thunk;
 382 }
 383
 384 /* If E does not lead to a thunk, simply redirect it to N.  Otherwise create
 385    one or more equivalent thunks for N and redirect E to the first in the
 386    chain.  Note that it is then necessary to call
 387    n->expand_all_artificial_thunks once all callers are redirected.  */
 388
 389 void
 390 cgraph_edge::redirect_callee_duplicating_thunks (cgraph_node *n)
 391 {
 392   cgraph_node *orig_to = callee->ultimate_alias_target ();
 393   if (orig_to->thunk.thunk_p)
 394     n = duplicate_thunk_for_node (orig_to, n);
 395
 396   redirect_callee (n);
 397 }
 398
 399 /* Call expand_thunk on all callers that are thunks and if analyze those nodes
 400    that were expanded.  */
 401
 402 void
 403 cgraph_node::expand_all_artificial_thunks ()
 404 {
 405   cgraph_edge *e;
 406   for (e = callers; e;)
 407     if (e->caller->thunk.thunk_p)
 408       {
 409         cgraph_node *thunk = e->caller;
 410
 411         e = e->next_caller;
 412         if (thunk->expand_thunk (false, false))
 413           {
 414             thunk->thunk.thunk_p = false;
 415             thunk->analyze ();
 416           }
 417         thunk->expand_all_artificial_thunks ();
 418       }
 419     else
 420       e = e->next_caller;
 421 }
 422
 423 /* Create node representing clone of N executed COUNT times.  Decrease
 424    the execution counts from original node too.
 425    The new clone will have decl set to DECL that may or may not be the same
 426    as decl of N.
 427
 428    When UPDATE_ORIGINAL is true, the counts are subtracted from the original
 429    function's profile to reflect the fact that part of execution is handled
 430    by node.
 431    When CALL_DUPLICATOIN_HOOK is true, the ipa passes are acknowledged about
 432    the new clone. Otherwise the caller is responsible for doing so later.
 433
 434    If the new node is being inlined into another one, NEW_INLINED_TO should be
 435    the outline function the new one is (even indirectly) inlined to.  All hooks
 436    will see this in node's global.inlined_to, when invoked.  Can be NULL if the
 437    node is not inlined.  */
 438
 439 cgraph_node *
 440 cgraph_node::create_clone (tree new_decl, gcov_type gcov_count, int freq,
 441                            bool update_original,
 442                            vec<cgraph_edge *> redirect_callers,
 443                            bool call_duplication_hook,
 444                            cgraph_node *new_inlined_to,
 445                            bitmap args_to_skip)
 446 {
 447   cgraph_node *new_node = symtab->create_empty ();
 448   cgraph_edge *e;
 449   gcov_type count_scale;
 450   unsigned i;
 451
 452   new_node->decl = new_decl;
 453   new_node->register_symbol ();
 454   new_node->origin = origin;
 455   new_node->lto_file_data = lto_file_data;
 456   if (new_node->origin)
 457     {
 458       new_node->next_nested = new_node->origin->nested;
 459       new_node->origin->nested = new_node;
 460     }
 461   new_node->analyzed = analyzed;
 462   new_node->definition = definition;
 463   new_node->local = local;
 464   new_node->externally_visible = false;
 465   new_node->no_reorder = no_reorder;
 466   new_node->local.local = true;
 467   new_node->global = global;
 468   new_node->global.inlined_to = new_inlined_to;
 469   new_node->rtl = rtl;
 470   new_node->count = count;
 471   new_node->frequency = frequency;
 472   new_node->tp_first_run = tp_first_run;
 473   new_node->tm_clone = tm_clone;
 474   new_node->icf_merged = icf_merged;
 475   new_node->merged = merged;
 476
 477   new_node->clone.tree_map = NULL;
 478   new_node->clone.args_to_skip = args_to_skip;
 479   new_node->split_part = split_part;
 480   if (!args_to_skip)
 481     new_node->clone.combined_args_to_skip = clone.combined_args_to_skip;
 482   else if (clone.combined_args_to_skip)
 483     {
 484       new_node->clone.combined_args_to_skip = BITMAP_GGC_ALLOC ();
 485       bitmap_ior (new_node->clone.combined_args_to_skip,
 486                   clone.combined_args_to_skip, args_to_skip);
 487     }
 488   else
 489     new_node->clone.combined_args_to_skip = args_to_skip;
 490
 491   if (count)
 492     {
 493       if (new_node->count > count)
 494         count_scale = REG_BR_PROB_BASE;
 495       else
 496         count_scale = GCOV_COMPUTE_SCALE (new_node->count, count);
 497     }
 498   else
 499     count_scale = 0;
 500   if (update_original)
 501     {
 502       count -= gcov_count;
 503       if (count < 0)
 504         count = 0;
 505     }
 506
 507   FOR_EACH_VEC_ELT (redirect_callers, i, e)
 508     {
 509       /* Redirect calls to the old version node to point to its new
 510          version.  The only exception is when the edge was proved to
 511          be unreachable during the clonning procedure.  */
 512       if (!e->callee
 513           || DECL_BUILT_IN_CLASS (e->callee->decl) != BUILT_IN_NORMAL
 514           || DECL_FUNCTION_CODE (e->callee->decl) != BUILT_IN_UNREACHABLE)
 515         e->redirect_callee_duplicating_thunks (new_node);
 516     }
 517   new_node->expand_all_artificial_thunks ();
 518
 519   for (e = callees;e; e=e->next_callee)
 520     e->clone (new_node, e->call_stmt, e->lto_stmt_uid, count_scale,
 521               freq, update_original);
 522
 523   for (e = indirect_calls; e; e = e->next_callee)
 524     e->clone (new_node, e->call_stmt, e->lto_stmt_uid,
 525               count_scale, freq, update_original);
 526   new_node->clone_references (this);
 527
 528   new_node->next_sibling_clone = clones;
 529   if (clones)
 530     clones->prev_sibling_clone = new_node;
 531   clones = new_node;
 532   new_node->clone_of = this;
 533
 534   if (call_duplication_hook)
 535     symtab->call_cgraph_duplication_hooks (this, new_node);
 536   return new_node;
 537 }
 538
 539 static GTY(()) unsigned int clone_fn_id_num;
 540
 541 /* Return a new assembler name for a clone with SUFFIX of a decl named
 542    NAME.  */
 543
 544 tree
 545 clone_function_name_1 (const char *name, const char *suffix)
 546 {
 547   size_t len = strlen (name);
 548   char *tmp_name, *prefix;
 549
 550   prefix = XALLOCAVEC (char, len + strlen (suffix) + 2);
 551   memcpy (prefix, name, len);
 552   strcpy (prefix + len + 1, suffix);
 553 #ifndef NO_DOT_IN_LABEL
 554   prefix[len] = '.';
 555 #elif !defined NO_DOLLAR_IN_LABEL
 556   prefix[len] = '$';
 557 #else
 558   prefix[len] = '_';
 559 #endif
 560   ASM_FORMAT_PRIVATE_NAME (tmp_name, prefix, clone_fn_id_num++);
 561   return get_identifier (tmp_name);
 562 }
 563
 564 /* Return a new assembler name for a clone of DECL with SUFFIX.  */
 565
 566 tree
 567 clone_function_name (tree decl, const char *suffix)
 568 {
 569   tree name = DECL_ASSEMBLER_NAME (decl);
 570   return clone_function_name_1 (IDENTIFIER_POINTER (name), suffix);
 571 }
 572
 573
 574 /* Create callgraph node clone with new declaration.  The actual body will
 575    be copied later at compilation stage.
 576
 577    TODO: after merging in ipa-sra use function call notes instead of args_to_skip
 578    bitmap interface.
 579    */
 580 cgraph_node *
 581 cgraph_node::create_virtual_clone (vec<cgraph_edge *> redirect_callers,
 582                                    vec<ipa_replace_map *, va_gc> *tree_map,
 583                                    bitmap args_to_skip, const char * suffix)
 584 {
 585   tree old_decl = decl;
 586   cgraph_node *new_node = NULL;
 587   tree new_decl;
 588   size_t len, i;
 589   ipa_replace_map *map;
 590   char *name;
 591
 592   if (!in_lto_p)
 593     gcc_checking_assert (tree_versionable_function_p (old_decl));
 594
 595   gcc_assert (local.can_change_signature || !args_to_skip);
 596
 597   /* Make a new FUNCTION_DECL tree node */
 598   if (!args_to_skip)
 599     new_decl = copy_node (old_decl);
 600   else
 601     new_decl = build_function_decl_skip_args (old_decl, args_to_skip, false);
 602
 603   /* These pointers represent function body and will be populated only when clone
 604      is materialized.  */
 605   gcc_assert (new_decl != old_decl);
 606   DECL_STRUCT_FUNCTION (new_decl) = NULL;
 607   DECL_ARGUMENTS (new_decl) = NULL;
 608   DECL_INITIAL (new_decl) = NULL;
 609   DECL_RESULT (new_decl) = NULL;
 610   /* We can not do DECL_RESULT (new_decl) = NULL; here because of LTO partitioning
 611      sometimes storing only clone decl instead of original.  */
 612
 613   /* Generate a new name for the new version. */
 614   len = IDENTIFIER_LENGTH (DECL_NAME (old_decl));
 615   name = XALLOCAVEC (char, len + strlen (suffix) + 2);
 616   memcpy (name, IDENTIFIER_POINTER (DECL_NAME (old_decl)), len);
 617   strcpy (name + len + 1, suffix);
 618   name[len] = '.';
 619   DECL_NAME (new_decl) = get_identifier (name);
 620   SET_DECL_ASSEMBLER_NAME (new_decl, clone_function_name (old_decl, suffix));
 621   SET_DECL_RTL (new_decl, NULL);
 622
 623   new_node = create_clone (new_decl, count, CGRAPH_FREQ_BASE, false,
 624                            redirect_callers, false, NULL, args_to_skip);
 625
 626   /* Update the properties.
 627      Make clone visible only within this translation unit.  Make sure
 628      that is not weak also.
 629      ??? We cannot use COMDAT linkage because there is no
 630      ABI support for this.  */
 631   set_new_clone_decl_and_node_flags (new_node);
 632   new_node->clone.tree_map = tree_map;
 633   if (!implicit_section)
 634     new_node->set_section (get_section ());
 635
 636   /* Clones of global symbols or symbols with unique names are unique.  */
 637   if ((TREE_PUBLIC (old_decl)
 638        && !DECL_EXTERNAL (old_decl)
 639        && !DECL_WEAK (old_decl)
 640        && !DECL_COMDAT (old_decl))
 641       || in_lto_p)
 642     new_node->unique_name = true;
 643   FOR_EACH_VEC_SAFE_ELT (tree_map, i, map)
 644     new_node->maybe_create_reference (map->new_tree, IPA_REF_ADDR, NULL);
 645
 646   if (ipa_transforms_to_apply.exists ())
 647     new_node->ipa_transforms_to_apply
 648       = ipa_transforms_to_apply.copy ();
 649
 650   symtab->call_cgraph_duplication_hooks (this, new_node);
 651
 652   return new_node;
 653 }
 654
 655 /* callgraph node being removed from symbol table; see if its entry can be
 656    replaced by other inline clone.  */
 657 cgraph_node *
 658 cgraph_node::find_replacement (void)
 659 {
 660   cgraph_node *next_inline_clone, *replacement;
 661
 662   for (next_inline_clone = clones;
 663        next_inline_clone
 664        && next_inline_clone->decl != decl;
 665        next_inline_clone = next_inline_clone->next_sibling_clone)
 666     ;
 667
 668   /* If there is inline clone of the node being removed, we need
 669      to put it into the position of removed node and reorganize all
 670      other clones to be based on it.  */
 671   if (next_inline_clone)
 672     {
 673       cgraph_node *n;
 674       cgraph_node *new_clones;
 675
 676       replacement = next_inline_clone;
 677
 678       /* Unlink inline clone from the list of clones of removed node.  */
 679       if (next_inline_clone->next_sibling_clone)
 680         next_inline_clone->next_sibling_clone->prev_sibling_clone
 681           = next_inline_clone->prev_sibling_clone;
 682       if (next_inline_clone->prev_sibling_clone)
 683         {
 684           gcc_assert (clones != next_inline_clone);
 685           next_inline_clone->prev_sibling_clone->next_sibling_clone
 686             = next_inline_clone->next_sibling_clone;
 687         }
 688       else
 689         {
 690           gcc_assert (clones == next_inline_clone);
 691           clones = next_inline_clone->next_sibling_clone;
 692         }
 693
 694       new_clones = clones;
 695       clones = NULL;
 696
 697       /* Copy clone info.  */
 698       next_inline_clone->clone = clone;
 699
 700       /* Now place it into clone tree at same level at NODE.  */
 701       next_inline_clone->clone_of = clone_of;
 702       next_inline_clone->prev_sibling_clone = NULL;
 703       next_inline_clone->next_sibling_clone = NULL;
 704       if (clone_of)
 705         {
 706           if (clone_of->clones)
 707             clone_of->clones->prev_sibling_clone = next_inline_clone;
 708           next_inline_clone->next_sibling_clone = clone_of->clones;
 709           clone_of->clones = next_inline_clone;
 710         }
 711
 712       /* Merge the clone list.  */
 713       if (new_clones)
 714         {
 715           if (!next_inline_clone->clones)
 716             next_inline_clone->clones = new_clones;
 717           else
 718             {
 719               n = next_inline_clone->clones;
 720               while (n->next_sibling_clone)
 721                 n = n->next_sibling_clone;
 722               n->next_sibling_clone = new_clones;
 723               new_clones->prev_sibling_clone = n;
 724             }
 725         }
 726
 727       /* Update clone_of pointers.  */
 728       n = new_clones;
 729       while (n)
 730         {
 731           n->clone_of = next_inline_clone;
 732           n = n->next_sibling_clone;
 733         }
 734       return replacement;
 735     }
 736   else
 737     return NULL;
 738 }
 739
 740 /* Like cgraph_set_call_stmt but walk the clone tree and update all
 741    clones sharing the same function body.
 742    When WHOLE_SPECULATIVE_EDGES is true, all three components of
 743    speculative edge gets updated.  Otherwise we update only direct
 744    call.  */
 745
 746 void
 747 cgraph_node::set_call_stmt_including_clones (gimple old_stmt,
 748                                              gcall *new_stmt,
 749                                              bool update_speculative)
 750 {
 751   cgraph_node *node;
 752   cgraph_edge *edge = get_edge (old_stmt);
 753
 754   if (edge)
 755     edge->set_call_stmt (new_stmt, update_speculative);
 756
 757   node = clones;
 758   if (node)
 759     while (node != this)
 760       {
 761         cgraph_edge *edge = node->get_edge (old_stmt);
 762         if (edge)
 763           {
 764             edge->set_call_stmt (new_stmt, update_speculative);
 765             /* If UPDATE_SPECULATIVE is false, it means that we are turning
 766                speculative call into a real code sequence.  Update the
 767                callgraph edges.  */
 768             if (edge->speculative && !update_speculative)
 769               {
 770                 cgraph_edge *direct, *indirect;
 771                 ipa_ref *ref;
 772
 773                 gcc_assert (!edge->indirect_unknown_callee);
 774                 edge->speculative_call_info (direct, indirect, ref);
 775                 direct->speculative = false;
 776                 indirect->speculative = false;
 777                 ref->speculative = false;
 778               }
 779           }
 780         if (node->clones)
 781           node = node->clones;
 782         else if (node->next_sibling_clone)
 783           node = node->next_sibling_clone;
 784         else
 785           {
 786             while (node != this && !node->next_sibling_clone)
 787               node = node->clone_of;
 788             if (node != this)
 789               node = node->next_sibling_clone;
 790           }
 791       }
 792 }
 793
 794 /* Like cgraph_create_edge walk the clone tree and update all clones sharing
 795    same function body.  If clones already have edge for OLD_STMT; only
 796    update the edge same way as cgraph_set_call_stmt_including_clones does.
 797
 798    TODO: COUNT and LOOP_DEPTH should be properly distributed based on relative
 799    frequencies of the clones.  */
 800
 801 void
 802 cgraph_node::create_edge_including_clones (cgraph_node *callee,
 803                                            gimple old_stmt, gcall *stmt,
 804                                            gcov_type count,
 805                                            int freq,
 806                                            cgraph_inline_failed_t reason)
 807 {
 808   cgraph_node *node;
 809   cgraph_edge *edge;
 810
 811   if (!get_edge (stmt))
 812     {
 813       edge = create_edge (callee, stmt, count, freq);
 814       edge->inline_failed = reason;
 815     }
 816
 817   node = clones;
 818   if (node)
 819     while (node != this)
 820       {
 821         cgraph_edge *edge = node->get_edge (old_stmt);
 822
 823         /* It is possible that clones already contain the edge while
 824            master didn't.  Either we promoted indirect call into direct
 825            call in the clone or we are processing clones of unreachable
 826            master where edges has been removed.  */
 827         if (edge)
 828           edge->set_call_stmt (stmt);
 829         else if (! node->get_edge (stmt))
 830           {
 831             edge = node->create_edge (callee, stmt, count, freq);
 832             edge->inline_failed = reason;
 833           }
 834
 835         if (node->clones)
 836           node = node->clones;
 837         else if (node->next_sibling_clone)
 838           node = node->next_sibling_clone;
 839         else
 840           {
 841             while (node != this && !node->next_sibling_clone)
 842               node = node->clone_of;
 843             if (node != this)
 844               node = node->next_sibling_clone;
 845           }
 846       }
 847 }
 848
 849 /* Remove the node from cgraph and all inline clones inlined into it.
 850    Skip however removal of FORBIDDEN_NODE and return true if it needs to be
 851    removed.  This allows to call the function from outer loop walking clone
 852    tree.  */
 853
 854 bool
 855 cgraph_node::remove_symbol_and_inline_clones (cgraph_node *forbidden_node)
 856 {
 857   cgraph_edge *e, *next;
 858   bool found = false;
 859
 860   if (this == forbidden_node)
 861     {
 862       callers->remove ();
 863       return true;
 864     }
 865   for (e = callees; e; e = next)
 866     {
 867       next = e->next_callee;
 868       if (!e->inline_failed)
 869         found |= e->callee->remove_symbol_and_inline_clones (forbidden_node);
 870     }
 871   remove ();
 872   return found;
 873 }
 874
 875 /* The edges representing the callers of the NEW_VERSION node were
 876    fixed by cgraph_function_versioning (), now the call_expr in their
 877    respective tree code should be updated to call the NEW_VERSION.  */
 878
 879 static void
 880 update_call_expr (cgraph_node *new_version)
 881 {
 882   cgraph_edge *e;
 883
 884   gcc_assert (new_version);
 885
 886   /* Update the call expr on the edges to call the new version.  */
 887   for (e = new_version->callers; e; e = e->next_caller)
 888     {
 889       function *inner_function = DECL_STRUCT_FUNCTION (e->caller->decl);
 890       gimple_call_set_fndecl (e->call_stmt, new_version->decl);
 891       maybe_clean_eh_stmt_fn (inner_function, e->call_stmt);
 892     }
 893 }
 894
 895
 896 /* Create a new cgraph node which is the new version of
 897    callgraph node.  REDIRECT_CALLERS holds the callers
 898    edges which should be redirected to point to
 899    NEW_VERSION.  ALL the callees edges of the node
 900    are cloned to the new version node.  Return the new
 901    version node.
 902
 903    If non-NULL BLOCK_TO_COPY determine what basic blocks
 904    was copied to prevent duplications of calls that are dead
 905    in the clone.  */
 906
 907 cgraph_node *
 908 cgraph_node::create_version_clone (tree new_decl,
 909                                   vec<cgraph_edge *> redirect_callers,
 910                                   bitmap bbs_to_copy)
 911  {
 912    cgraph_node *new_version;
 913    cgraph_edge *e;
 914    unsigned i;
 915
 916    new_version = cgraph_node::create (new_decl);
 917
 918    new_version->analyzed = analyzed;
 919    new_version->definition = definition;
 920    new_version->local = local;
 921    new_version->externally_visible = false;
 922    new_version->no_reorder = no_reorder;
 923    new_version->local.local = new_version->definition;
 924    new_version->global = global;
 925    new_version->rtl = rtl;
 926    new_version->count = count;
 927
 928    for (e = callees; e; e=e->next_callee)
 929      if (!bbs_to_copy
 930          || bitmap_bit_p (bbs_to_copy, gimple_bb (e->call_stmt)->index))
 931        e->clone (new_version, e->call_stmt,
 932                  e->lto_stmt_uid, REG_BR_PROB_BASE,
 933                  CGRAPH_FREQ_BASE,
 934                  true);
 935    for (e = indirect_calls; e; e=e->next_callee)
 936      if (!bbs_to_copy
 937          || bitmap_bit_p (bbs_to_copy, gimple_bb (e->call_stmt)->index))
 938        e->clone (new_version, e->call_stmt,
 939                  e->lto_stmt_uid, REG_BR_PROB_BASE,
 940                  CGRAPH_FREQ_BASE,
 941                  true);
 942    FOR_EACH_VEC_ELT (redirect_callers, i, e)
 943      {
 944        /* Redirect calls to the old version node to point to its new
 945           version.  */
 946        e->redirect_callee (new_version);
 947      }
 948
 949    symtab->call_cgraph_duplication_hooks (this, new_version);
 950
 951    return new_version;
 952  }
 953
 954 /* Perform function versioning.
 955    Function versioning includes copying of the tree and
 956    a callgraph update (creating a new cgraph node and updating
 957    its callees and callers).
 958
 959    REDIRECT_CALLERS varray includes the edges to be redirected
 960    to the new version.
 961
 962    TREE_MAP is a mapping of tree nodes we want to replace with
 963    new ones (according to results of prior analysis).
 964
 965    If non-NULL ARGS_TO_SKIP determine function parameters to remove
 966    from new version.
 967    If SKIP_RETURN is true, the new version will return void.
 968    If non-NULL BLOCK_TO_COPY determine what basic blocks to copy.
 969    If non_NULL NEW_ENTRY determine new entry BB of the clone.
 970
 971    Return the new version's cgraph node.  */
 972
 973 cgraph_node *
 974 cgraph_node::create_version_clone_with_body
 975   (vec<cgraph_edge *> redirect_callers,
 976    vec<ipa_replace_map *, va_gc> *tree_map, bitmap args_to_skip,
 977    bool skip_return, bitmap bbs_to_copy, basic_block new_entry_block,
 978    const char *clone_name)
 979 {
 980   tree old_decl = decl;
 981   cgraph_node *new_version_node = NULL;
 982   tree new_decl;
 983
 984   if (!tree_versionable_function_p (old_decl))
 985     return NULL;
 986
 987   gcc_assert (local.can_change_signature || !args_to_skip);
 988
 989   /* Make a new FUNCTION_DECL tree node for the new version. */
 990   if (!args_to_skip && !skip_return)
 991     new_decl = copy_node (old_decl);
 992   else
 993     new_decl
 994       = build_function_decl_skip_args (old_decl, args_to_skip, skip_return);
 995
 996   /* Generate a new name for the new version. */
 997   DECL_NAME (new_decl) = clone_function_name (old_decl, clone_name);
 998   SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
 999   SET_DECL_RTL (new_decl, NULL);
1000
1001   /* When the old decl was a con-/destructor make sure the clone isn't.  */
1002   DECL_STATIC_CONSTRUCTOR (new_decl) = 0;
1003   DECL_STATIC_DESTRUCTOR (new_decl) = 0;
1004
1005   /* Create the new version's call-graph node.
1006      and update the edges of the new node. */
1007   new_version_node = create_version_clone (new_decl, redirect_callers,
1008                                           bbs_to_copy);
1009
1010   if (ipa_transforms_to_apply.exists ())
1011     new_version_node->ipa_transforms_to_apply
1012       = ipa_transforms_to_apply.copy ();
1013   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
1014   tree_function_versioning (old_decl, new_decl, tree_map, false, args_to_skip,
1015                             skip_return, bbs_to_copy, new_entry_block);
1016
1017   /* Update the new version's properties.
1018      Make The new version visible only within this translation unit.  Make sure
1019      that is not weak also.
1020      ??? We cannot use COMDAT linkage because there is no
1021      ABI support for this.  */
1022   new_version_node->make_decl_local ();
1023   DECL_VIRTUAL_P (new_version_node->decl) = 0;
1024   new_version_node->externally_visible = 0;
1025   new_version_node->local.local = 1;
1026   new_version_node->lowered = true;
1027   if (!implicit_section)
1028     new_version_node->set_section (get_section ());
1029   /* Clones of global symbols or symbols with unique names are unique.  */
1030   if ((TREE_PUBLIC (old_decl)
1031        && !DECL_EXTERNAL (old_decl)
1032        && !DECL_WEAK (old_decl)
1033        && !DECL_COMDAT (old_decl))
1034       || in_lto_p)
1035     new_version_node->unique_name = true;
1036
1037   /* Update the call_expr on the edges to call the new version node. */
1038   update_call_expr (new_version_node);
1039
1040   symtab->call_cgraph_insertion_hooks (this);
1041   return new_version_node;
1042 }
1043
1044 /* Given virtual clone, turn it into actual clone.  */
1045
1046 static void
1047 cgraph_materialize_clone (cgraph_node *node)
1048 {
1049   bitmap_obstack_initialize (NULL);
1050   node->former_clone_of = node->clone_of->decl;
1051   if (node->clone_of->former_clone_of)
1052     node->former_clone_of = node->clone_of->former_clone_of;
1053   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
1054   tree_function_versioning (node->clone_of->decl, node->decl,
1055                             node->clone.tree_map, true,
1056                             node->clone.args_to_skip, false,
1057                             NULL, NULL);
1058   if (symtab->dump_file)
1059     {
1060       dump_function_to_file (node->clone_of->decl, symtab->dump_file,
1061                              dump_flags);
1062       dump_function_to_file (node->decl, symtab->dump_file, dump_flags);
1063     }
1064
1065   /* Function is no longer clone.  */
1066   if (node->next_sibling_clone)
1067     node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
1068   if (node->prev_sibling_clone)
1069     node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
1070   else
1071     node->clone_of->clones = node->next_sibling_clone;
1072   node->next_sibling_clone = NULL;
1073   node->prev_sibling_clone = NULL;
1074   if (!node->clone_of->analyzed && !node->clone_of->clones)
1075     {
1076       node->clone_of->release_body ();
1077       node->clone_of->remove_callees ();
1078       node->clone_of->remove_all_references ();
1079     }
1080   node->clone_of = NULL;
1081   bitmap_obstack_release (NULL);
1082 }
1083
1084 /* Once all functions from compilation unit are in memory, produce all clones
1085    and update all calls.  We might also do this on demand if we don't want to
1086    bring all functions to memory prior compilation, but current WHOPR
1087    implementation does that and it is is bit easier to keep everything right in
1088    this order.  */
1089
1090 void
1091 symbol_table::materialize_all_clones (void)
1092 {
1093   cgraph_node *node;
1094   bool stabilized = false;
1095
1096
1097   if (symtab->dump_file)
1098     fprintf (symtab->dump_file, "Materializing clones\n");
1099 #ifdef ENABLE_CHECKING
1100   cgraph_node::verify_cgraph_nodes ();
1101 #endif
1102
1103   /* We can also do topological order, but number of iterations should be
1104      bounded by number of IPA passes since single IPA pass is probably not
1105      going to create clones of clones it created itself.  */
1106   while (!stabilized)
1107     {
1108       stabilized = true;
1109       FOR_EACH_FUNCTION (node)
1110         {
1111           if (node->clone_of && node->decl != node->clone_of->decl
1112               && !gimple_has_body_p (node->decl))
1113             {
1114               if (!node->clone_of->clone_of)
1115                 node->clone_of->get_untransformed_body ();
1116               if (gimple_has_body_p (node->clone_of->decl))
1117                 {
1118                   if (symtab->dump_file)
1119                     {
1120                       fprintf (symtab->dump_file, "cloning %s to %s\n",
1121                                xstrdup_for_dump (node->clone_of->name ()),
1122                                xstrdup_for_dump (node->name ()));
1123                       if (node->clone.tree_map)
1124                         {
1125                           unsigned int i;
1126                           fprintf (symtab->dump_file, "   replace map: ");
1127                           for (i = 0;
1128                                i < vec_safe_length (node->clone.tree_map);
1129                                i++)
1130                             {
1131                               ipa_replace_map *replace_info;
1132                               replace_info = (*node->clone.tree_map)[i];
1133                               print_generic_expr (symtab->dump_file, replace_info->old_tree, 0);
1134                               fprintf (symtab->dump_file, " -> ");
1135                               print_generic_expr (symtab->dump_file, replace_info->new_tree, 0);
1136                               fprintf (symtab->dump_file, "%s%s;",
1137                                        replace_info->replace_p ? "(replace)":"",
1138                                        replace_info->ref_p ? "(ref)":"");
1139                             }
1140                           fprintf (symtab->dump_file, "\n");
1141                         }
1142                       if (node->clone.args_to_skip)
1143                         {
1144                           fprintf (symtab->dump_file, "   args_to_skip: ");
1145                           dump_bitmap (symtab->dump_file,
1146                                        node->clone.args_to_skip);
1147                         }
1148                       if (node->clone.args_to_skip)
1149                         {
1150                           fprintf (symtab->dump_file, "   combined_args_to_skip:");
1151                           dump_bitmap (symtab->dump_file, node->clone.combined_args_to_skip);
1152                         }
1153                     }
1154                   cgraph_materialize_clone (node);
1155                   stabilized = false;
1156                 }
1157             }
1158         }
1159     }
1160   FOR_EACH_FUNCTION (node)
1161     if (!node->analyzed && node->callees)
1162       {
1163         node->remove_callees ();
1164         node->remove_all_references ();
1165       }
1166     else
1167       node->clear_stmts_in_references ();
1168   if (symtab->dump_file)
1169     fprintf (symtab->dump_file, "Materialization Call site updates done.\n");
1170 #ifdef ENABLE_CHECKING
1171   cgraph_node::verify_cgraph_nodes ();
1172 #endif
1173   symtab->remove_unreachable_nodes (symtab->dump_file);
1174 }
1175
1176 #include "gt-cgraphclones.h"