gcc/ipa-inline-transform.c

   1 /* Callgraph transformations to handle inlining
   2    Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010, 2011
   3    Free Software Foundation, Inc.
   4    Contributed by Jan Hubicka
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* The inline decisions are stored in callgraph in "inline plan" and
  23    applied later.
  24
  25    To mark given call inline, use inline_call function.
  26    The function marks the edge inlinable and, if necessary, produces
  27    virtual clone in the callgraph representing the new copy of callee's
  28    function body.
  29
  30    The inline plan is applied on given function body by inline_transform.  */
  31
  32 #include "config.h"
  33 #include "system.h"
  34 #include "coretypes.h"
  35 #include "tm.h"
  36 #include "tree.h"
  37 #include "langhooks.h"
  38 #include "cgraph.h"
  39 #include "timevar.h"
  40 #include "output.h"
  41 #include "intl.h"
  42 #include "coverage.h"
  43 #include "ggc.h"
  44 #include "tree-flow.h"
  45 #include "ipa-prop.h"
  46 #include "ipa-inline.h"
  47 #include "tree-inline.h"
  48
  49 int ncalls_inlined;
  50 int nfunctions_inlined;
  51
  52 /* Scale frequency of NODE edges by FREQ_SCALE.  */
  53
  54 static void
  55 update_noncloned_frequencies (struct cgraph_node *node,
  56                               int freq_scale)
  57 {
  58   struct cgraph_edge *e;
  59
  60   /* We do not want to ignore high loop nest after freq drops to 0.  */
  61   if (!freq_scale)
  62     freq_scale = 1;
  63   for (e = node->callees; e; e = e->next_callee)
  64     {
  65       e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
  66       if (e->frequency > CGRAPH_FREQ_MAX)
  67         e->frequency = CGRAPH_FREQ_MAX;
  68       if (!e->inline_failed)
  69         update_noncloned_frequencies (e->callee, freq_scale);
  70     }
  71   for (e = node->indirect_calls; e; e = e->next_callee)
  72     {
  73       e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
  74       if (e->frequency > CGRAPH_FREQ_MAX)
  75         e->frequency = CGRAPH_FREQ_MAX;
  76     }
  77 }
  78
  79
  80 /* E is expected to be an edge being inlined.  Clone destination node of
  81    the edge and redirect it to the new clone.
  82    DUPLICATE is used for bookkeeping on whether we are actually creating new
  83    clones or re-using node originally representing out-of-line function call.
  84    */
  85
  86 void
  87 clone_inlined_nodes (struct cgraph_edge *e, bool duplicate,
  88                      bool update_original, int *overall_size)
  89 {
  90   if (duplicate)
  91     {
  92       /* We may eliminate the need for out-of-line copy to be output.
  93          In that case just go ahead and re-use it.  This is not just an
  94          memory optimization.  Making offline copy of fuction disappear
  95          from the program will improve future decisions on inlining.  */
  96       if (!e->callee->callers->next_caller
  97           /* Recursive inlining never wants the master clone to
  98              be overwritten.  */
  99           && update_original
 100           /* FIXME: When address is taken of DECL_EXTERNAL function we still
 101              can remove its offline copy, but we would need to keep unanalyzed
 102              node in the callgraph so references can point to it.  */
 103           && !e->callee->address_taken
 104           && cgraph_can_remove_if_no_direct_calls_p (e->callee)
 105           /* Inlining might enable more devirtualizing, so we want to remove
 106              those only after all devirtualizable virtual calls are processed.
 107              Lacking may edges in callgraph we just preserve them post
 108              inlining.  */
 109           && (!DECL_VIRTUAL_P (e->callee->decl)
 110               || (!DECL_COMDAT (e->callee->decl)
 111                   && !DECL_EXTERNAL (e->callee->decl)))
 112           /* Don't reuse if more than one function shares a comdat group.
 113              If the other function(s) are needed, we need to emit even
 114              this function out of line.  */
 115           && !e->callee->same_comdat_group
 116           /* During early inlining some unanalyzed cgraph nodes might be in the
 117              callgraph and they might reffer the function in question.  */
 118           && !cgraph_new_nodes)
 119         {
 120           gcc_assert (!e->callee->global.inlined_to);
 121           if (e->callee->analyzed && !DECL_EXTERNAL (e->callee->decl))
 122             {
 123               if (overall_size)
 124                 *overall_size -= inline_summary (e->callee)->size;
 125               nfunctions_inlined++;
 126             }
 127           duplicate = false;
 128           e->callee->local.externally_visible = false;
 129           update_noncloned_frequencies (e->callee, e->frequency);
 130         }
 131       else
 132         {
 133           struct cgraph_node *n;
 134           n = cgraph_clone_node (e->callee, e->callee->decl,
 135                                  e->count, e->frequency,
 136                                  update_original, NULL);
 137           cgraph_redirect_edge_callee (e, n);
 138         }
 139     }
 140
 141   if (e->caller->global.inlined_to)
 142     e->callee->global.inlined_to = e->caller->global.inlined_to;
 143   else
 144     e->callee->global.inlined_to = e->caller;
 145
 146   /* Recursively clone all bodies.  */
 147   for (e = e->callee->callees; e; e = e->next_callee)
 148     if (!e->inline_failed)
 149       clone_inlined_nodes (e, duplicate, update_original, overall_size);
 150 }
 151
 152
 153 /* Mark edge E as inlined and update callgraph accordingly.  UPDATE_ORIGINAL
 154    specify whether profile of original function should be updated.  If any new
 155    indirect edges are discovered in the process, add them to NEW_EDGES, unless
 156    it is NULL.  Return true iff any new callgraph edges were discovered as a
 157    result of inlining.  */
 158
 159 bool
 160 inline_call (struct cgraph_edge *e, bool update_original,
 161              VEC (cgraph_edge_p, heap) **new_edges,
 162              int *overall_size)
 163 {
 164   int old_size = 0, new_size = 0;
 165   struct cgraph_node *to = NULL;
 166   struct cgraph_edge *curr = e;
 167
 168   /* Don't inline inlined edges.  */
 169   gcc_assert (e->inline_failed);
 170   /* Don't even think of inlining inline clone.  */
 171   gcc_assert (!e->callee->global.inlined_to);
 172
 173   e->inline_failed = CIF_OK;
 174   DECL_POSSIBLY_INLINED (e->callee->decl) = true;
 175
 176   to = e->caller;
 177   if (to->global.inlined_to)
 178     to = to->global.inlined_to;
 179
 180   clone_inlined_nodes (e, true, update_original, overall_size);
 181
 182   gcc_assert (curr->callee->global.inlined_to == to);
 183
 184   old_size = inline_summary (to)->size;
 185   inline_merge_summary (e);
 186   new_size = inline_summary (to)->size;
 187   if (overall_size && new_size > old_size)
 188     *overall_size += new_size - old_size;
 189   ncalls_inlined++;
 190
 191   if (flag_indirect_inlining && optimize)
 192     return ipa_propagate_indirect_call_infos (curr, new_edges);
 193   else
 194     return false;
 195 }
 196
 197
 198 /* Copy function body of NODE and redirect all inline clones to it.
 199    This is done before inline plan is applied to NODE when there are
 200    still some inline clones if it.
 201
 202    This is neccesary because inline decisions are not really transitive
 203    and the other inline clones may have different bodies.  */
 204
 205 static struct cgraph_node *
 206 save_inline_function_body (struct cgraph_node *node)
 207 {
 208   struct cgraph_node *first_clone, *n;
 209
 210   if (dump_file)
 211     fprintf (dump_file, "\nSaving body of %s for later reuse\n",
 212              cgraph_node_name (node));
 213
 214   gcc_assert (node == cgraph_get_node (node->decl));
 215
 216   /* first_clone will be turned into real function.  */
 217   first_clone = node->clones;
 218   first_clone->decl = copy_node (node->decl);
 219   cgraph_insert_node_to_hashtable (first_clone);
 220   gcc_assert (first_clone == cgraph_get_node (first_clone->decl));
 221
 222   /* Now reshape the clone tree, so all other clones descends from
 223      first_clone.  */
 224   if (first_clone->next_sibling_clone)
 225     {
 226       for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
 227         n->clone_of = first_clone;
 228       n->clone_of = first_clone;
 229       n->next_sibling_clone = first_clone->clones;
 230       if (first_clone->clones)
 231         first_clone->clones->prev_sibling_clone = n;
 232       first_clone->clones = first_clone->next_sibling_clone;
 233       first_clone->next_sibling_clone->prev_sibling_clone = NULL;
 234       first_clone->next_sibling_clone = NULL;
 235       gcc_assert (!first_clone->prev_sibling_clone);
 236     }
 237   first_clone->clone_of = NULL;
 238
 239   /* Now node in question has no clones.  */
 240   node->clones = NULL;
 241
 242   /* Inline clones share decl with the function they are cloned
 243      from.  Walk the whole clone tree and redirect them all to the
 244      new decl.  */
 245   if (first_clone->clones)
 246     for (n = first_clone->clones; n != first_clone;)
 247       {
 248         gcc_assert (n->decl == node->decl);
 249         n->decl = first_clone->decl;
 250         if (n->clones)
 251           n = n->clones;
 252         else if (n->next_sibling_clone)
 253           n = n->next_sibling_clone;
 254         else
 255           {
 256             while (n != first_clone && !n->next_sibling_clone)
 257               n = n->clone_of;
 258             if (n != first_clone)
 259               n = n->next_sibling_clone;
 260           }
 261       }
 262
 263   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
 264   tree_function_versioning (node->decl, first_clone->decl, NULL, true, NULL,
 265                             NULL, NULL);
 266
 267   /* The function will be short lived and removed after we inline all the clones,
 268      but make it internal so we won't confuse ourself.  */
 269   DECL_EXTERNAL (first_clone->decl) = 0;
 270   DECL_COMDAT_GROUP (first_clone->decl) = NULL_TREE;
 271   TREE_PUBLIC (first_clone->decl) = 0;
 272   DECL_COMDAT (first_clone->decl) = 0;
 273   VEC_free (ipa_opt_pass, heap,
 274             first_clone->ipa_transforms_to_apply);
 275   first_clone->ipa_transforms_to_apply = NULL;
 276
 277 #ifdef ENABLE_CHECKING
 278   verify_cgraph_node (first_clone);
 279 #endif
 280   return first_clone;
 281 }
 282
 283
 284 /* Apply inline plan to function.  */
 285
 286 unsigned int
 287 inline_transform (struct cgraph_node *node)
 288 {
 289   unsigned int todo = 0;
 290   struct cgraph_edge *e;
 291   bool inline_p = false;
 292
 293   /* FIXME: Currently the pass manager is adding inline transform more than
 294      once to some clones.  This needs revisiting after WPA cleanups.  */
 295   if (cfun->after_inlining)
 296     return 0;
 297
 298   /* We might need the body of this function so that we can expand
 299      it inline somewhere else.  */
 300   if (cgraph_preserve_function_body_p (node))
 301     save_inline_function_body (node);
 302
 303   for (e = node->callees; e; e = e->next_callee)
 304     {
 305       cgraph_redirect_edge_call_stmt_to_callee (e);
 306       if (!e->inline_failed || warn_inline)
 307         inline_p = true;
 308     }
 309
 310   if (inline_p)
 311     {
 312       timevar_push (TV_INTEGRATION);
 313       todo = optimize_inline_calls (current_function_decl);
 314       timevar_pop (TV_INTEGRATION);
 315     }
 316   cfun->always_inline_functions_inlined = true;
 317   cfun->after_inlining = true;
 318   return todo | execute_fixup_cfg ();
 319 }