gcc/ipa-inline-analysis.c

   1 /* Inlining decision heuristics.
   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 /* Analysis used by the inliner and other passes limiting code size growth.
  23
  24    We estimate for each function
  25      - function body size
  26      - function runtime
  27      - inlining size benefit (that is how much of function body size
  28        and its call sequence is expected to disappear by inlining)
  29      - inlining time benefit
  30      - function frame size
  31    For each call
  32      - call sequence size
  33
  34    inlinie_summary datastructures store above information locally (i.e.
  35    parameters of the function itself) and globally (i.e. parameters of
  36    the function created by applying all the inline decisions already
  37    present in the callgraph).
  38
  39    We also provide accestor to the inline_summary datastructure and
  40    basic logic updating the parameters when inlining is performed.
  41
  42    Finally pass_inline_parameters is exported.  This is used to drive
  43    computation of function parameters used by the early inliner. IPA
  44    inlined performs analysis via its analyze_function method. */
  45
  46 #include "config.h"
  47 #include "system.h"
  48 #include "coretypes.h"
  49 #include "tm.h"
  50 #include "tree.h"
  51 #include "tree-inline.h"
  52 #include "langhooks.h"
  53 #include "flags.h"
  54 #include "cgraph.h"
  55 #include "diagnostic.h"
  56 #include "gimple-pretty-print.h"
  57 #include "timevar.h"
  58 #include "params.h"
  59 #include "tree-pass.h"
  60 #include "coverage.h"
  61 #include "ggc.h"
  62 #include "tree-flow.h"
  63 #include "ipa-prop.h"
  64 #include "ipa-inline.h"
  65
  66 #define MAX_TIME 1000000000
  67
  68 /* Holders of ipa cgraph hooks: */
  69 static struct cgraph_node_hook_list *function_insertion_hook_holder;
  70
  71 /* See if statement might disappear after inlining.
  72    0 - means not eliminated
  73    1 - half of statements goes away
  74    2 - for sure it is eliminated.
  75    We are not terribly sophisticated, basically looking for simple abstraction
  76    penalty wrappers.  */
  77
  78 static int
  79 eliminated_by_inlining_prob (gimple stmt)
  80 {
  81   enum gimple_code code = gimple_code (stmt);
  82   switch (code)
  83     {
  84       case GIMPLE_RETURN:
  85         return 2;
  86       case GIMPLE_ASSIGN:
  87         if (gimple_num_ops (stmt) != 2)
  88           return 0;
  89
  90         /* Casts of parameters, loads from parameters passed by reference
  91            and stores to return value or parameters are often free after
  92            inlining dua to SRA and further combining.
  93            Assume that half of statements goes away.  */
  94         if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
  95             || gimple_assign_rhs_code (stmt) == NOP_EXPR
  96             || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
  97             || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
  98           {
  99             tree rhs = gimple_assign_rhs1 (stmt);
 100             tree lhs = gimple_assign_lhs (stmt);
 101             tree inner_rhs = rhs;
 102             tree inner_lhs = lhs;
 103             bool rhs_free = false;
 104             bool lhs_free = false;
 105
 106             while (handled_component_p (inner_lhs)
 107                    || TREE_CODE (inner_lhs) == MEM_REF)
 108               inner_lhs = TREE_OPERAND (inner_lhs, 0);
 109             while (handled_component_p (inner_rhs)
 110                    || TREE_CODE (inner_rhs) == ADDR_EXPR
 111                    || TREE_CODE (inner_rhs) == MEM_REF)
 112               inner_rhs = TREE_OPERAND (inner_rhs, 0);
 113
 114
 115             if (TREE_CODE (inner_rhs) == PARM_DECL
 116                 || (TREE_CODE (inner_rhs) == SSA_NAME
 117                     && SSA_NAME_IS_DEFAULT_DEF (inner_rhs)
 118                     && TREE_CODE (SSA_NAME_VAR (inner_rhs)) == PARM_DECL))
 119               rhs_free = true;
 120             if (rhs_free && is_gimple_reg (lhs))
 121               lhs_free = true;
 122             if (((TREE_CODE (inner_lhs) == PARM_DECL
 123                   || (TREE_CODE (inner_lhs) == SSA_NAME
 124                       && SSA_NAME_IS_DEFAULT_DEF (inner_lhs)
 125                       && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == PARM_DECL))
 126                  && inner_lhs != lhs)
 127                 || TREE_CODE (inner_lhs) == RESULT_DECL
 128                 || (TREE_CODE (inner_lhs) == SSA_NAME
 129                     && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == RESULT_DECL))
 130               lhs_free = true;
 131             if (lhs_free
 132                 && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
 133               rhs_free = true;
 134             if (lhs_free && rhs_free)
 135               return 1;
 136           }
 137         return 0;
 138       default:
 139         return 0;
 140     }
 141 }
 142
 143
 144 /* Compute function body size parameters for NODE.  */
 145
 146 static void
 147 estimate_function_body_sizes (struct cgraph_node *node)
 148 {
 149   gcov_type time = 0;
 150   gcov_type time_inlining_benefit = 0;
 151   /* Estimate static overhead for function prologue/epilogue and alignment. */
 152   int size = 2;
 153   /* Benefits are scaled by probability of elimination that is in range
 154      <0,2>.  */
 155   int size_inlining_benefit = 2 * 2;
 156   basic_block bb;
 157   gimple_stmt_iterator bsi;
 158   struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
 159   int freq;
 160
 161   if (dump_file)
 162     fprintf (dump_file, "Analyzing function body size: %s\n",
 163              cgraph_node_name (node));
 164
 165   gcc_assert (my_function && my_function->cfg);
 166   FOR_EACH_BB_FN (bb, my_function)
 167     {
 168       freq = compute_call_stmt_bb_frequency (node->decl, bb);
 169       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 170         {
 171           gimple stmt = gsi_stmt (bsi);
 172           int this_size = estimate_num_insns (stmt, &eni_size_weights);
 173           int this_time = estimate_num_insns (stmt, &eni_time_weights);
 174           int prob;
 175
 176           if (dump_file && (dump_flags & TDF_DETAILS))
 177             {
 178               fprintf (dump_file, "  freq:%6i size:%3i time:%3i ",
 179                        freq, this_size, this_time);
 180               print_gimple_stmt (dump_file, stmt, 0, 0);
 181             }
 182           this_time *= freq;
 183           time += this_time;
 184           size += this_size;
 185           prob = eliminated_by_inlining_prob (stmt);
 186           if (prob == 1 && dump_file && (dump_flags & TDF_DETAILS))
 187             fprintf (dump_file, "    50%% will be eliminated by inlining\n");
 188           if (prob == 2 && dump_file && (dump_flags & TDF_DETAILS))
 189             fprintf (dump_file, "    will eliminated by inlining\n");
 190           size_inlining_benefit += this_size * prob;
 191           time_inlining_benefit += this_time * prob;
 192           gcc_assert (time >= 0);
 193           gcc_assert (size >= 0);
 194         }
 195     }
 196   time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
 197   time_inlining_benefit = ((time_inlining_benefit + CGRAPH_FREQ_BASE)
 198                            / (CGRAPH_FREQ_BASE * 2));
 199   size_inlining_benefit = (size_inlining_benefit + 1) / 2;
 200   if (time_inlining_benefit > MAX_TIME)
 201     time_inlining_benefit = MAX_TIME;
 202   if (time > MAX_TIME)
 203     time = MAX_TIME;
 204   if (dump_file)
 205     fprintf (dump_file, "Overall function body time: %i-%i size: %i-%i\n",
 206              (int)time, (int)time_inlining_benefit,
 207              size, size_inlining_benefit);
 208   inline_summary (node)->self_time = time;
 209   inline_summary (node)->self_size = size;
 210   inline_summary (node)->time_inlining_benefit = time_inlining_benefit;
 211   inline_summary (node)->size_inlining_benefit = size_inlining_benefit;
 212 }
 213
 214
 215 /* Compute parameters of functions used by inliner.  */
 216
 217 void
 218 compute_inline_parameters (struct cgraph_node *node)
 219 {
 220   HOST_WIDE_INT self_stack_size;
 221   struct cgraph_edge *e;
 222
 223   gcc_assert (!node->global.inlined_to);
 224
 225   /* Estimate the stack size for the function if we're optimizing.  */
 226   self_stack_size = optimize ? estimated_stack_frame_size (node) : 0;
 227   inline_summary (node)->estimated_self_stack_size = self_stack_size;
 228   node->global.estimated_stack_size = self_stack_size;
 229   node->global.stack_frame_offset = 0;
 230
 231   /* Can this function be inlined at all?  */
 232   node->local.inlinable = tree_inlinable_function_p (node->decl);
 233   if (!node->local.inlinable)
 234     node->local.disregard_inline_limits = 0;
 235
 236   /* Inlinable functions always can change signature.  */
 237   if (node->local.inlinable)
 238     node->local.can_change_signature = true;
 239   else
 240     {
 241       /* Functions calling builtin_apply can not change signature.  */
 242       for (e = node->callees; e; e = e->next_callee)
 243         if (DECL_BUILT_IN (e->callee->decl)
 244             && DECL_BUILT_IN_CLASS (e->callee->decl) == BUILT_IN_NORMAL
 245             && DECL_FUNCTION_CODE (e->callee->decl) == BUILT_IN_APPLY_ARGS)
 246           break;
 247       node->local.can_change_signature = !e;
 248     }
 249   estimate_function_body_sizes (node);
 250   /* Compute size of call statements.  We have to do this for callers here,
 251      those sizes need to be present for edges _to_ us as early as
 252      we are finished with early opts.  */
 253   for (e = node->callers; e; e = e->next_caller)
 254     if (e->call_stmt)
 255       {
 256         e->call_stmt_size
 257           = estimate_num_insns (e->call_stmt, &eni_size_weights);
 258         e->call_stmt_time
 259           = estimate_num_insns (e->call_stmt, &eni_time_weights);
 260       }
 261   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
 262   node->global.time = inline_summary (node)->self_time;
 263   node->global.size = inline_summary (node)->self_size;
 264 }
 265
 266
 267 /* Compute parameters of functions used by inliner using
 268    current_function_decl.  */
 269
 270 static unsigned int
 271 compute_inline_parameters_for_current (void)
 272 {
 273   compute_inline_parameters (cgraph_get_node (current_function_decl));
 274   return 0;
 275 }
 276
 277 struct gimple_opt_pass pass_inline_parameters =
 278 {
 279  {
 280   GIMPLE_PASS,
 281   "inline_param",                       /* name */
 282   NULL,                                 /* gate */
 283   compute_inline_parameters_for_current,/* execute */
 284   NULL,                                 /* sub */
 285   NULL,                                 /* next */
 286   0,                                    /* static_pass_number */
 287   TV_INLINE_HEURISTICS,                 /* tv_id */
 288   0,                                    /* properties_required */
 289   0,                                    /* properties_provided */
 290   0,                                    /* properties_destroyed */
 291   0,                                    /* todo_flags_start */
 292   0                                     /* todo_flags_finish */
 293  }
 294 };
 295
 296
 297 /* Estimate the time cost for the caller when inlining EDGE.  */
 298
 299 static inline int
 300 estimate_edge_time (struct cgraph_edge *edge)
 301 {
 302   int call_stmt_time;
 303   /* ???  We throw away cgraph edges all the time so the information
 304      we store in edges doesn't persist for early inlining.  Ugh.  */
 305   if (!edge->call_stmt)
 306     call_stmt_time = edge->call_stmt_time;
 307   else
 308     call_stmt_time = estimate_num_insns (edge->call_stmt, &eni_time_weights);
 309   return (((gcov_type)edge->callee->global.time
 310            - inline_summary (edge->callee)->time_inlining_benefit
 311            - call_stmt_time) * edge->frequency
 312           + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
 313 }
 314
 315
 316 /* Estimate self time of the function NODE after inlining EDGE.  */
 317
 318 int
 319 estimate_time_after_inlining (struct cgraph_node *node,
 320                               struct cgraph_edge *edge)
 321 {
 322   gcov_type time = node->global.time + estimate_edge_time (edge);
 323   if (time < 0)
 324     time = 0;
 325   if (time > MAX_TIME)
 326     time = MAX_TIME;
 327   return time;
 328 }
 329
 330
 331 /* Estimate the size of NODE after inlining EDGE which should be an
 332    edge to either NODE or a call inlined into NODE.  */
 333
 334 int
 335 estimate_size_after_inlining (struct cgraph_node *node,
 336                                      struct cgraph_edge *edge)
 337 {
 338   int size = node->global.size + estimate_edge_growth (edge);
 339   gcc_assert (size >= 0);
 340   return size;
 341 }
 342
 343
 344 /* Estimate the growth caused by inlining NODE into all callees.  */
 345
 346 int
 347 estimate_growth (struct cgraph_node *node)
 348 {
 349   int growth = 0;
 350   struct cgraph_edge *e;
 351   bool self_recursive = false;
 352
 353   if (node->global.estimated_growth != INT_MIN)
 354     return node->global.estimated_growth;
 355
 356   for (e = node->callers; e; e = e->next_caller)
 357     {
 358       if (e->caller == node)
 359         self_recursive = true;
 360       if (e->inline_failed)
 361         growth += estimate_edge_growth (e);
 362     }
 363
 364   /* ??? Wrong for non-trivially self recursive functions or cases where
 365      we decide to not inline for different reasons, but it is not big deal
 366      as in that case we will keep the body around, but we will also avoid
 367      some inlining.  */
 368   if (cgraph_will_be_removed_from_program_if_no_direct_calls (node)
 369       && !DECL_EXTERNAL (node->decl) && !self_recursive)
 370     growth -= node->global.size;
 371   /* COMDAT functions are very often not shared across multiple units since they
 372      come from various template instantiations.  Take this into account.  */
 373   else  if (DECL_COMDAT (node->decl) && !self_recursive
 374             && cgraph_can_remove_if_no_direct_calls_p (node))
 375     growth -= (node->global.size
 376                * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY)) + 50) / 100;
 377
 378   node->global.estimated_growth = growth;
 379   return growth;
 380 }
 381
 382 /* This function performs intraprocedural analysis in NODE that is required to
 383    inline indirect calls.  */
 384 static void
 385 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
 386 {
 387   ipa_analyze_node (node);
 388   if (dump_file && (dump_flags & TDF_DETAILS))
 389     {
 390       ipa_print_node_params (dump_file, node);
 391       ipa_print_node_jump_functions (dump_file, node);
 392     }
 393 }
 394
 395
 396 /* Note function body size.  */
 397
 398 static void
 399 inline_analyze_function (struct cgraph_node *node)
 400 {
 401   push_cfun (DECL_STRUCT_FUNCTION (node->decl));
 402   current_function_decl = node->decl;
 403
 404   compute_inline_parameters (node);
 405   /* FIXME: We should remove the optimize check after we ensure we never run
 406      IPA passes when not optimizing.  */
 407   if (flag_indirect_inlining && optimize)
 408     inline_indirect_intraprocedural_analysis (node);
 409
 410   current_function_decl = NULL;
 411   pop_cfun ();
 412 }
 413
 414
 415 /* Called when new function is inserted to callgraph late.  */
 416
 417 static void
 418 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 419 {
 420   inline_analyze_function (node);
 421 }
 422
 423
 424 /* Note function body size.  */
 425
 426 void
 427 inline_generate_summary (void)
 428 {
 429   struct cgraph_node *node;
 430
 431   function_insertion_hook_holder =
 432       cgraph_add_function_insertion_hook (&add_new_function, NULL);
 433
 434   if (flag_indirect_inlining)
 435     ipa_register_cgraph_hooks ();
 436
 437   for (node = cgraph_nodes; node; node = node->next)
 438     if (node->analyzed)
 439       inline_analyze_function (node);
 440
 441   return;
 442 }
 443
 444
 445 /* Read inline summary.  Jump functions are shared among ipa-cp
 446    and inliner, so when ipa-cp is active, we don't need to write them
 447    twice.  */
 448
 449 void
 450 inline_read_summary (void)
 451 {
 452   if (flag_indirect_inlining)
 453     {
 454       ipa_register_cgraph_hooks ();
 455       if (!flag_ipa_cp)
 456         ipa_prop_read_jump_functions ();
 457     }
 458   function_insertion_hook_holder =
 459       cgraph_add_function_insertion_hook (&add_new_function, NULL);
 460 }
 461
 462
 463 /* Write inline summary for node in SET.
 464    Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
 465    active, we don't need to write them twice.  */
 466
 467 void
 468 inline_write_summary (cgraph_node_set set,
 469                       varpool_node_set vset ATTRIBUTE_UNUSED)
 470 {
 471   if (flag_indirect_inlining && !flag_ipa_cp)
 472     ipa_prop_write_jump_functions (set);
 473 }
 474
 475 /* Release inline summary.  */
 476
 477 void
 478 inline_free_summary (void)
 479 {
 480   cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
 481 }