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 aliases are involved, redirect edge to the actual destination and
 326      possibly remove the aliases.  */
 327   if (e->callee != callee)
 328     {
 329       struct cgraph_node *alias = e->callee, *next_alias;
 330       e->redirect_callee (callee);
 331       while (alias && alias != callee)
 332         {
 333           if (!alias->callers
 334               && can_remove_node_now_p (alias,
 335                                         !e->next_caller && !e->prev_caller ? e : NULL))
 336             {
 337               next_alias = alias->get_alias_target ();
 338               alias->remove ();
 339               if (callee_removed)
 340                 *callee_removed = true;
 341               alias = next_alias;
 342             }
 343           else
 344             break;
 345         }
 346     }
 347
 348   clone_inlined_nodes (e, true, update_original, overall_size, e->frequency);
 349
 350   gcc_assert (curr->callee->global.inlined_to == to);
 351
 352   old_size = inline_summaries->get (to)->size;
 353   inline_merge_summary (e);
 354   if (e->in_polymorphic_cdtor)
 355     mark_all_inlined_calls_cdtor (e->callee);
 356   if (opt_for_fn (e->caller->decl, optimize))
 357     new_edges_found = ipa_propagate_indirect_call_infos (curr, new_edges);
 358   if (update_overall_summary)
 359    inline_update_overall_summary (to);
 360   new_size = inline_summaries->get (to)->size;
 361
 362   if (callee->calls_comdat_local)
 363     to->calls_comdat_local = true;
 364   else if (to->calls_comdat_local && callee->comdat_local_p ())
 365     {
 366       struct cgraph_edge *se = to->callees;
 367       for (; se; se = se->next_callee)
 368         if (se->inline_failed && se->callee->comdat_local_p ())
 369           break;
 370       if (se == NULL)
 371         to->calls_comdat_local = false;
 372     }
 373
 374 #ifdef ENABLE_CHECKING
 375   /* Verify that estimated growth match real growth.  Allow off-by-one
 376      error due to INLINE_SIZE_SCALE roudoff errors.  */
 377   gcc_assert (!update_overall_summary || !overall_size || new_edges_found
 378               || abs (estimated_growth - (new_size - old_size)) <= 1
 379               || speculation_removed
 380               /* FIXME: a hack.  Edges with false predicate are accounted
 381                  wrong, we should remove them from callgraph.  */
 382               || predicated);
 383 #endif
 384
 385   /* Account the change of overall unit size; external functions will be
 386      removed and are thus not accounted.  */
 387   if (overall_size && inline_account_function_p (to))
 388     *overall_size += new_size - old_size;
 389   ncalls_inlined++;
 390
 391   /* This must happen after inline_merge_summary that rely on jump
 392      functions of callee to not be updated.  */
 393   return new_edges_found;
 394 }
 395
 396
 397 /* Copy function body of NODE and redirect all inline clones to it.
 398    This is done before inline plan is applied to NODE when there are
 399    still some inline clones if it.
 400
 401    This is necessary because inline decisions are not really transitive
 402    and the other inline clones may have different bodies.  */
 403
 404 static struct cgraph_node *
 405 save_inline_function_body (struct cgraph_node *node)
 406 {
 407   struct cgraph_node *first_clone, *n;
 408
 409   if (dump_file)
 410     fprintf (dump_file, "\nSaving body of %s for later reuse\n",
 411              node->name ());
 412
 413   gcc_assert (node == cgraph_node::get (node->decl));
 414
 415   /* first_clone will be turned into real function.  */
 416   first_clone = node->clones;
 417   first_clone->decl = copy_node (node->decl);
 418   first_clone->decl->decl_with_vis.symtab_node = first_clone;
 419   gcc_assert (first_clone == cgraph_node::get (first_clone->decl));
 420
 421   /* Now reshape the clone tree, so all other clones descends from
 422      first_clone.  */
 423   if (first_clone->next_sibling_clone)
 424     {
 425       for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
 426         n->clone_of = first_clone;
 427       n->clone_of = first_clone;
 428       n->next_sibling_clone = first_clone->clones;
 429       if (first_clone->clones)
 430         first_clone->clones->prev_sibling_clone = n;
 431       first_clone->clones = first_clone->next_sibling_clone;
 432       first_clone->next_sibling_clone->prev_sibling_clone = NULL;
 433       first_clone->next_sibling_clone = NULL;
 434       gcc_assert (!first_clone->prev_sibling_clone);
 435     }
 436   first_clone->clone_of = NULL;
 437
 438   /* Now node in question has no clones.  */
 439   node->clones = NULL;
 440
 441   /* Inline clones share decl with the function they are cloned
 442      from.  Walk the whole clone tree and redirect them all to the
 443      new decl.  */
 444   if (first_clone->clones)
 445     for (n = first_clone->clones; n != first_clone;)
 446       {
 447         gcc_assert (n->decl == node->decl);
 448         n->decl = first_clone->decl;
 449         if (n->clones)
 450           n = n->clones;
 451         else if (n->next_sibling_clone)
 452           n = n->next_sibling_clone;
 453         else
 454           {
 455             while (n != first_clone && !n->next_sibling_clone)
 456               n = n->clone_of;
 457             if (n != first_clone)
 458               n = n->next_sibling_clone;
 459           }
 460       }
 461
 462   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
 463   tree_function_versioning (node->decl, first_clone->decl,
 464                             NULL, true, NULL, false,
 465                             NULL, NULL);
 466
 467   /* The function will be short lived and removed after we inline all the clones,
 468      but make it internal so we won't confuse ourself.  */
 469   DECL_EXTERNAL (first_clone->decl) = 0;
 470   TREE_PUBLIC (first_clone->decl) = 0;
 471   DECL_COMDAT (first_clone->decl) = 0;
 472   first_clone->ipa_transforms_to_apply.release ();
 473
 474   /* When doing recursive inlining, the clone may become unnecessary.
 475      This is possible i.e. in the case when the recursive function is proved to be
 476      non-throwing and the recursion happens only in the EH landing pad.
 477      We can not remove the clone until we are done with saving the body.
 478      Remove it now.  */
 479   if (!first_clone->callers)
 480     {
 481       first_clone->remove_symbol_and_inline_clones ();
 482       first_clone = NULL;
 483     }
 484 #ifdef ENABLE_CHECKING
 485   else
 486     first_clone->verify ();
 487 #endif
 488   return first_clone;
 489 }
 490
 491 /* Return true when function body of DECL still needs to be kept around
 492    for later re-use.  */
 493 static bool
 494 preserve_function_body_p (struct cgraph_node *node)
 495 {
 496   gcc_assert (symtab->global_info_ready);
 497   gcc_assert (!node->alias && !node->thunk.thunk_p);
 498
 499   /* Look if there is any clone around.  */
 500   if (node->clones)
 501     return true;
 502   return false;
 503 }
 504
 505 /* Apply inline plan to function.  */
 506
 507 unsigned int
 508 inline_transform (struct cgraph_node *node)
 509 {
 510   unsigned int todo = 0;
 511   struct cgraph_edge *e, *next;
 512   bool has_inline = false;
 513
 514   /* FIXME: Currently the pass manager is adding inline transform more than
 515      once to some clones.  This needs revisiting after WPA cleanups.  */
 516   if (cfun->after_inlining)
 517     return 0;
 518
 519   /* We might need the body of this function so that we can expand
 520      it inline somewhere else.  */
 521   if (preserve_function_body_p (node))
 522     save_inline_function_body (node);
 523
 524   for (e = node->callees; e; e = next)
 525     {
 526       if (!e->inline_failed)
 527         has_inline = true;
 528       next = e->next_callee;
 529       e->redirect_call_stmt_to_callee ();
 530     }
 531   node->remove_all_references ();
 532
 533   timevar_push (TV_INTEGRATION);
 534   if (node->callees && (opt_for_fn (node->decl, optimize) || has_inline))
 535     todo = optimize_inline_calls (current_function_decl);
 536   timevar_pop (TV_INTEGRATION);
 537
 538   cfun->always_inline_functions_inlined = true;
 539   cfun->after_inlining = true;
 540   todo |= execute_fixup_cfg ();
 541
 542   if (!(todo & TODO_update_ssa_any))
 543     /* Redirecting edges might lead to a need for vops to be recomputed.  */
 544     todo |= TODO_update_ssa_only_virtuals;
 545
 546   return todo;
 547 }