gcc/ipa-inline-transform.c

   1 /* Callgraph transformations to handle inlining
   2    Copyright (C) 2003-2013 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 "tree.h"
  36 #include "langhooks.h"
  37 #include "cgraph.h"
  38 #include "intl.h"
  39 #include "coverage.h"
  40 #include "ggc.h"
  41 #include "tree-ssa.h"
  42 #include "ipa-prop.h"
  43 #include "ipa-inline.h"
  44 #include "tree-inline.h"
  45 #include "tree-pass.h"
  46
  47 int ncalls_inlined;
  48 int nfunctions_inlined;
  49 bool speculation_removed;
  50
  51 /* Scale frequency of NODE edges by FREQ_SCALE.  */
  52
  53 static void
  54 update_noncloned_frequencies (struct cgraph_node *node,
  55                               int freq_scale)
  56 {
  57   struct cgraph_edge *e;
  58
  59   /* We do not want to ignore high loop nest after freq drops to 0.  */
  60   if (!freq_scale)
  61     freq_scale = 1;
  62   for (e = node->callees; e; e = e->next_callee)
  63     {
  64       e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
  65       if (e->frequency > CGRAPH_FREQ_MAX)
  66         e->frequency = CGRAPH_FREQ_MAX;
  67       if (!e->inline_failed)
  68         update_noncloned_frequencies (e->callee, freq_scale);
  69     }
  70   for (e = node->indirect_calls; e; e = e->next_callee)
  71     {
  72       e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
  73       if (e->frequency > CGRAPH_FREQ_MAX)
  74         e->frequency = CGRAPH_FREQ_MAX;
  75     }
  76 }
  77
  78 /* We removed or are going to remove the last call to NODE.
  79    Return true if we can and want proactively remove the NODE now.
  80    This is important to do, since we want inliner to know when offline
  81    copy of function was removed.  */
  82
  83 static bool
  84 can_remove_node_now_p_1 (struct cgraph_node *node)
  85 {
  86   /* FIXME: When address is taken of DECL_EXTERNAL function we still
  87      can remove its offline copy, but we would need to keep unanalyzed node in
  88      the callgraph so references can point to it.  */
  89   return (!node->symbol.address_taken
  90           && !ipa_ref_has_aliases_p (&node->symbol.ref_list)
  91           && !node->used_as_abstract_origin
  92           && cgraph_can_remove_if_no_direct_calls_p (node)
  93           /* Inlining might enable more devirtualizing, so we want to remove
  94              those only after all devirtualizable virtual calls are processed.
  95              Lacking may edges in callgraph we just preserve them post
  96              inlining.  */
  97           && !DECL_VIRTUAL_P (node->symbol.decl)
  98           /* During early inlining some unanalyzed cgraph nodes might be in the
  99              callgraph and they might reffer the function in question.  */
 100           && !cgraph_new_nodes);
 101 }
 102
 103 /* We are going to eliminate last direct call to NODE (or alias of it) via edge E.
 104    Verify that the NODE can be removed from unit and if it is contained in comdat
 105    group that the whole comdat group is removable.  */
 106
 107 static bool
 108 can_remove_node_now_p (struct cgraph_node *node, struct cgraph_edge *e)
 109 {
 110   struct cgraph_node *next;
 111   if (!can_remove_node_now_p_1 (node))
 112     return false;
 113
 114   /* When we see same comdat group, we need to be sure that all
 115      items can be removed.  */
 116   if (!node->symbol.same_comdat_group)
 117     return true;
 118   for (next = cgraph (node->symbol.same_comdat_group);
 119        next != node; next = cgraph (next->symbol.same_comdat_group))
 120     if ((next->callers && next->callers != e)
 121         || !can_remove_node_now_p_1 (next))
 122       return false;
 123   return true;
 124 }
 125
 126
 127 /* E is expected to be an edge being inlined.  Clone destination node of
 128    the edge and redirect it to the new clone.
 129    DUPLICATE is used for bookkeeping on whether we are actually creating new
 130    clones or re-using node originally representing out-of-line function call.
 131    */
 132
 133 void
 134 clone_inlined_nodes (struct cgraph_edge *e, bool duplicate,
 135                      bool update_original, int *overall_size)
 136 {
 137   struct cgraph_node *inlining_into;
 138   struct cgraph_edge *next;
 139
 140   if (e->caller->global.inlined_to)
 141     inlining_into = e->caller->global.inlined_to;
 142   else
 143     inlining_into = e->caller;
 144
 145   if (duplicate)
 146     {
 147       /* We may eliminate the need for out-of-line copy to be output.
 148          In that case just go ahead and re-use it.  This is not just an
 149          memory optimization.  Making offline copy of fuction disappear
 150          from the program will improve future decisions on inlining.  */
 151       if (!e->callee->callers->next_caller
 152           /* Recursive inlining never wants the master clone to
 153              be overwritten.  */
 154           && update_original
 155           && can_remove_node_now_p (e->callee, e))
 156         {
 157           /* TODO: When callee is in a comdat group, we could remove all of it,
 158              including all inline clones inlined into it.  That would however
 159              need small function inlining to register edge removal hook to
 160              maintain the priority queue.
 161
 162              For now we keep the ohter functions in the group in program until
 163              cgraph_remove_unreachable_functions gets rid of them.  */
 164           gcc_assert (!e->callee->global.inlined_to);
 165           symtab_dissolve_same_comdat_group_list ((symtab_node) e->callee);
 166           if (e->callee->symbol.definition && !DECL_EXTERNAL (e->callee->symbol.decl))
 167             {
 168               if (overall_size)
 169                 *overall_size -= inline_summary (e->callee)->size;
 170               nfunctions_inlined++;
 171             }
 172           duplicate = false;
 173           e->callee->symbol.externally_visible = false;
 174           update_noncloned_frequencies (e->callee, e->frequency);
 175         }
 176       else
 177         {
 178           struct cgraph_node *n;
 179           n = cgraph_clone_node (e->callee, e->callee->symbol.decl,
 180                                  e->count, e->frequency, update_original,
 181                                  vNULL, true, inlining_into);
 182           cgraph_redirect_edge_callee (e, n);
 183         }
 184     }
 185   else
 186     symtab_dissolve_same_comdat_group_list ((symtab_node) e->callee);
 187
 188   e->callee->global.inlined_to = inlining_into;
 189
 190   /* Recursively clone all bodies.  */
 191   for (e = e->callee->callees; e; e = next)
 192     {
 193       next = e->next_callee;
 194       if (!e->inline_failed)
 195         clone_inlined_nodes (e, duplicate, update_original, overall_size);
 196       if (e->speculative && !speculation_useful_p (e, true))
 197         {
 198           cgraph_resolve_speculation (e, NULL);
 199           speculation_removed = true;
 200         }
 201     }
 202 }
 203
 204
 205 /* Mark edge E as inlined and update callgraph accordingly.  UPDATE_ORIGINAL
 206    specify whether profile of original function should be updated.  If any new
 207    indirect edges are discovered in the process, add them to NEW_EDGES, unless
 208    it is NULL. If UPDATE_OVERALL_SUMMARY is false, do not bother to recompute overall
 209    size of caller after inlining. Caller is required to eventually do it via
 210    inline_update_overall_summary.
 211
 212    Return true iff any new callgraph edges were discovered as a
 213    result of inlining.  */
 214
 215 bool
 216 inline_call (struct cgraph_edge *e, bool update_original,
 217              vec<cgraph_edge_p> *new_edges,
 218              int *overall_size, bool update_overall_summary)
 219 {
 220   int old_size = 0, new_size = 0;
 221   struct cgraph_node *to = NULL;
 222   struct cgraph_edge *curr = e;
 223   struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
 224   bool new_edges_found = false;
 225
 226 #ifdef ENABLE_CHECKING
 227   int estimated_growth = estimate_edge_growth (e);
 228   bool predicated = inline_edge_summary (e)->predicate != NULL;
 229 #endif
 230
 231   speculation_removed = false;
 232   /* Don't inline inlined edges.  */
 233   gcc_assert (e->inline_failed);
 234   /* Don't even think of inlining inline clone.  */
 235   gcc_assert (!callee->global.inlined_to);
 236
 237   e->inline_failed = CIF_OK;
 238   DECL_POSSIBLY_INLINED (callee->symbol.decl) = true;
 239
 240   to = e->caller;
 241   if (to->global.inlined_to)
 242     to = to->global.inlined_to;
 243
 244   /* If aliases are involved, redirect edge to the actual destination and
 245      possibly remove the aliases.  */
 246   if (e->callee != callee)
 247     {
 248       struct cgraph_node *alias = e->callee, *next_alias;
 249       cgraph_redirect_edge_callee (e, callee);
 250       while (alias && alias != callee)
 251         {
 252           if (!alias->callers
 253               && can_remove_node_now_p (alias, e))
 254             {
 255               next_alias = cgraph_alias_target (alias);
 256               cgraph_remove_node (alias);
 257               alias = next_alias;
 258             }
 259           else
 260             break;
 261         }
 262     }
 263
 264   clone_inlined_nodes (e, true, update_original, overall_size);
 265
 266   gcc_assert (curr->callee->global.inlined_to == to);
 267
 268   old_size = inline_summary (to)->size;
 269   inline_merge_summary (e);
 270   if (optimize)
 271     new_edges_found = ipa_propagate_indirect_call_infos (curr, new_edges);
 272   if (update_overall_summary)
 273    inline_update_overall_summary (to);
 274   new_size = inline_summary (to)->size;
 275
 276 #ifdef ENABLE_CHECKING
 277   /* Verify that estimated growth match real growth.  Allow off-by-one
 278      error due to INLINE_SIZE_SCALE roudoff errors.  */
 279   gcc_assert (!update_overall_summary || !overall_size || new_edges_found
 280               || abs (estimated_growth - (new_size - old_size)) <= 1
 281               || speculation_removed
 282               /* FIXME: a hack.  Edges with false predicate are accounted
 283                  wrong, we should remove them from callgraph.  */
 284               || predicated);
 285 #endif
 286
 287   /* Account the change of overall unit size; external functions will be
 288      removed and are thus not accounted.  */
 289   if (overall_size
 290       && !DECL_EXTERNAL (to->symbol.decl))
 291     *overall_size += new_size - old_size;
 292   ncalls_inlined++;
 293
 294   /* This must happen after inline_merge_summary that rely on jump
 295      functions of callee to not be updated.  */
 296   return new_edges_found;
 297 }
 298
 299
 300 /* Copy function body of NODE and redirect all inline clones to it.
 301    This is done before inline plan is applied to NODE when there are
 302    still some inline clones if it.
 303
 304    This is necessary because inline decisions are not really transitive
 305    and the other inline clones may have different bodies.  */
 306
 307 static struct cgraph_node *
 308 save_inline_function_body (struct cgraph_node *node)
 309 {
 310   struct cgraph_node *first_clone, *n;
 311
 312   if (dump_file)
 313     fprintf (dump_file, "\nSaving body of %s for later reuse\n",
 314              cgraph_node_name (node));
 315
 316   gcc_assert (node == cgraph_get_node (node->symbol.decl));
 317
 318   /* first_clone will be turned into real function.  */
 319   first_clone = node->clones;
 320   first_clone->symbol.decl = copy_node (node->symbol.decl);
 321   symtab_insert_node_to_hashtable ((symtab_node) first_clone);
 322   gcc_assert (first_clone == cgraph_get_node (first_clone->symbol.decl));
 323
 324   /* Now reshape the clone tree, so all other clones descends from
 325      first_clone.  */
 326   if (first_clone->next_sibling_clone)
 327     {
 328       for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
 329         n->clone_of = first_clone;
 330       n->clone_of = first_clone;
 331       n->next_sibling_clone = first_clone->clones;
 332       if (first_clone->clones)
 333         first_clone->clones->prev_sibling_clone = n;
 334       first_clone->clones = first_clone->next_sibling_clone;
 335       first_clone->next_sibling_clone->prev_sibling_clone = NULL;
 336       first_clone->next_sibling_clone = NULL;
 337       gcc_assert (!first_clone->prev_sibling_clone);
 338     }
 339   first_clone->clone_of = NULL;
 340
 341   /* Now node in question has no clones.  */
 342   node->clones = NULL;
 343
 344   /* Inline clones share decl with the function they are cloned
 345      from.  Walk the whole clone tree and redirect them all to the
 346      new decl.  */
 347   if (first_clone->clones)
 348     for (n = first_clone->clones; n != first_clone;)
 349       {
 350         gcc_assert (n->symbol.decl == node->symbol.decl);
 351         n->symbol.decl = first_clone->symbol.decl;
 352         if (n->clones)
 353           n = n->clones;
 354         else if (n->next_sibling_clone)
 355           n = n->next_sibling_clone;
 356         else
 357           {
 358             while (n != first_clone && !n->next_sibling_clone)
 359               n = n->clone_of;
 360             if (n != first_clone)
 361               n = n->next_sibling_clone;
 362           }
 363       }
 364
 365   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
 366   tree_function_versioning (node->symbol.decl, first_clone->symbol.decl,
 367                             NULL, true, NULL, false,
 368                             NULL, NULL);
 369
 370   /* The function will be short lived and removed after we inline all the clones,
 371      but make it internal so we won't confuse ourself.  */
 372   DECL_EXTERNAL (first_clone->symbol.decl) = 0;
 373   DECL_COMDAT_GROUP (first_clone->symbol.decl) = NULL_TREE;
 374   TREE_PUBLIC (first_clone->symbol.decl) = 0;
 375   DECL_COMDAT (first_clone->symbol.decl) = 0;
 376   first_clone->ipa_transforms_to_apply.release ();
 377
 378   /* When doing recursive inlining, the clone may become unnecessary.
 379      This is possible i.e. in the case when the recursive function is proved to be
 380      non-throwing and the recursion happens only in the EH landing pad.
 381      We can not remove the clone until we are done with saving the body.
 382      Remove it now.  */
 383   if (!first_clone->callers)
 384     {
 385       cgraph_remove_node_and_inline_clones (first_clone, NULL);
 386       first_clone = NULL;
 387     }
 388 #ifdef ENABLE_CHECKING
 389   else
 390     verify_cgraph_node (first_clone);
 391 #endif
 392   return first_clone;
 393 }
 394
 395 /* Return true when function body of DECL still needs to be kept around
 396    for later re-use.  */
 397 static bool
 398 preserve_function_body_p (struct cgraph_node *node)
 399 {
 400   gcc_assert (cgraph_global_info_ready);
 401   gcc_assert (!node->symbol.alias && !node->thunk.thunk_p);
 402
 403   /* Look if there is any clone around.  */
 404   if (node->clones)
 405     return true;
 406   return false;
 407 }
 408
 409 /* Apply inline plan to function.  */
 410
 411 unsigned int
 412 inline_transform (struct cgraph_node *node)
 413 {
 414   unsigned int todo = 0;
 415   struct cgraph_edge *e, *next;
 416
 417   /* FIXME: Currently the pass manager is adding inline transform more than
 418      once to some clones.  This needs revisiting after WPA cleanups.  */
 419   if (cfun->after_inlining)
 420     return 0;
 421
 422   /* We might need the body of this function so that we can expand
 423      it inline somewhere else.  */
 424   if (preserve_function_body_p (node))
 425     save_inline_function_body (node);
 426
 427   for (e = node->callees; e; e = next)
 428     {
 429       next = e->next_callee;
 430       cgraph_redirect_edge_call_stmt_to_callee (e);
 431     }
 432   ipa_remove_all_references (&node->symbol.ref_list);
 433
 434   timevar_push (TV_INTEGRATION);
 435   if (node->callees && optimize)
 436     todo = optimize_inline_calls (current_function_decl);
 437   timevar_pop (TV_INTEGRATION);
 438
 439   cfun->always_inline_functions_inlined = true;
 440   cfun->after_inlining = true;
 441   todo |= execute_fixup_cfg ();
 442
 443   if (!(todo & TODO_update_ssa_any))
 444     /* Redirecting edges might lead to a need for vops to be recomputed.  */
 445     todo |= TODO_update_ssa_only_virtuals;
 446
 447   return todo;
 448 }