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