gcc/ipa-inline-transform.c

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